A+ | A- | Ø
 
  • English
 
 
2014. augusztus 29. péntek 01:19
A Bolyai Intézet által aktuálisan oktatott kurzusok

Vissza

A tárgy kódja és neveMMN211E Algoritmusok és bonyolultságelmélet
Meghirdető tanszék(csoport)Algebra és Számelmélet Tanszék 
Felelős oktatóDr. Hajnal Péter 
Kredit
Heti óraszám
Típusaelőadás 
Számonkéréskollokvium 


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

  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.