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

(Friedl Katalin, Simon András)
  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. Fixpontok a gráf-modellben

  8. Turing-gép és változatai (több szalagos, illetve nemdeterminisztikus), ezek ekvivalenciája. Church-Turing-tézis
  9. Rekurzív és rekurzívan felsorolható nyelvek. Az R, RE, coRE nyelvosztályok. Nevezetes nyelvek és osztályuk.
  10. 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.
  11. Nemdeterminisztikus Turing-gépek, tanú tétel. Az NP és coNP osztályok. NP-teljes nyelvek.
  12. 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.
  13. Adattömörítés: Huffman-kód és ennek optimalitása. A Lempel-Ziv-Welch tömörítő eljárás.