Tárgy neve: Kombinatorikus számítási modellek (MSc 2017-2025)

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őadás kódja: MMNM53E, óraszám: 2, kredit: 3