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).

A zárthelyi feladatainak megoldása