Kombinatorikus számítási modellek (MSc)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
Döntési fák, zárkózott függvények, alsó becslések. Kommunikációs bonyolultság, mátrixok parkettázása és a rang alsó becslés. Elágazó programok, korlátos szélesség és Barrington tétele. Formulák Khrapchenko és Subbotovszkaja tételei, monotonitás és alsó becslések. Hálózatok, monotonitás és Razborov tétele. Switching lemma. Smolensky tétele.

Előfeltétel: nincs.

Helyettesítő tárgyak: nincsenek.

Előadás:
Kurzuskód: MMNM53E Kredit: 3 Óraszám: 2 hetente