A+ | A- | Ø
 
  • English
 
 
2014. november 24. hétfő 16:03
A Bolyai Intézet által aktuálisan oktatott kurzusok

Vissza

A tárgy kódja és neveMMN042E 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
Heti óraszám
Típusaelőadás 
Számonkéréskollokvium 


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

  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.