- Előadás helye: D 1.105, ideje: kedd 10:15-11:45
Az előadás témáját leginkább ez az angol jegyzet közelíti meg.
-
Hetenkénti téma
Szeptember 11
Felidéztünk két randomizált algoritmust: polinomazonosság tesztelését és a prímtesztelést. 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 azt a tulajdonságot, hogy a gép át tud másolni a programszalagr ól az adatszalagra.
Szeptember 18
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ó. Algoritmust adtunk arra, hogy egy sorozat Kolmogorov-bonyolultságát véges várható értékű hibával kiszámítsuk.
Szeptember 25
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.
Október 2
Bebizonyítottuk, hogy minden gyengén informatikusan véletlen sorozat kielégíti a nagy számok törvényét. Megmutattuk a kapcsolatot az entropiaval. Röviden beszéltünk a prefix mentes Kolmogorv-bonyolultsagrol.Definialtuk a kod tomorseget, és egyszerű korlatokat adtunk rá.
Október 9
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, 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 16
Bevezettük az egyirányú függvény és az egyirányú permutáció fogalmát. Diszkutáltunk több 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 30
Döntési fák. Olyan algoritmusokat láttunk, melyek váza egy döntési fa: Keresés, sorbarakás, konvex burok.November 6
A döntési fa pontos fogalma. Egyszerű döntési fák. 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.November 13
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 20
Alsó becslések döntési fák mélységére. Zárkózott formulák, Ben-Or tétele.November 27
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.December 4
Determinisztikus és nem-determinisztikus kommuniká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.