PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
Automaty a výpočetní složitost - NMMB415
Anglický název: Automata and Computational Complexity
Zajišťuje: Katedra algebry (32-KA)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019 do 2019
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:3/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: nevyučován
Jazyk výuky: angličtina
Způsob výuky: prezenční
Garant: doc. Mgr. Štěpán Holub, Ph.D.
Anotace
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (13.12.2018)
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.
Literatura -
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (13.12.2018)

Papadimitriou, Christos H.: Computational Complexity, Addison-Wesley 1994.

Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich: Discrete Algebraic Methods, Walter de Gruyther 2016.

Sakarovitch, Jacques: Elements of automata theory, Cambridge University Press 2009.

Sipser, Michael: Introduction to the Theory of Computation, PWS Publishing Company 1997

Shallit, Jeffrey: A second Course in Formal Languages and Automata Theory, Cambridge University Press 2009.

Sylabus
Poslední úprava: doc. Mgr. et Mgr. Jan Žemlička, Ph.D. (13.12.2018)

1. Turingovy stroje. Determinismus a nedeterminismus. Rekursivní jazyky.

2. Halting problem a nerozhodnutelné jazyky

3. Časová a prostorová složitost. Asymptotické třídy funkcí.

4. Savitchova věta. Třídy L a NL.

5. Třídy P a NP.

6. NP-úplnost. Cook-Levinova věta.

7. Racionální a rozpoznatelné podmnožiny monoidů.

8. Determinisitické a nedeterministické konečné automaty.

9. Kleeneova věta.

 
Univerzita Karlova | Informační systém UK