• Třídy pravděpodobnostních algoritmů.
• RP, BPP, ZPP, PP, RL(ogspace) 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
• 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
• Pravděpodobnostní algoritmy pro kombinatorické problémy.
• MINCUT - jednoduchý alg., zlepšení iterativním procesem na čas O(n² polylog n)
• MIS: paralelní algoritmus pro hledání maximální nezávislé množiny (maximální vzhledem k inkluzi, tedy ne nutně největší)
• 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í
• 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ů, univerzální transverzální posloupnosti
• 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í
  
• redukce na náhodné vybírání, počítání splňujících ohodnocení DNF
• permanent (párování v bipartitních grafech), konduktance a použití náhodných procházek
• 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 2^2k
• pravděpodobnostní algoritmus 3^k, dolní odhad 2.61^k
• Verifikace
• maticové násobení
• polynomiální výrazy
• Distribuované algoritmy
  
• hledání shody - "Byzantine agreement"
• dělení zdrojů - "cake cutting"
  

Zkoušky

Kontakt: sgall@math.cas.cz, 222 090 780