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(n2
polylog n)
MIS: paralelní algoritmus pro hledání maximální nezávislé
množiny
(maximální
vzhledem k inkluzi, tedy ne nutně největší)
3SAT - rychlý exponenciální algoritmus
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
Verifikace
maticové násobení
polynomiální výrazy
Distribuované algoritmy
hledání shody - "Byzantine agreement"
Zkoušky
se konají v mé pracovně na MFF Malá Strana, 3. patro u zadního
schodiště, případně na přilehlé chodbě KAM. Vypsané jsou dva termíny,
ve čtvrtky 18.6. a 25.6. od 10 hodin.
Kontakt
E-mail: last name at
kam.mff.cuni.cz http://kam.mff.cuni.cz/~sgall/
Malostranské nám. 25, 3. patro,
místnost
326
Telefon: 221 914 293 (pracovna), 221 914 230 (sekretářka)