DMI025 - Pravděpodobnostní algoritmy - Probraná témata

• 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
• 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)
  • MAXCUT - jednoduchý 2-aproximační alg., derandomizace
  • 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
    
• 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
    
• 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
• 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
• Náhodnost v on-line algoritmech
  
  • cachování s k stránkami rychlé paměti (pravděpodobnostně O(log k) kompetitivní vs. k deterministicky), odpovídající dolní odhady
• Distribuované algoritmy
  
  • "Byzantine agreement"

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, 222090780