Sylabus
- Příklady pravděpodobnostních algoritmů a protokolů
- Třídy pravděpodobnostních algoritmů a jejich vztahy
- Věty o minimaxu (von Neumann, Yao)
- Techniky pro omezení počtu náhodných bitů: po dvou nezávislé proměnné, expandery
- Markovovy řetězce a jejich použití: náhodné procházky a testování souvislosti grafů, algoritmy pro splnitelnost, přibližné počítání (splňující ohodnocení, párování v hustých grafech), coupling (počítání obarvení grafů)
- Základy teorie front
- Algoritmy pro proudy dat
- Pravděpodobnostní protokoly a verifikace: testování linearity funkcí, PCP věta (důkaz exponenciální verze)
Anotace
Přenáška o použití náhodnosti v algoritmech a protokolech. Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně.
Probereme metody pro návrh a analýzu takových algoritmů a protokolů, ilustrované na konkrétních problémech. Předpokládá se znalost na úrovni předmětů NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů a NTIN022 Pravděpodobnostní techniky.