A Bolyai Intézet által aktuálisan oktatott kurzusok

Vissza A tárgy kódja és neve MMN211E Algoritmusok és bonyolultságelmélet Meghirdető tanszék(csoport) Algebra és Számelmélet Tanszék  Felelős oktató Dr. Hajnal Péter  Kredit 4  Heti óraszám 2  Típusa előadás  Számonkérés kollokvium  Tematika Véges automaták és formális nyelvek. Kiszámíthatósági modellek: rekurzív függvények, Turing-gépek. NP-teljesség, Cook-tétel és néhány nevezetes NP-teljes probléma. Approximációs algoritmusok és az ezekhez kapcsolódó bonyolultsági osztályok. A poliéder-módszer gráfelméleti alkalmazásai. On-line algoritmusok. Ajánlott irodalom C. H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995, Magyarul: Számítási bonyolultság (szerk.: Ésik Zoltán), Novadat, Győr, 1999. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. The MIT Press/McGraw-Hill, Cambridge/New York, 2001. Magyarul: Új algoritmusok (szerkesztő: Iványi Antal). Scolar, Budapest, 2003. Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük. Polygon, Szeged, 1999. Gécseg Ferenc: Automaták és formmális nyelvek. Polygon, Szeged, 2005. M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.