| 19.9. | Úvod do vyčíslitelnosti, Turingův stroj. (studijní text) | |
| 26.9. | Varianty Turingova stroje, programovací techniky TS. Nedeterministický TS. Univerzální TS. (studijní text) | |
| 3.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ů. (studijní text) | |
| 10.10. | Vztah jazyků TS k jazykům Chomského hierarchie. | |
| 17.10. | Redukce problémů. Riceova věta. Postův problém přiřazení a jeho aplikace. | |
| 24.10. | Věta o rekurzi, věta o minimální reprezentaci. | |
| 31.10. | ZÁPOČTOVÝ PÍSEMNÝ TEST | |
| 7.11. | Časová a paměťová složitost, třídy složitostí, třídy P, NP. | |
| 14.11. | NP-úplné problémy. Cookova věta. Dokazování NP-úplnosti. | |
| 21.11. | Další NP-úplné problémy. | |
| 28.11. | Třída paměťové složitosti PSPACE a PSPACE-úplné problémy. Třídy paměťové složitosti L a NL. | |
| 5.12. | 1. OPRAVNÝ PÍSEMNÝ TEST dobrovolná hromadná konzultace; popřípadě rezerva, | |
| 12.12. | 2. OPRAVNÝ PÍSEMNÝ TEST |
Dne 5.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 12.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ě.