A tantárgy az alábbi témakörök ismeretére épít:
Algebra, lineáris algebra.
A tantárgy szerepe a képzés céljának megvalósításában:
TTK Matematikus és Alkalmazott matematikus MSc képzések kötelezően választható törzstárgya
A tantárgy részletes tematikája magyarul és angolul:
A logikai programozás és gépi bizonyítás elméleti alapjai. Véges modellek és bonyolultság. Nem-klasszikus logikák a számítástudományban: temporális, dinamikus, program logikák.
Rekurzív függvények és a lambda-kalkulus kapcsolata. Boole-algebrák, reláció algebrák és alkalmazásaik. Fontosabb gépmodellek. Bonyolultságelméleti alapfogalmak, nevezetes idő és tárosztályok.
NP-teljesség. Randomizált számítások. Algoritmustervezési módszerek. Fejlett adatszerkezetek, amortizációs elemzés. Mintaillesztés szövegben. Adattömörítés.
Követelmények szorgalmi időszakban:
Házi feladok elkészítése. Szóbeli beszámoló
Pótlási lehetőségek:
A TVSz előírásai szerint.
Konzultációs lehetőségek:
Jegyzet, tankönyv, felhasználható irodalom:
Carmen, T.H., Leiserson, C.E., Rivest: Algoritmusok, Műszaki Kiadó, 1999.
Rónyai L., Ivanyos G., Szabó R.: Algoritmusok, Typotex, 2001.; Ferenczi M.: Matematikai Logika, Műszaki Kiadó, 2002.
Galton, A.: Logic for Information Technology, Wiley, 1990.
Nyomtatóbarát változat
