I387/M734 - Pravděpodobnostní algoritmy - Probraná témata
LS 1999 - Jiří Sgall
-
Třídy pravděpodobnostních algoritmů.
-
RP, BPP, ZPP, PP, RLOGSPACE vztahy k P, NP, PSPACE, polynomiálním obvodům
-
aproximační alg., aproximace v průměru vs. s velkou pravděp., (F)PRAS,
vztah k #P
-
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
-
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
-
Přibližné počítání
-
odhady pomocí náhodných vzorků z většího univerza (tzv. Monte-Carlo)
-
generování přibližně náhodných vzorků pomocí náhodných procházek
-
iterované použití pro výpočet permanentu hustých 0-1 matic
-
konduktance, metoda kanonických cest pro permanent
-
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)
-
rozvrhování, dva modely: v reálném čase a s posloupností požadavků
-
hladový algoritmus, jeho (téměř) optimalita v modelu v reálném čase
-
rozvrhování pro 2 počítače s posloupností požadavků - 3/2 deterministicky
vs. 4/3 pravděpodobnostně
-
Číselně teoretické algoritmy
-
kvadratická rezidua a odmocniny
-
testování prvočíselnosti
-
kryptografie s veřejným klíčem (RSA, Rabinův systém)