Elméleti számítástudomány

(Simon András, Katona Gyula Y., 2016)
  1. A Church-Rosser tétel és következményei
  2. Programozás a lambda-kalkulusban
  3. Rekurzió és fixpont-kombinátor
  4. Folytonos függvények cpo-kon
  5. Reflexív cpo-k
  6. A gráf-modell

  7. Turing-gép és változatai (több szalagos, illetve nemdeterminisztikus), ezek ekvivalenciája. Church-Turing-tézis
  8. Rekurzív és rekurzívan felsorolható nyelvek. Az R, RE, coRE nyelvosztályok. Nevezetes nyelvek és osztályuk.
  9. Id- és tárkorlátos Turing-gépek, id- és tárosztályok. Tár-id tétel. A P, PSPACE és EXPTIME osztályok.
  10. Nemdeterminisztikus Turing-gépek, tanú tétel. Az NP és coNP osztályok. NP-teljes nyelvek.
  11. Kolmogorov-bonyolultság adott Turing-gépre és általában. Invariancia-tétel. Összenyomhatatlan szavak. A Kolmogorov-bonyolultság, mint függvény bonyolultsága.