I396 - Aproximační a online algoritmy
ZS 1999

Zajišťuje: KAM
Vyučující: Jiří Sgall
Rozsah v ZS: 2/0 Zk
Rozsah v LS: ---
Třída: I

Anotace

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. Nebudeme se věnovat online algoritmům pro datové struktury (těm je věnována přednáška I259 Datové struktury a online algoritmy V. Majerecha).

Přednáška je určena především studentům vyšších ročníků, případně i doktorandům. Práce na otevřených problémech v této oblasti může vést k diplomové nebo i disertační práci. Přednášející v tomto oboru pracuje a publikuje.

Předpoklady

Základní pojmy z teorie algoritmů (např. I025, I148, nebo I404)

Osnova

Základní lit.

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.

Doplň.popis

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

Probraná témata