Vyčíslitelnost a složitost

Rozvrh předmětu

Přednáška: úterý 15:00-17:15
Cvičení: úterý 17:30-18:15

Sylabus předmětu

22.9.	Úvod do vyčíslitelnosti, Turingův stroj.
29.9.	Varianty Turingova stroje, programovací techniky TS. Nedeterministický TS. Univerzální TS.
6.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ů.
13.10.	NEBUDE (nahrazeno na konci semestru)
20.10.	Vztah jazyků TS k jazykům Chomského hierarchie.
27.10.	Redukce problémů. Riceova věta. Postův problém přiřazení a jeho aplikace.
3.11.	Věta o rekurzi, věta o minimální reprezentaci.
10.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
17.11.	STÁTNÍ SVÁTEK
24.11.	Další NP-úplné problémy.
1.12.	Třída paměťové složitosti PSPACE a PSPACE-úplné problémy. Třídy paměťové složitosti L a NL.
7.12.	1. OPRAVNÝ PÍSEMNÝ TEST dobrovolná hromadná konzultace; popřípadě rezerva,
14.12.	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.

Požadavky na zápočet

Dne 10.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 7.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 14.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

L1 -- přednáška 22.9. (update 23.9.2015: oprava indexů v definici kroku výpočtu, doplněno zakódování TS; uploaded: 16.9.2015)
L2 -- přednáška 29.9. (update 22.11.2015: spellcheck; update 4.10.2015: doplnění LBA; uploaded: 23.9.2015)
L3 -- přednáška 6.10. (update 26.11.2015: spellcheck; update 5.10.2015: doplněny enumeratory; uploaded: 24.9.2015)
L4 -- přednáška 20.10. (uploaded: 14.10.2015)
L5 -- přednáška 27.10. (update 30.10.2015: přidána Riceova věta s důkazem; uploaded: 23.10.2015)
L6 -- přednáška 3.11. ((update 26.11.2015: spellcheck; update 13.11.2015: přejmenování; update 30.10.2015: odstraněna Riceova věta s důkazem; uploaded: 24.10.2015)
L7 -- přednáška 10.11. (update 25.11.2015: oprava formulí A,B,C v důkazu Cookovy věty; update 13.11.2015: přejmenování, doplění NP-úplných problémů, sjednocení názvosloví; uploaded: 30.10.2015)
L8 -- přednáška 24.11. (uploaded: 15.11.2015)
L9 -- přednáška 1.12. (update 25.11.2015: důkaz Savitchovy věty; uploaded: 19.11.2015)
další budou průběžně doplněny.