A vizsga "100-(évközben elért pontszám)"-ra lesz skálázva. Jegy az év eleji szabályok szerint.

A vizsganapjaim az ETR-en elérhetők.

Amennyiben egyéb teendőim megengedik (például nincs záróvizsga) a vizsga előtti szerda 11-től a szobámban elérhető leszek konzultációra.

Modellek és hozzá tartozó bonyolultsági mértékek: Döntési fák (determinisztikus, nem-determinisztikus, véletlen). Kommunikációs protokolok (determinisztikus, nem-determinisztikus, véletlen). Elágazó programok. Permutációs elágazó programok. Formulák. Hálózatok. Adott mélységű halózatok.

Algoritmusok: Döntési fák: Triviális algoritmus, összefüggőség, izolált pont létezése, irányított gráfokra nyelő létezése (véletlen algoritmussal). Kommunikációs protokolok: Triviális algoritmus, egyenlőség tesztelése (determinisztikus, véletlen), egy fában két részfa közös pontjának létezése, Két V-n adott gráf uniójának összefüggősége. Elágazó programok: Permutációs programok rekurziói. Formulák: Triviális formula, monoton formula, paritás (kétféle bázisban is). Hálózatok: Többség függvény, mod m (O(log n) mélységű hálózatokkal való kiszámolása).

Tételek: Döntési fa bonyolultság és stratégiák. Nem-determinisztikus és determinisztikus bonyolultság kapcsolata: döntési fák és kommunikációs bonyolultság. Véletlen Boole-függvény döntési fa bonyolultsága. Rang becslés a kommunikáció bonyolultságra. Neciporuk-tétel. Barrington-tétel. Alsó becslés nem explicit függvény formula bonyolultságára. Khrapcenko-tétel.

A vizsgán az alábbi típusú kérdésekből szerepel kettő.

1. • Definiáljuk a döntési fát, az általa kiszámolt Boole-függvényt. Definiáljuk egy Boole-függvény döntési fa bonyolultságát. Definiáljuk mikor mondjuk, hogy zárkózott egy Boole-függvény.
   • Fogalmazzuk meg egy függvény zárkózottságát mint egy kérdező-válaszoló játékra vonatkozó állítás. Adjunk startégiát a válaszoló játékos számára, ami bizonyítja az összefüggőség zárkózottságát.
   • Igazoljuk, hogy a fenti stratégia kényszeríti a kérdezőt az összes kérdés feltevésére.
2. • Definiáljuk a kommunikációs protokol fogalmát és egy f(x₁,...,x_n,y₁,...,y_n) Boole-függvény komunikációs bonyolultságát.
   • Adjunk kommunikációs protokolt arra a függvényre, ami egy fa két részfájáról dönti el, hogy van-e közös csúcsuk. Mi a bonyolultsága?
   • Mit tud mondani egy függvény kommunikációs bonyolultságáról, ha mindkét fajta nem-determinisztikus bonyolultságára van felső becslése? Igazolja állítását.
3. • Definiálja az elágazó program fogalmát, és az erre alapuló Boole-függvények bonyolultságát. Mikor mondjuk, hogy egy elágazó program szintezett? Mi egy szintezett program szélessége?
   • Adjunk meg szintezett elágazó programok egy sorozatát (minden inputmérethez tartozzon program), ami a (mod 4) függvényt számolja ki (a függvény pontosan akkor 1, ha az inputban lévő egyesek száma néggyel osztható). Konstrukciónk olyan legyen, hogy a sorozatban a szélesség korlátos legyen.
   • Mondjuk ki Barrington tételét. A szükséges alapfogalmakat is definiáljuk.
4. • Definiáljuk a formula fogalmát és egy Boole-függvény formula bonyolultságát.
   • Egy tetszőleges monoton Boole-függvényre adjon meg egy {Λ,V} bázisú formulát, ami a függvényt számolja ki.
   • Igazolja, hogy van olyan n változós Boole-függvény, ami nem számolható ki polinomiális méretű formulával.
5. • Definiáljuk a formula fogalmát és egy Boole-függvény formula bonyolultságát.
   • A paritás függvényre adjon meg de Morgan bázisú formulát és egy olyat, ami kizáró vagy kaput is használ.
   • Mondja ki és igazolja a Khrapcenko-tételt.
6. • Milyen függvényeknek van kommunikációs bonyolultsága? Hogyan azonosítottuk az ilyen függvényeket mátrixokkal? Fogalmazza meg a függvények determinisztikus és kétféle nem determinisztikus bonyolultságát a függvényt leíró mátrix segítsegével.
   • Az egység mátrix 1-eseit fedjuk le homogén téglalapokkal, az egység mátrix 0-sait fedjuk le homogén téglalapokkal. A két esetben mi a fedő téglalapok minimális száma?
   • Mi a köze egy Boole-függvényt leíró mátrix rangjának a kommunikációs bonyolultságához. Igazolja állítását.