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
-
-
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/Karp-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
RP értelemben kiszámít egy nyelvet.
-
Milyen output esetén lehetünk biztosak, hogy helyes? Miért?
-
L nyelvbeli input esetén milyen valószínűséggel hibázhatunk? Indokolja, hogy a
különböző alternatívák miért vezetnek ugyanahhoz az osztályhoz.