A+ | A- | Ø
 
  • Magyar
 
 
Friday, 22 August 2014
Math courses taught by the Bolyai Institute

Back

Course code and titleMMN211E Algoritmusok és bonyolultságelmélet
Responsible DepartmentDepartment of Algebra and Number Theory 
Responsible instructorDr. Hajnal Péter 
Credit
Contact lecture hours
Typelecture 
Type of examexam 


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

  1. C. H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995, Magyarul: Számítási bonyolultság (szerk.: Ésik Zoltán), Novadat, Győr, 1999.
  2. 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.
  3. Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük. Polygon, Szeged, 1999.
  4. Gécseg Ferenc: Automaták és formmális nyelvek. Polygon, Szeged, 2005.
  5. M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.