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

(Friedl Katalin, Ferenczi Miklós)
  1. A logikai programozás és gépi bizonyítás elméleti alapjai. Állítás-, alap- és elsorendu illesztéses rezolúció. SLD rezolúció.
  2. Herbrand modellek és a korrekt válasz probléma.
  3. A SAT, HORNSAT probléma. Fagin tétel, pszi gráf probléma. Véges modellek és bonyolultság.
  4. Boole-algebrák, reláció algebrák és alkalmazásaik. Algebrai logika.


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