Sylabus
Sylabus
1. Výpočetní modely: počítač, Turingův stroj, Booleovský obvod
2. Nerozhodnutelné problémy, problém zastavení
3. Časová složitost, třída P
4. Třída NP, NP-úplnost, Cook-Levinova věta, nedeterministické výpočty
5. Prostorová složitost, PSPACE, QBF, Polynomiální hierarchie
6. L, NL, Savičova věta, NL=coNL
7. Věty o hierarchii, zjemnělá složitost
8. Konečné automaty, regulární jazyky Webová stránka přednášky: https://iuuk.mff.cuni.cz/~koucky/vyuka/AVS-ZS2020/index.html
Anotace
Množiny charakterizované výpočetními modely.
Turingovy stroje, rekursivní a rekursivně vyčíslitelné jazyky.
Časová a prostorová složitost, základní deterministické složitostní třídy
(L,NL,P,NP,PSPACE). NP-úplnost.
Konečné automaty, regulární jazyky a jejich algebraická interpretace.