Elméleti számítástudomány
      
(Csima Judit, Ferenczi Miklós, 2024)


  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. Lambda-kalkulus. Normálforma. Church-Rosser tétel és alkalmazása. A lambda kalkulus, mint programozási nyelv.


     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, zártsági tulajdonságaik.
     7.Nevezetes nyelvek és osztályuk: diagonális, univerzális és megállási nyelv, a semmit el nem fogadó Turing-gépek nyelve. Rice-tétel. PCP és Dominó nyelv.
     8.Idő- és tárkorlátos Turing-gépek, idő- és tárosztályok. Tár-idő tétel. A P, NP, coNP, PSPACE és EXPTIME osztályok, ezek kapcsolata egymással és az R osztállyal.