1)

• Definiálja mit értünk egy algoritmus legrosszabb eset analízisén.
• Definiálja milyen típusú feladatokra szolgáló algoritmusok esetén beszélhetünk amortizált analízisről. Mit jelent ez a fogalom?
• Ajon konkrét példát, ahol az amortizált analízis használható.
• Írjon le egy algoritmust a példájára és analizálja a legrosszabb eset analízissel és amortizáltan is.

1)'

• Definiálja a hálózat fogalmát. Mit értünk a hálózatra vonatkozó folyam problémán? Definiálja a probléma megértéséhez szükséges további fogalmakat.
• Írja le a Ford-Fulkerson-algoritmust.
• Az algoritmus keresési részének implementációját vázolja.
• Mi a Edmonds-Karp-algoritmus lényeges újdonsága?
• A fenti újdonság miért javítja meg a az algoritmus futási idejét?

1)''

• Mikor mondjuk a természetes számok egy $R$ részhalmazát bizonyíthatónak?
• Igazolja, hogy a hatványszámok halmaza bizonyítható.
• Igazolja, hogy a prímszámok halmaza bizonyítható. (Pratt tétele)
• Mikor mondjuk a természetes számok egy $R$ részhalmazát tesztelhetőnek?
• Igazolja, hogy a hatványszámok halmaza tesztelhető.

2)

• Definiálja hogyan kell módosítani a Turing-gép standard modelljét, a nem-determinisztrikus Turing-gép fogalmáhzo.
• Definiálja, mikor mondjuk, hogy egy nem-determinisztikus Turing-gép eldönt egy L nyelvet?
• Definiálja az NL és NP nyelvosztályokat.
• Adjon példát két NP-teljes nyelvre és adjon meg köztük egy redukciót. Egyikről mutassa meg, hogy NP-beli.

2)'

• Definiálja a Turing-gép standard modelljét számítási és eldöntési feladatok esetén is.
• Mikor mondjuk, hogy egy nyelv eldönthető, mikor hogy felsorolható.
• Igazolja, hogy van nem felsorolható nyelv.
• Definiálja az univerzális Turing-gépet.
• Írja le a MEGÁLLÁS nyelvet.
• Igazolja, hogy MEGÁLLÁS nem eldönthető.
• MEGÁLLÁS felsorolható-e? Indokolja válaszát.

2)''

• Definiálja két nyelv közötti redukció fogalmát.
• Definiálja absztrakt módon a teljes nyelv fogalmát.
• Definiálja specifikusan az NL-teljes és NP-teljes nyelv fogalmát.
• Adjon példát NL-teljes, P_teljes és NP-teljes nyelvre.
• Igazolja, hogy a log-tár redukció tranzitív.

2)'''

• Definiálja hogyan kell módosítani a Turing-gép standard modelljét, a véletlen számokat használó Turing-gép fogalmához.
• Definiálja az RP és co-RP nyelvosztályokat.
• Definiálja a BPP nyelvosztályt.
• Írja fel mi a fenti osztályok viszonya P, NP, co-NP és PSPACE nyelvosztályokhoz.
• A fenti definiácíjában (RP/BPP) szerepel egy hibázási valószínűség. Hogyan változtatható ez, hogy a megfelelő osztály ne változzon. Az egyik esetben igazolja is, hogy a hibázási valószínűség megnövelése nem szűkíti az osztályt. A másik esetben is vázolja azt a Turing-gépet, ami a hasnoló állítást igazolja.