A+ | A- | Ø
 
  • Magyar
 
 
Thursday, 24 April 2014
Math courses taught by the Bolyai Institute

Back

Course code and titleMMN042E Kombinatorikus számítási modellek
Responsible DepartmentDepartment of Set Theory and Mathematical Logic 
Responsible instructorDr. Hajnal Péter 
Credit
Contact lecture hours
Typelecture 
Type of examexam 


Curriculum

: Döntési fák, tartózkodó függvények, alsó becslések. Kommunikációs bonyolultság, mátrix szeletelés, rang-becslés. Elágazó programok, korlátos szélességű programok. Formulák, Khrapcenko-módszer, monoton formulák, alsó becslések. Hálózatok, monoton hálózatok, Razborov-módszer.


Suggested literature

  1. Hajnal Péter, Halmazrendszerek, Polygon Jegyzettár, Szeged, 2002.
  2. Ingo Wegener, Complexity theory (Exploring the limits of efficient algorithms), Springer-Verlag, Berlin, 2005.