Math courses taught by the Bolyai Institute

Back Course code and title MMN211E Algoritmusok és bonyolultságelmélet Responsible Department Department of Algebra and Number Theory  Responsible instructor Dr. Hajnal Péter  Credit 4  Contact lecture hours 2  Type lecture  Type of exam exam  Curriculum 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. Suggested literature 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.