A Bolyai Intézet által aktuálisan oktatott kurzusok

Vissza A tárgy kódja és neve MMN042E Kombinatorikus számítási modellek Meghirdető tanszék(csoport) Halmazelmélet és Matematikai Logika Tanszék  Felelős oktató Dr. Hajnal Péter  Kredit 3  Heti óraszám 2  Típusa előadás  Számonkérés kollokvium  Tematika : 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. Ajánlott irodalom Hajnal Péter, Halmazrendszerek, Polygon Jegyzettár, Szeged, 2002. Ingo Wegener, Complexity theory (Exploring the limits of efficient algorithms), Springer-Verlag, Berlin, 2005.