Algoritmusok és bonyolultságelmélet

VIZSGA, 2015 Tavasz


Akik ezt a részt olvassák valószínűleg már teljesítették a kurzus gyakorlati részét. A vizsga maximális 50 pontra lesz skálázva.

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

Amennyiben egyéb teendőim megengedik (például nincs záróvizsga, nem kell Pestre utaznom, nincs ünnep) a vizsga előtti szerda 10-től a szobámban elérhető leszek konzultációra.

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 eset). Nem-determinisztikus 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(s(n)), NSPACE(s(n)). Redukciók/visszavezetések: Karp, Turing. Teljes probléma egy nyelvosztályra és egy visszavezetési algoritmusosztályra. Véletlen számokat használó Turing-gép és az általa eldöntött nyelv. 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, Pnem-uniform. Ezek ismert viszonyai.

Tételek: PALINDROM nyelv felismerése input=munkaszalag modellben, alsó/felső becslés az időre. MEGÁLLÁS kiszámíthatatlansága. ELÉRHETŐSÉG nyelv NL-teljes. Immerman-Szelepcsényi-tétel. 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. QBF PSPACE-teljes. Karp-Lipton-tétel. Gács-Sipser tétel, BPP és a Pnemuniform viszonya.

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

Egy második minta a vizsgára