Předmět Aproximační a online algoritmy (NDMI018)
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 NDMI018 - Aproximační a online algoritmy, 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
Cíl
Naučit středně pokročilé techniky návrhu a analýzy aproximačních a online algoritmů.
Sylabus
Probírané techniky: Základní pojmy, aproximační a kompetitivní poměr Polynomiální aproximační schémata, jejich vztah k silné NP-úplnosti Pokročilé použití metod lineárního programování v aproximačních algoritmech: zaokrouhlování, primárně-duální algoritmy Použití metod semidefinitního programování v aproximačních algoritmech Použití potenciálu pro online algoritmy Metody pro dokazování obtížnosti i přibližného řešení kombinatorických problémů: L-redukce, APX-úplnost, PCP větaProbírané problémy a algoritmy: Různé modely rozvrhování a "bin packing", hladový algoritmus, další aproximační a online algoritmy Kombinatorické problémy: Steinerův strom, maximální řez, barvení grafů Online algoritmy pro paging (caching) a k-server problém Online algoritmy pro pohyb v neznámém prostředí
Literatura
D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011. V. V. Vazirani: Approximation Algorithms, Springer, 2001. A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998. A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.
Garant
prof. RNDr. Jiří Sgall, DrSc.Dr. rer. nat. Morteza Monemizadeh