Az előadásokban vannak érdekességek is. A vizsgához csak az alábbi kérdések megválaszolásához szükséges ismeretek kellenek.

1. • Ismertesse a mohó algoritmus tervezési elvet. Adjon rá példát: Ismertessen egy optimalizálási feladatot (mi az input, mit kell kiszámolnunk) és ennek egy mohó megoldását. [Az előadáson ismertetett algoritmusokból választhat.] Garantálja-e az algoritmus outputjának optimalitását? Ha nem, akor milyen garancia adható az output jóságára? A garanciáról szóló állításait igazolja.
   • Definiálja a (Karp-)redukció fogalmát. Definiálja a NP-teljesség definícióját. Definiálja a Boole-hálózat fogalmát- Definiálja a HÁLÓZAT-SAT nyelvet. Definiálja a SAT nyelvet. Igazolja, hogy HÁLÓZAT-SAT < SAT.
2. • Ismertesse a szalámi taktika algoritmus tervezési elvet. Ismertesse a bináris keresés alapkérdését (mi az input, mit kell kiszámolnunk). Mi a bináris keresés algoritmusa? Elemezze az algoritmust.
   • Definiálja a PALINDROM nyelvet. Mi az ezáltal a nyelv által leírt döntési probláma. Vázoljon egy ezt megoldó Turing-gépet. Pontosan írja le melyik modellt használja.
3. • Ismertesse a szalámi taktika algoritmus tervezési elvet. Ismertesse a medián keresés alapkérdését (mi az input, mit kell kiszámolnunk). Hogyan általánosítottuk ezt a feladatot? Adjon rá algoritmust. Elemezze az algoritmust.
   • Definiálja a (Karp-)redukció fogalmát. Definiálja a NP-teljesség definícióját. Definiáljon két nyelvet: A, B. Írjon el köztük egy nem-triviális redukciót: A < B. Tudjuk, hogy A NP-teljes. Mire következtethetünk?
4. • Ismertesse az oszd meg és uralkodj algoritmus tervezési elvet. Ismertesse a rendezés alapkérdését (mi az input, mit kell kiszámolnunk). Adjon rá algoritmust. Elemezze az algoritmust.
   • Mit értünk egy T nem-determinisztikus Turing-gép időigényén egy adott input esetén? Mit értünk egy T nem-determinisztikus Turing-gép tárigényén egy adott input esetén? Hogyan lesznek ebből bonyolultsági osztályok? Definiálja az NL, NP, NPSPACE, NEXP, coNL, coNP, coNPSPACE, coNEXP osztályokat.
5. • Ismertesse az oszd meg és uralkodj algoritmus tervezési elvet. Ismertesse a szorzás alapkérdését (mi az input, mit kell kiszámolnunk). Ismertesse Karacuba algoritmusát. Elemezze az algoritmust.
   • Definiálja a Karp-redukció fogalmát. Definiálja a NP-teljesség definícióját. Definiálja a Boole-hálózat fogalmát- Definiálja a HÁLÓZAT-SAT nyelvet. Igazolja, hogy a HÁLÓZAT-SAT NP-teljes.
6. • Ismertesse a dinamikus programozási algoritmus tervezési elvet. Ismertessen egy problémát, ahol ez az elv alkalmazható (mi az input, mit kell kiszámolnunk). Ismertessen egy dinamikus programozási algoritmust erre a problémára. Elemezze az algoritmust.
   • Definiálja a (Karp-)redukció fogalmát. Definiálja a P-teljesség definícióját. Definiálja a Boole-hálózat fogalmát- Definiálja a HÁLÓZAT-KIÉRTÉKELÉS nyelvet. Igazolja, hogy a HÁLÓZAT-KIÉRTÉKELÉS P-teljes.
7. • Definiálja a folyam problémát (mi az input, mit kell kiszámolnunk). Definiálja a javító út fogalmát. Írja le az erre alapuló javítgatásos algoritmus sémáját. Ford és Fulkerson hogyan keresett javító utat?
   • Definiálja a (Karp-)redukció fogalmát. Definiálja az NL-teljesség definícióját. Igazolja, hogy az IRÁNYÍTOTT-ELÉRHETŐSÉG NL-teljes. Mi következik ebből?
8. • Definiálja a folyam problémát (mi az input, mit kell kiszámolnunk). Definiálja a javító út fogalmát. Írja le az erre alapuló javítgatásos algoritmus sémáját. Edmonds és Karp hogyan keresett javító utat? Mondja ki az erre vonatkozó tételt.
   • Definiálja a (Karp-)redukció fogalmát. Adjon egyszerű példákat. Definiálja a teljesség fogalmát. Definiálja az NL-teljes, P-teljes és NP-teljes nyelv fogalmát.
9. • Ciklizálhat-e a Ford-Fulkerson-algoritmus ha az inputbeli számok racionálisak? Ciklizálhat-e a Ford-Fulkerson-algoritmus ha az inputbeli számok pontos valós aritmetikával kezeltek? Mit mondhatunk a folyam problémáról, ha az inputbeli számok egészek? Indokolja válaszait.
   • Definiálja az IRÁNYÍTOTT-ELÉRHETŐSÉG nyelvet/problémát. Mondjon valamit a bonyolultságáról? Több választ is adjon. Vázolja Savitch algoritmusát.
10. • Milyen problémák esetén beszélhetünk amortizált analízisről? Mit értünk alatta? Ismertesse a bináris számláló problémáját. Elemezze amortizációs analízissel. Mit értünk bankár szemlélet alatt? Mit értünk fizikus szemlélet alatt?
    • Definiálja az univerzális Turing-gép fogalmát. Definiálja a MEGÁLLÁS nyelvet. Definiálja az eldönthető nyelvek osztályát. Definiálja a felsorolható nyelvek osztályát. Igazolja, hogy MEGÁLLÁS nem eldönthető.
11. • Definiálja a min-kupac-fa és max-kupac-fa fogalmát. Hogyan ábrázolhatjuk ezt, ha az alap gyökeres fa bináris? Hogyan ábrázolhatjuk ezt, ha az alap gyökeres fa fokai nem korlátosak? Definiálja a Fibonacci-kupac fogalmát. Milyen "szolgáltatásokat" lát el egy Fibonacci-kupac?
    • Definiálja a (Karp-)redukció fogalmát. Igazolja, hogy a polinomiális és logtár redukálhatóság is tranzitív fogalom.
12. • Definiálja a Fibonacci-kupac fogalmát. Milyen "szolgáltatásokat" lát el egy Fibonacci-kupac? Hogyan implementáltuk Kulcs-Cökkent(v, delta) szolgáltatást?
    • Ismertesse a Turing-gép fogalmát (munka-ábécé, állapothalmaz, átmeneti-függvény, konfiguráció, konfiguráció-update, futás). Mikor mondjuk, hogy T Turing-gép kiszámol egy f számítási problémát? Hogy módosul a fogalom, ha döntési problémákat kezelünk?
13. • Definiálja a Fibonacci-kupac fogalmát. Milyen "szolgáltatásokat" lát el egy Fibonacci-kupac? Hogyan implementáltuk Min-Töröl szolgáltatást?
    • Mit értünk egy T Turing-gép időigényén egy adott input esetén? Mit értünk egy T Turing-gép tárigényén egy adott input esetén? Hogyan lesznek ebből bonyolultsági osztályok? Definiálja az L, P, PSPACE, EXP osztályokat.
14. • Szöveg = karaktersorozat. Mit értünk karakter alapú kódoláson. Emlékszik-e az ASCII kódolás paramétereire? Milyen hosszú (hány bites) egy n karakterből álló szöveg ASCII kódja? Mit értünk prefix kódoláson? Írja le a Huffman-algoritmust. Milyen algoritmus tervezési elvet követ az algoritmus?
    • Mik az L, NL, P, NP, PSPACE, NPSPACE, EXP, NEXP osztályok tartalmazási viszonyai? Igazolja válaszait.
15. • Szöveg = karaktersorozat. Mit értünk karakter alapú kódoláson. Emlékszik-e az ASCII kódolás paramétereire? Milyen hosszú (hány bites) egy n karakterből álló szöveg ASCII kódja? Mit értünk szótár alapú kódoláson? Írja le a Lempel-Ziv-Welsh-algoritmust.
    • Ismertesse a nem-determinisztikus Turing-gép fogalmát. Az előadáson ismertetett mindkét változatot írja le.