Math courses taught by the Bolyai Institute

Back Course code and title MMN042E Kombinatorikus számítási modellek Responsible Department Department of Set Theory and Mathematical Logic  Responsible instructor Dr. Hajnal Péter  Credit 3  Contact lecture hours 2  Type lecture  Type of exam exam  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 Hajnal Péter, Halmazrendszerek, Polygon Jegyzettár, Szeged, 2002. Ingo Wegener, Complexity theory (Exploring the limits of efficient algorithms), Springer-Verlag, Berlin, 2005.