PředmětyPředměty(verze: 806)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Aproximační a online algoritmy - NDMI018
Anglický název: Approximation and Online Algorithms
Zajišťuje: Informatický ústav Univerzity Karlovy (32-IUUK)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 6
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://iuuk.mff.cuni.cz/~sgall/vyuka/
Garant: prof. RNDr. Jiří Sgall, DrSc.
Třída: Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Diskrétní matematika
Anotace -
Poslední úprava: (11.05.2015)

Pro mnohé optimalizační problémy je obtížné navrhnout algoritmy, které je vyřeší optimálně a zároveň rychle (např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Tzv. online algoritmy se studují v situaci, kde není předem znám celý vstup. Přednáška se zaměří na teoretické studium aproximačních a online algoritmů pro různé problémy. Předpokládá se znalost na úrovni Bc. předmětu NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů.
Cíl předmětu -
Poslední úprava: (11.05.2015)

Naučit středně pokročilé techniky návrhu a analýzy aproximačních a online algoritmů.

Literatura -
Poslední úprava: (11.05.2015)

  • 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.

Sylabus -
Poslední úprava: (11.05.2015)

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ěta

Probí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í

 
Univerzita Karlova | Informační systém UK