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