Számítástudomány (tematika)
- Az előadás főbb témaköreinek ismertetése: formális nyelvek, kiszámíthatóság elmélet, bonyolultságelmélet (bevezetés, motiváció, gyakorlati vonatkozások).
- Formális nyelvek, műveletek nyelveken. Véges automaták, felismerhető nyelvek, a felismerhető nyelvek zártsági tulajdonságai. Reguláris nyelvek - reguláris kifejezések.
- UNIX reguláris kifejezések. Nemdeterminisztikus véges automata, determinizálás, minimalizálás (Brzozowski algoritmusa).
- Kleene tétele. A felismerhető nyelvek pumpáló lemmája. Mealy automaták.
- Környezetfüggetlen nyelvtanok, derivációs fák. Egyértelműség, zártsági tulajdonságok. A környezetfüggetlen nyelvek pumpáló lemmája.
- A környezetfüggetlen nyelvtanok átalakításai. A Chomsky normálforma és a CYK algoritmus.
- Veremautomaták, determinisztikus veremautomaták. A veremautomaták és a környezetfüggetlen nyelvtanok ekvivalenciája. Top-down elemzés, LL(1) elemzők.
- Általános, környezetfüggő, és jobblineáris nyelvtanok. A Chomsky hierarchia. A kiszámíthatóság elmélet története és alapjai. A Church-Turing tézis. A Turing-gép, a Turing-felismerhető/rekurzívan felsorolható és eldönthető/rekurzív nyelvek.
- Aszimptotikus jelölések. A többszalagos és a nemdeterminisztikus Turing-gép. A Turing-gépek időigénye. Eldöntési probléma, mint formális nyelv. Az L_u és L_átló nyelvek. Az L_átló nem Turing-felismerhető.
- L_u eldönthetetlen, de Turing-felismerhető. A visszavezetések fogalma. A Turing-gépek megállási problémája. Rice tétele. A PMP (dominó) probléma. Bonyolultságelmélet:P, NP, Polinom időben verifikálhatóság.
- Az NP szerkezete, a coNP osztály. Tárbonyolultság: a PSPACE és NPSPACE osztályok. Savitch tétele és következménye. PSPACE-teljesség, QBF és Földrajzi játék. Logaritmikus tárbonyolultság: L és NL. NL-teljesség: az Elérhetőség probléma. Az Immerman-Szelepcsényi tétel: NL=coNL.