Sylabus

• Algoritmus jako výpočetní model. Churchova teze.
  
• Vyčíslitelné funkce a jejich numerace.
  
• Vyčíslitelné vlastnosti množin a rozhodnutelnost problémů.
• Uzávěrové vlastnosti, Riceovy věty.
• Redukce.
  
• Časová a prostorová složitost algoritmů a problémů.
  
• Základní složitostní třídy.
  
• Polynomiální redukce a úplnost v třídách problémů.
  
• NP-úplné problémy.

Literatura

Výuka se bude opírat o tři základní texty: skripta prof. Brima o Vyčíslitelnosti, skripta téhož autora o Složitosti, a dále o sbírku příkladů.

Ke studiu lze využít i následující literaturu.

• KOZEN, Dexter C. Automata and computability. New York: Springer, 1997. xiii, 400. ISBN 0387949070. info
• SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. info
• BOVET, D. a Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994. xi, 282 s. ISBN 0-13-915380-2. info
• KFOURY, A. J., Robert N. MOLL a Michael A. ARBIB. A programming approach to computability. New York: Springer-Verlag, 1982. viii, 251. ISBN 0-387-90743-2. info

Jako bonus přidáváme odkaz na pěkné motivační video.

Výuka

Vzhledem k platným omezením a horšící se situaci prezenční přednášky nebudou. V prvním týdnu v úterý 14. 9. 2021 od 10:00 proběhne úvodní část přednášky věnovaná organizačním záležitostem formou videokonference v MS Teams (odkaz naleznete v ISu). Tato přednáška bude nahrávána a záznam bude následně zveřejněný. Vlastní učivo bude prezentováno v 11-12 blocích. Každý blok bude obsahovat několik kratších videí. Videa budou využívat "řídké" slajdy, které také budou k dispozici.

V dalších týdnech budou vždy v úterý od 10:00 probíhat online konzultační hodiny přes MS Teams, kde můžete klást dotazy k učivu nebo k předmětu obecně.

Cvičení budou probíhat prezenčně (alespoň prozatím). Na všech skupinách se budou cvičit stejné příklady. Skupina IB107/A bude klást více důrazu na samostatnou práci (a je proto nevhodná pro studenty, kteří preferují společné řešení příkladů). V pondělí 13. 9. 2021 cvičení nebudou.

Jakékoliv dotazy k předmětu je možné pokládat také v diskusním fóru předmětu, které budou vyučující sledovat.

Domácí úkoly

Během semestru zadáme tři domácí úkoly (přibližně na konci první, druhé a třetí čtvrtiny semestru). Z každého úkolu bude možné získat až 6 bodů. Úkoly nebudou povinné, ale k úspešnému absolvování bude třeba získat z úkolů alespoň 9 bodů. Body získané z úkolů nad tuto hranici slouží jako tzv. měkké body a mohou vylepšit známku v připadě úspěšného absolvování předmětu.

Hodnocení

V předmětu nebude žádná vnitrosemestrální písemka, pouze závěrečná zkoušková písemka. Na tuto písemku mohou přijít pouze studenti, kteří z domácích úkolů získají alespoň 9 bodů. Písemka bude na 100 bodů. Kdo z písemky získá méně než 50 bodů, dostane hodnocení F. Kdo z písemky získá alespoň 50 bodů, tomu se přičtou měkké body z domácích úkolů a známka se určí dle následující tabulky:

Studenti, kteří si zvolí ukončení předmětu zápočtem (zdaleka ne všechny studijní programy tuto volbu umožňují), musí taktéž získat z domácích úkolů alespoň 9 bodů. Body z domácích úkolů získaných nad tuto hranici se jim však přičtou k bodům ze závěrečné písemky automaticky. Pro získání zápočtu musí součet těchto bodů být alespoň 50.

• Ke každé sadě domácích úloh bude zveřejněna samostatná kapitola v interaktivní osnově, obsahující odkazy na zadání a odevzdávárny. Rovněž zde budou uvedeny termíny pro odevzdání.
• Kvůli čitelnosti požadujeme, abyste úkoly odevzdávali strojově vysázené, nikoliv ručně psané. Konkrétně je vyžadováno odevzdání ve formě pdf souboru vysázeného systémem LaTeX se standardní "skenovací" hlavičkou FI. Za tímto účelem budete mít u každého úkolu k dispozici předchystaný TeX-ový soubor se zadáním a požadovaným formátem. K úspěšnému přeložení souboru budete potřebovat soubor se správným stylem "vycsloz.cls," který je k dispozici ve studijních materiálech:
  Chyba: Odkazovaný objekt neexistuje nebo nemáte právo jej číst.

  https://is.muni.cz/el/fi/podzim2021/IB107/um/du/vycsloz.cls
• Kvůli vypracování úkolu si nemusíte instalovat LaTeX na svůj stroj, můžete například využít Overleaf, k němuž je dostupná fakultní licence.
• Vzhledem k výše uvedenému je vysoce doporučeno vysázet samotné řešení rovněž systémem LaTeX. Je pro Vás užitečné se s tímto systémem seznámit (pakliže se tak již nestalo), zejména s ohledem na to, že většina z Vás je nyní ve 3. ročníku a brzy Vás čeká psaní bakalářské práce. Níže naleznete nějaké zdroje pro práci s TeXem. Pokud ale TeX skutečně použít nechcete, můžete řešení připravit v jiném programu (např. Word), vyexportovat jej do pdf a toto pdf poté vložit do předpřipraveného TeXového souboru (přímo v souboru je na vhodném místě napsáno, jak na to). Tento soubor pak opět přeložíte LaTeXem a dostanete soubor s požadovanou skenovatelnou hlavičkou.
• V každém případě nezapomeňte ve zdrojovém TeXovém souboru na správné místo vyplnit Vaše jméno a UČO tím, že změníte definici příslušných maker. Ve zdrojovém souboru je to popsáno. Kromě maker \name a \uco neměňte nic mimo prostředí "reseni".
• Odevzdávárny umožňují přepisovat odevzdané soubory. Pokud si tedy před deadlinem uvědomíte chybu v řešení, odevzdaný soubor přepište. Pokud budete mít v jedné odevzdávárně více odevzdaných souborů, opraví opravující pouze jeden z nich (v pořadí, v jakém se k nim dostane, tj. víceméně náhodně), a pouze ten bude obodován.
  
• Nad úkoly můžete vzájemně diskutovat. Ze společné porady si však odneste pouze myšlenku. Vlastní řešení musí každý student zformulovat zcela samostatně (vlastními slovy), nikoliv jako kopii (či drobnou obměnu) cizího řešení. Zjištěné případy opisování budou postoupeny disciplinární komisi (a navíc přijdete o body z úkolu).
• Zadání i vzorová řešení úkolů dále nešiřte. Jedná se o porušení disciplinárního řádu FI.
  
• Informace k práci s TeXem:
  Cheat sheet z předmětu IB005
  LaTeX Wikibook
  StackExchange

Studium

V úterý 14. 9. 2021 proběhla úvodní část přednášky věnovaná organizačním záležitostem formou videokonference v MS Teams. Zde je záznam:

Učivo z tohoto bloku je popsáno na stranách 7-23 těchto skript:

Následují slajdy k prvnímu bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Studium

Učivo tohoto bloku je popsáno na stranách 24-35 těchto skript:

Následují slajdy k druhému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Jelikož je v úterý 28. 9. 2021 státní svátek, nebudou se v tomto týdnu konat online konzultace. Všechna cvičení však normálně proběhnou s výjimkou úterní skupiny, která bude pokračovat třetím cvičením v dalším týdnu (proto není třeba toto cvičení nijak nahrazovat).

Studium

Učivo tohoto bloku je popsáno na stranách 36-41 těchto skript:

Následují slajdy k třetímu bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Nejprve se seznamte s obecnými informacemi o hodnocení tohoto předmětu a s technickými informacemi o domácích úlohách.

Termín pro odevzdání je 12. října, 23:59. Tento termín je striktní!

Odevzdávejte skrze odevzdávárny níže. Na jménu souboru nezáleží, IS jej sám přejmenuje. Nezapomeňte v odevzdaných souborech vyplnit jméno a učo, ať tam pak nemáme spoustu Ferdů Mravenců a Brouků Pytlíků. :-)

Vzorová řešení

Videa k tomuto bloku jsou přibližně o 20 minut delší, než by odpovídalo standardní přednášce. Berte to prosím jako příslib kratších videí v týdnu příštím.

Studium

Učivo tohoto bloku je popsáno na stranách 42-50 těchto skript:

Studium

Učivo tohoto bloku je popsáno na stranách 51-54 těchto skript:

Následují slajdy k pátému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Studium

Učivo tohoto bloku je popsáno na stranách 55-59 těchto skript:

Následují slajdy k šestému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Nejprve se seznamte s obecnými informacemi o hodnocení tohoto předmětu a s technickými informacemi o domácích úlohách.

Termín pro odevzdání je 2. listopadu, 23:59. Tento termín je striktní!

Odevzdávejte skrze odevzdávárny níže. Na jménu souboru nezáleží, IS jej sám přejmenuje. Nezapomeňte v odevzdaných souborech vyplnit jméno a učo.

Vzorová řešení

Videa jsou opět dohromady o něco delší, ale první je jen opakování a čtvrté je nepovinné.

Studium

Učivo tohoto bloku je popsáno na stranách 60-63 těchto skript:

Redukce v terminologii Turingových strojů a Postův korespondenční problém jsou popsány v kapitolách 5.4 a 5.6 skript k předmětu IB005:

Následují slajdy k sedmému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Jako další zdroj informací k redukcím (v kontextu Turingových strojů) lze použít následující democvičení z FJA natočené v závěru jarního semestru 2020.

Studium

Učivo tohoto bloku je popsáno v kapitolách 1.1 až 1.3 těchto skript:

Následují slajdy k osmému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Studium

Učivo tohoto bloku je popsáno v kapitolách 1.4 až 1.5.2 těchto skript:

Následují slajdy k devátému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Jelikož je ve středu 17. 11. 2021 státní svátek a tudíž i poslední cvičení naberou zpoždění za přednáškou, rozložíme 10. blok do dvou kratších částí (část A a část B), kterým se budeme věnovat tento a následující týden. Poslední domácí úkol bude zveřejněný po dokončení 10. bloku.

Studium

Učivo tohoto bloku je popsáno v kapitole 1.5 těchto skript:

Následují slajdy k desátému bloku (část A končí slajdem 12), které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Studium

Učivo tohoto bloku (s vyjímkou problému VERTEX-COVER, který je popsán například v knize od M. Sipsera zmíněné v doporučené literatuře) je popsáno v kapitole 1.5 těchto skript:

Nejprve se seznamte s obecnými informacemi o hodnocení tohoto předmětu a s technickými informacemi o domácích úlohách.

Termín pro odevzdání je 7. prosince 12. prosince, 23:59. Tento termín je striktní!

Odevzdávejte skrze odevzdávárny níže. Na jménu souboru nezáleží, IS jej sám přejmenuje. Nezapomeňte v odevzdaných souborech vyplnit jméno a učo.

Vzorová řešení DÚ 3 z roku 2020 (pro inspiraci)

Vzorová řešení

V ISu již najdete termíny zkouškových písemek. Jejich forma bude vzhledem k aktuální situaci upřesněna později.

Studium

Učivo tohoto bloku je popsáno (s výjimkou sublineární prostorové složitosti) v kapitolách 2.1 až 2.3 těchto skript:

Následují slajdy k jedenáctému bloku, které si můžete vytisknout a dělat si do nich poznámky, a dále již výuková videa.

Na zkoušky se prosím nezapomeňte v ISu včas přihlásit. Přihlásíte-li se jako na řádný termín až na 27. 1. 2022, dobrovolně se tím vzdáváte nároku na druhý opravný termín. To se samozřejmě nevztavuje na případy, kdy na nějaký zkouškový termín budete mít platnou omluvenku v ISu.

Zkoušky se pravděpodobně uskuteční prezenčně. Zadání bude podobné, jako bylo minulého roku při online zkouškách, zejména nebude obsahovat příklady typu "Zformulujte 2. Riceovu větu", ale budou tam příklady na přemýšlení. Proto budete moci mít libovolné studijní materiály (na papíru, nikoliv v telefonech/tabletech/počítačích). Zkoušková písemka bude trvat 100 minut.

0. termín (ukázkový)