- Előadó: Lovász László
- Előadás helye: Déli Tömb 00.718, ideje: péntek 8:15-9:45
- Első előadás: szeptember 18.
Az előadás témáját leginkább ez az angol jegyzet közelíti meg.
Hetenkénti téma
Szeptember 12
Véletlent használó algoritmusok (rövid összefoglaló). Randomizált Turing gépek és az általuk definiált bonyolultsági osztályok: BPP,RP,Delta-RP,P és kapcsolatuk.Szeptember 19
Kolmogorov-bonyolultság definíciója és a géptől való függetlensége. A Kolmogorov-bonyolultság kiszámíthatatlansága, és kapcsolata a megállási problémával.Szeptember 26
Dékáni szünetOktóber 3
Informatikusan véletlen sorozat definíciója, nagy számok törvénye informatikusan véletlen sorozatra. Entrópia és információs bonyolultság. Példák: részhalmazok kódolása, fák Prüfer-kódja.Október 10
Álvéletlen sorozatok generálása. Klasszikus módszerek. Megbízhatóság és megjósolhatatlanság. Yao tétele.Október 17
Yao tételének bizonyítása. Egyirányú függvények és permutációk. Minden megbízható generátor egyirányú függvény. Egyirányú permutációból konstruálható álvéletlen generátor.Október 18
Kriptográfia elemei. Klasszikus módszerek, egyszer használható kulcsok. Egyszerű bonyolultságelméleti modellek: jelszó és boríték. Nyilvános kulcsú kriptográfia, RSA kód.November 7
Döntesi fák, barkochba, rendezés döntési fán, informacióelméleti alsó korlát döntési fa mélységére. Alkalmazás rendezésre. Nemkülönbözőségi probléma. A konvex burok keresésének problemája. Algebrai döntési fák, lineáris döntési fák. Általanosítás d-edfokú polinomokra, Milnor-Thom, Ben-Or tétel.November 14
Egyszerű döntési fák. Nemdeterminisztikus döntési bonyolultság, kapcsolata a determinisztikussal. Gráfproblémák és döntési fák. Az összefüggőség zárkózott. Paritási feltétel, izolált-pont-mentesség zárkózott.November 21
(Elmaradt, későbbi előadások során pótolva.)November 28
Zárkózott Boole-függvények. Polinom-feltétel. Minden szimmetrikus nem-konstans Boole-függvény zárkózott. Minden gyengén szimmetrikus monoton nem-konstans Boole-függvény zárkózott, ha a változók száma prím. Kommunkációs bonyolultság. Rang-feltétel. Példák: részfa diszjunktsága, teljes és üres részgráf diszjunktsága.December 5
Nem-determinisztikus kommunikációs bonyolultság, példa: konvex sokszögek diszjunktsága. Az Aho-Ullman-Yannakakis Tétel. P és NP kommunikációs bonyolultság esetén. Randomizált protokoll az egyenlőség eldöntésére. Interaktív bizonyítások: egyszerű példák, Hamilton-kör létezésének bizonyítása a kör megadása nélkül.December 12