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

(Csima Judit, Ferenczi Miklós, 2018)
  1. A logikai programozás és gépi bizonyítás elméleti alapjai. Állítás-, alap- és elsőrendű 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, ezek kapcsolata.
  8. Nemdeterminisztikus Turing-gépek, tanú tétel. Az NP és coNP osztályok. NP-teljes nyelvek.