Algoritmusok és bonyolultságelmélet

VIZSGA, 2010 Tavasz

Akik ezt a részt olvassák valószínűleg már teljesítették a kurzus gyakorlati részét és (amennyiben vállalkoztak rá) jegyzetelésüket is beadták, kijavították. A kurzusról történő beszámolás hátralévő része egy írásos vizsga. Ennek maximális teljesítése 30 illetve 50 pontra lesz skálázva aszerint, hogy a hallgató vállalt-e jegyzetelést vagy nem.

Tematika

Alapfogalmak: Nyelv, számítási probléma. Turing-gép (eldöntő/kiszámító). Nem-determinisztikus Turing-gép, véletlen Turing-gép, alternáló Turing-gép. Ezek konfigurációja. Futás (determinisztikus eset), futások fája (nemdeterminisztikus, véletlen, alternáló eset). Nemtereminisztikus/véletlen Turing-gép által eldöntött nyelv. Futás idő/tár-igénye. Legrosszabb-eset-analízis: TIME(t(n)), NTIME(t(n)), SPACE(t(n)), NSPACE(t(n)). Redukciók/visszavezetések: eredeti (Cook), Turing. Teljes probléma egy nyelvosztályra és egy visszavezetési algoritmusosztályra. Orákulumos Turing-gép. Hálózat.

Bonyolultsági osztályok definíciói: P, NP, coNP, L, NL, coNL, PSPACE, NPSPACE, coNPSPACE, Σ_iP, Π_iP, PH, BPP, RP, coRP, ZPP, #P, MajP, ParityP. Ezek ismert viszonyai.

Tételek: PALINDROM nyelv felismerése input=munkaszalag modellben. MEGÁLLÁS kiszámíthatatlansága. ELÉRHETŐSÉG nyelv NL-teljes. HÁLÓZAT-KIÉRTÉKELÉS nyelv P-teljes. HÁlÓZAT-KIELÉGÍTHETŐSÉG nyelv NP-teljes. NP-teljesség redukciókkal: SAT, 3-SAT, egy szabadon választott gráfelméleti probléma, egy szabadon választott halmazrendszeres probléma, egy szabadon választott egyéb probléma. Immerman-Szelepcsényi-tétel. NemuniformP jellemzései. Karp-Lipton-tétel. Gács-Sipser tétel, BPP és a nemuniformP viszonya. 0-1 mátrixok permanenesének kiszámítása #P-teljes.

Algoritmusok: ELÉRHETŐSÉG eldöntése log-négyzet tárban. "Ritka" k-CNF kielégítő kiértékelésének megtalálása.

Mintavizsga

- Definiálja a nemdeterminisztikus Turing-gépet, az általa elfogadott nyelvet.
- Definiálja az NP nyelvosztályt.
- Adjon példát NP-beli nyelvre. Állítását indokolja is. (Példájának értéke függ attól, hogy mennyire jellemző NP-re.)
- Adjon példát olyan nyelvre, amiről azt hisszük, hogy nem NP-beli. Miért hisszük ezt? (Mi történne, ha az ön által megadott nyelv NP-be esne.)
- Definiálja a hálózat fogalmát.
- Vázolja, hogy egy Turing-gép konfigurációját hogyan kódolná bitsorozattal.
- Vázoljon egy hálózatot, amely egy Turing-gép konfigurációjából kiszámolja a rákövetkező konfirgurációját.
- Ajon meg egy P-teljes nyelvet. Miért lesz ez P-teljes?
- Definiálja a véletlen Turing-gépet, és azt, hogy mikor mondjuk, hogy BP értelemben kiszámít egy nyelvet.
- Definiálja a BPP nyelvosztályt.
- Milyen bővebbnek hitt nyelvosztály része BPP? Állítását indokolja. (Az ön által adott felsó becslés értéke függ attól milyen nagy nyelvosztályt mond.)

Egy második minta a vizsgára

- Definiálja a nemdeterminisztikus Turing-gépet, az általa elfogadott nyelvet.
- Definiálja az NL nyelvosztályt.
- Adjon példát NL-beli nyelvre. Állítását indokolja is. (Példájának értéke függ attól, hogy mennyire jellemző NL-re.)
- Adjon példát olyan nyelvre, amiről azt hisszük, hogy nem NL-beli. Miért hisszük ezt? (Mi történne, ha az ön által megadott nyelv NL-be esne.)
- Definiálja az eredeti/Cook-redukció és a Turing-redukció lényegét.
- Adjon meg teljes problémát a következő osztályokra (ismertesse milyen redukciót használtunk): NL,P, NP.
- NP esetén adjon meg második példát is és valamilyen irányba mutassa meg a visszavevzethetőséget.
- Definiálja a véletlen Turing-gépet, és azt, hogy mikor mondjuk, hogy ZP értelemben kiszámít egy nyelvet.
- Definiálja a ZPP nyelvosztályt.
- Írjon le egy problémát (lehet kiszámi;to is), ami ZP értelemben polinom idő alatt kiszámítható/eldönthető. Ismertesse egy ezt igazoló algoritmust is.