- Előadás helye: 3-517, ideje: kedd 12:14-13:45
Az előadás témáját leginkább ez az angol jegyzet közelíti meg. Új változat, 2007. jan. 3.
-
Hetenkénti téma
Szeptember 12
Felidéztünk két randomizált algoritmust: polinomazonosság tesztelését és a prímtesztelést. Ezzel motiváltuk azt, hogy a "véletlen sorozat" fogalmát definiálni kell. Bevezettük egy sorozat Kolmogorov-bonyolultságának a fogalmát. Ehhez felidéztük a Turing-gép és az univerzális Turing-gép fogalmát, és hozzátettük a (*) tulajdonságot (hogy a gép át tud másolni a programszalagr ól az adatszalagra). Bebizonyítottuk, hogy egy sorozat két különböző Turing-géppel definiált Kolmogorov-bonyolultságainak különbsége csak a gépektől függő konstanssal korlátozható, és hogy a Kolmogorov-bonyolultság nem algoritmikusan nem kiszámítható.
Szeptember 19
Algoritmust adtunk arra, hogy egy sorozat Kolmogorov-bonyolultságát véges várható értékű hibával kiszámítsuk. Definiáltuk a gyengén informatikusan véletlen sorozat fogalmát, és megmutattuk, hogy egy független 1/2 valószínűségű bitekből álló végtelen sorozat 1 valószínűséggel gyengén informatikusan véletlen.
Szeptember 26
Bebizonyítottuk, hogy minden gyengén informatikusan véletlen sorozat kielégíti a nagy számok törvényét. Bevezettük az álvéletlen-szám generátor fogalmát, először informálisan és klasszikus példákon, aztán formálisan.
Október 3
Átismételtük az álvéletlen-szám generátor fogalmát, két definíciót adva: biztonságosság és megjósolhatatlanság. Bebizonyítottuk Yao tételét, mely szerint a két fogalom ekvivalens.
Október 10
Bevezettük az egyirányú függvény és az egyirányú permutáció fogalmát. Diszkutáltuk a négyzetreemelést (mod m), mint egy lehetséges példát egyirányú függvényre. Bebizonyítottuk, hogy minden biztonságos véletlenszám-generátor egyirányú függvény, és vázoltam annak a bizonyítását, hogy ha van egyirányú permutáció, akkor van biztonságos véletlenszám-generátor (Goldreich-Levin Generátor).
Október 17
Döntési fák. Olyan algoritmusokat láttunk, melyek váza egy döntési fa: Keresés, sorbarakás, konvex burok. Ben-Or tételének vázlata.
Október 24
A döntési fa pontos fogalma. Nem-determinisztikus döntési fák és kapcsolatuk konjunktív és diszjunktív normálformával. Példák: gráftulajdonságok, izolált pont létezése. Alsó és felső becslés a determinisztikus döntési fa bonyolultságára a nemdeterminisztikus döntési fák bonyolultságának függvényében.
November 7
Zárkózott Boole formulák.
November 14
Zárthelyi.
November 21
Kommunikációs bonyolultság. Példák egy fordulós és több fordulós protokollokra. Mátrix reprezentáció, a protokoll leírása a mátrixon. Alsó korlát a mátrix rangja segítségével. Nem-determinisztikus kommunikációs bonyolultságok, kombinatorikus jelentésük a mátrixon, példák.
November 28
Determinisztikus és nem-determinisztikus kommun= ikációs bonyolultságok közötti egyenlőtlenségek. A kommunikációs P, NP, co-NP osztályok és kapcsolatuk. Randomizált protokoll az egyenlőség eldöntésére.
December 5
Interaktív bizonyítások: boríték, jelszó, 0 információjú bizonyítások (példa: gráfban van Hamilton kör), interaktív bizonyítás co-NP-re (polinom minden {0,1}^n-beli helyettesítése 0).
-
Házi feladat. (Csak gyakorló példák, nem kell beadni.)
-
A zárthelyi feladatainak megoldása