TIN048 - Složitost a dolní odhady
ZS 2002

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

Anotace

Lze dokázat, že nějakou explicitní funkci nelze počítat jednoduchými algoritmy? Známe mnoho problémů, o kterých předpokládáme, že se nedají jednoduše řešit (např. NP-úplné problémy), ale o žádné takové funkci neumíme dokázat například ani to, že se nedá počítat ve třech krocích na paralelním počítači s polynomiálním počtem procesorů, které umí počítat prahové funkce v jednom kroku.

Cílem přednášky je podat co nejúplnější obraz současného stavu výzkumu v této části teorie složitosti. Přednáška je určena především studentům vyšších ročníků a doktorandům. Přednášející v tomto oboru pracuje a publikuje. Související přednášky jsou TIN020 Složitost a NP-úplnost a AIL021 Booleovské funkce a jejich aplikace, které se zabývají podobnými tématy, ale obsahově se nepřekrývají a ani nejsou předpokladem této přednášky.

Osnova

Základní lit.

Většinou články z časopisů a konferencí. Základní pojmy jsou v různém rozsahu vyloženy např. v těchto knihách:
Papadimitriou: Computational Complexity
Garey, Johnson: Computers and Intractability. A guide to the theory of NP-completeness.

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. 222 090 780.


4. 10. 2002