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 T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. The MIT Press/McGraw-Hill, 2001; magyarul: Új algoritmusok (szerk.: Iványi Antal), Scolar, 2003. Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Polygon,1999. Gécseg Ferenc: Automaták és formális nyelvek, Polygon, 2005. C. H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995; magyarul: Számítási bonyolultság (szerk.: Ésik Zoltán), Novadat, 1999. M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.