Vyčíslitelnost a složitost

Rozvrh předmětu

Přednáška: středa 15:00-17:15
Cvičení: středa 17:30-18:15

Sylabus předmětu

24.9.	Úvod do vyčíslitelnosti, Turingův stroj.
1.10.	Varianty Turingova stroje, programovací techniky TS. Nedeterministický TS. Univerzální TS.
8.10.	--- NEBUDE
15.10.	Problémy, které nejsou řešitelné, a problémy které nejsou ani částečně řešitelné. Uzávěrové vlastnosti rekurzivních a částečně rekurzivních jazyků.
22.10.	Vztah jazyků TS k jazykům Chomského hierarchie.
29.10.	Redukce problémů.
5.11.	Postův problém přiřazení a jeho aplikace. Riceova věta. Věta o rekurzi, věta o minimální reprezentaci.
12.11.	Časová a paměťová složitost, třídy složitostí, třídy P, NP, NP-úplné problémy, Cookova věta dokazování NP-úplnosti.ZÁPOČTOVÝ PÍSEMNÝ TEST
19.11.	Další NP-úplné problémy.
26.11.	Třída paměťové složitosti PSPACE a PSPACE-úplné problémy.
3.12.	Třídy paměťové složitosti L a NL. 1. OPRAVNÝ PÍSEMNÝ TEST
10.12.	dobrovolná hromadná konzultace; popřípadě rezerva, 2. OPRAVNÝ PÍSEMNÝ TEST

Doporučená literatura

Sipser M. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA, 1997. ISBN 0-534-94728-X.
Hopcroft, J. E., Motwani, R., Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. 2nd ed.. Pearson Addison Wesley, Upper Saddle River, 2003. ISBN 0321210298.
další uvedena na slajdech.

Požadavky na zápočet

Dne 12.11. proběhne zápočtový písemný test, ve kterém je možné získat až 100 bodů (obsah: vyčíslitelnost). Pro zápočet je nutné získat alespoň 100 bodů.

Dne 3.12. proběhne opravný písemný zápočtový test, ve kterém je možné získat až 100 bodů (obsah: složitost). Pro zápočet je nutné získat alespoň 100 bodů v součtu s prvním testem.

Dne 10.12. proběhne druhý opravný písemný text, ve kterém bude možné získat až 80 bodů. Body získané v tomto testu nahrazují horší výsledek z předchozích dvou testů. Pro zápočet je nutné získat v součtu alespoň 100 bodů po této náhradě.

Požadavky na zkoušku

Klasická ústní zkouška.

Výukové materiály (v průběhu semestru budou ještě aktualizovány; dat si nevšímejte)

24.9. Úvodní kydy, Turingovy stroje a jejich jazyky (00.pdf, 01.pdf)
1.10. Varianty TS (02.pdf)
8.10. Problémy, které nejsou řešitelné, a problémy které nejsou ani částečně řešitelné. Uzávěrové vlastnosti rekurzivních a částečně rekurzivních jazyků. (03.pdf)
ODSUD VÝŠ JE TO AKTUALIZOVANÉ
15.10. Jazyky TS a jazyky gramatik Chomskeho hierarchie (04.pdf)
22.10. Redukovatelnost (05.pdf)
29.10. PPP (06.pdf)
5.11. Věta o rekurzi (07.pdf)
12.11. Úvod do složitosti (08.pdf)
19.11. NP-úplnost (09.pdf)
26.11. Další NP-úplné problémy (10.pdf)
3.12. Paměťová složitost, PSACE, Bremermannova mez (11.pdf)
3.12. Paměťová složitost, L a NL (12.pdf)