DMI025 - Pravděpodobnostní algoritmy - Probraná témata
LS 2001 - Jiří Sgall
-
Třídy pravděpodobnostních algoritmů.
-
RP, BPP, ZPP, PP, RLOGSPACE vztahy k P, NP, PSPACE, polynomiálním obvodům
-
Základní nerovnosti používané při analýze pravděpodobnostních algoritmů.
-
Markov, Chernoff-Hoefding
-
Pravděpodobnostní algoritmy pro kombinatorické problémy.
-
MINCUT - jednoduchý alg., zlepšení iterativním procesem na čas O(n2
polylog n)
-
MAXCUT - jednoduchý 2-aproximační alg., derandomizace
-
paralelní algoritmus pro hledání maximální nezávislé množiny (maximální
vzhledem k inkluzi, tedy ne nutně největší)
-
Techniky pro omezení počtu náhodných bitů
-
po k nezávislé proměnné
-
definice, odhady na velikost pravděpodobnostních prostorů
-
konstrukce - lineární funkce, resp. polynomy, Sylvestrova matice
-
náhodné procházky na expanderech
-
Hashování
-
definice univerzálních systémů hashovacích funkcí, jejich konstrukce
-
dynamické hashování s průměrným konstantním časem vyhledávání.
-
statické hashování s nejhorším konstantním časem vyhledávání
-
Věty o minimaxu
-
von Neumann, Yao, vztah k teorii her
-
Vyhodnocování stromů pro hry (úplné binární AND-OR stromy)
-
deterministický dolní odhad 22k
-
pravděpodobnostní algoritmus 3k, dolní odhad 2.61k
-
Markovovy řetězce a náhodné procházky.
-
stacionární distribuce, její existence a konvergence, periodičnost
-
čas pokrytí grafu a dosažení daného vrcholu, odhady, příklady pro konkrétní
grafy
-
vztah k elektrickým obvodům
-
testování souvislosti grafů
-
Expandery
-
definice, konstrukce explicitní a pravděpodobnostní
-
vztah vlastních čísel a expanze
-
náhodné procházky na expanderech, rychlá konvergence, použití k derandomizaci
-
Náhodnost v on-line algoritmech
-
kompetitivní poměr
-
cachování s k stránkami rychlé paměti (pravděpodobnostně O(log k)
kompetitivní vs. k deterministicky), odpovídající dolní odhady
-
Číselně teoretické algoritmy
-
kvadratická rezidua a odmocniny
-
testování prvočíselnosti
-
kryptografie s veřejným klíčem (RSA, Rabinův systém)
Zkoušky
se konají v mé pracovně v Matematickém ústavu. Adresa je Žitná 25,
u křižovatky se Štěpánskou. Projdete průchodem, rovně přes dvůr do tzv.
zadní budovy (má modré rámy oken), ve 2. patře zazvoníte na dveře vpravo
(s cedulkou Matematický ústav).
Kontakt: sgall@math.cas.cz, 02/22090780