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 2020
• Semestr: zimní
• E-Kredity: 6
• Rozsah, examinace: zimní s.:3/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. Mgr. Michal Koucký, Ph.D.
• Vyučující: prof. Mgr. Michal Koucký, Ph.D.
• Třída: M Mgr. MMIB; M Mgr. MMIB > Povinné
• Kategorizace předmětu: Matematika > Algebra
• Je neslučitelnost pro: NMMB405
• Je záměnnost pro: NMMB405

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.

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

Literatura

čeština

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.

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

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

Poslední úprava: Koucký Michal, prof. Mgr., Ph.D. (28.09.2020)