Předmět Úvod do aproximačních a pravděpodobnostních algoritmů (NDMI084)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NDMI084 - Úvod do aproximačních a pravděpodobnostních algoritmů, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Sylabus
Probírané techniky: Hladový algoritmus jako metoda pro návrh aproximačních a online algoritmů Použití lineárního programování pro návrh aproximačních algoritmů Po dvou nezávislé náhodné proměnné Odstranění náhodnosti metodou podmíněných pravděpodobností Lokální prohledáváníProbírané problémy a algoritmy: Rozvrhování a hledání disjunktních cest v grafu - hladové algoritmy Problém obchodního cestujícího a vrcholové pokrytí - jednoduché kombinatorické aproximační algoritmy Množinové pokrytí - hladový algoritmus, použití lineárního programování Splnitelnost (MAX-SAT) - použití lineárního programování, náhodné zaokrouhlování, derandomizace Hashování dynamické a statické - pravděpodobnostní algoritmy, po dvou nezávislé náhodné proměnné Nejvétší řez v grafu - aproximace pomocí lokálního prohledávání Nejmenší řez v grafu - rychlý pravděpodobnostní algoritmus Maximální nezávislá množina v grafu - rychlý pravděpodobnostní paralelní algoritmus Verifikace maticových rovnic - pravděpodobnostní protokol
Literatura
D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge University Press, 2011.J. Kleinberg, E. Tardos: Algorithm Design, Pearson, 2006.V.V. Vazirani: Approximation Algorithms, Springer, 2001. R. Motwani, P. Raghavan: Randomized algorithms.M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
Garant
doc. Mgr. Petr Kolman, Ph.D.prof. RNDr. Jiří Sgall, DrSc.