Vyčíslitelnost a složitost

Rozvrh předmětu

Přednáška: úterý 08:00-10:15
Cvičení: úterý 10:30-11: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.	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ů.
15.10.	Vztah jazyků TS k jazykům Chomského hierarchie. (nepřítomnost; bude suplovat dr. Osička)
22.10.	Redukce problémů.
30.10.	Postův problém přiřazení a jeho aplikace. Riceova věta.
5.11.	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.1. PÍSEMNÝ TEST
19.11.	Další NP-úplné problémy.
26.11.	Třída paměťové složitosti PSPACE a PSPACE-úplné problémy.2. PÍSEMNÝ TEST
3.12.	Třídy paměťové složitosti L a NL.
10.12.	dobrovolná hromadná konzultace; popřípadě rezerva, 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

Průběhu semestru se budou psát dvě zápočtévé písemky -- jedna z vyčíslitelnosti (12.11.) a jedna ze složitosti (26.11.). Každá po 100 bodech. Pro zápočet je nutné získat v součtu alespoň 100 bodů. V zápočtovém týdnu (10.12.) se bude psát opravná písemka, která bude pokrývat všechny přednášky a bude možné získat z ní maximálně 80 bodů. Tyto body budou nahrazovat body z hůře napsané písemky.

Požadavky na zkoušku

Zkouška probíhá na základě ústního zkoušení.

Výukové materiály

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)
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)

Výukové materiály (z předchozího roku)

25.9. Úvod do vyčíslitelnosti, Turingovy stroje (pdf)

25.9. Programovací techniky a varianty TS (pdf) -- slajdy nebyly použity při přednášce, slajdy nejsou dokončené, óbsahují překlepy a nedokončené pasáže. Tyto slajdy byly zveřejněny na žádost studentů.

20.11. Další NP-úplné problémy (pdf)

27.11. Paměťová složitost (pdf)

3.12. L a NL (pdf)