Zajišťuje: KAM
Vyučující: Jiří Sgall
Rozsah v ZS: ---
Rozsah v LS: 2/0 Zk
Pro mnohé optimalizační problémy je obtížné navrhonout 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í. Typický příklad je rozvrhování úloh na několika počítačích. Je poměrně jednoduché nalézt algoritmus, který vždy vrátí rozvrh nejvýše dvakrát delší než optimální. Použitím složitějších metod je však možné efektivně nalézt i např. rozvrh jen o jedno procento delší než optimální. Tzv. online algoritmy se studují v situaci, kdy není předem znám celý vstup. Např. při rozvrhování je možné, že úlohy dostáváme postupně, ale přidělit je jednotlivým počítačům musíme ihned.
Přednáška se zaměří na teoretické studium aproximačních a online algoritmů pro různé problémy. Přednáška je určena především studentům vyšších ročníků, případně i doktorandům. Předpokládá se znalost základních pojmů z a teorie algoritmů (např. DMI026). Přednášející v tomto oboru pracuje a publikuje.
V.V. Vazirani: Approximation Algorithms, Springer, 2001.
G. Ausiello et al: Complexity and Approximation, Springer, 1999.
D.S. Hochbaum (editor): Approximation algorithms for NP-hard problems,
PWS publishing company, 1997.
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.
Přednáška se nekoná každý rok, předpokládám její opakování za 2-3 roky. Úmluva bude v prvním týdnu semestru na KAM, v rámci hromadné úmluvy na výběrové přednášky KAM. Kontakt: sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 222 090 780.
15. 4. 2005