A+ | A- | Ø
 
  • Magyar
 
 
Tuesday, 30 September 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. 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.
  2. Fülöp Zoltán: Formális nyelvek és szintaktikus elemzésük, Polygon,1999.
  3. Gécseg Ferenc: Automaták és formális nyelvek, Polygon, 2005.
  4. C. H. Papadimitriou: Computational Complexity. Addison-Wesley, 1995; magyarul: Számítási bonyolultság (szerk.: Ésik Zoltán), Novadat, 1999.
  5. M. Sipser: Introduction to the Theory of Computation. PWS Publishing Company, 1997.