FI:I012 Složitost - Informace o předmětu

I012 Složitost

Fakulta informatiky
podzim 2001

Rozsah

3/0. 3 kr. (plus ukončení). Doporučované ukončení: zk. Jiná možná ukončení: k, z.

Vyučující

prof. RNDr. Ivana Černá, CSc. (přednášející)

Garance

Rozvrh

Út 9:00–11:50 D1

Předpoklady

I005 FJA I

Omezení zápisu do předmětu

Předmět je nabízen i studentům mimo mateřské obory.

Mateřské obory/plány

Osnova

Problémy a algoritmy.
Základní výpočtové modely a míry složitosti. Polynomiální Turingova teze.
Složitostní třídy, jejich základní charakteristiky a hierarchie.
Redukce a úplnost v složitostních třídách. NP-úplné problémy.
coNP a výpočet funkcí.
Dolní odhady složitosti.
Pravděpodobnostní výpočty. Třídy ZPP, PP, BPP.
Paralelní výpočty. Třída NC. Paralelní výpočtová teze.
Aproximativní výpočty. Aproximativní algoritmy a odhady chyb. Neaproximovatelnost.
Aplikace: jednosměrné funkce a kryptografie.

Literatura

SIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997, xv, 396 s. ISBN 0-534-94728-X. info
PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
BOVET, D. a Pierluigi CRESCENZI. Introduction to the theory of complexity. New York: Prentice-Hall, 1994, xi, 282 s. ISBN 0-13-915380-2. info

Metody hodnocení

Závěrečné hodnocení je založeno na výsledcích písemné zkoušky.

Navazující předměty

Informace učitele

http://www.fi.muni.cz/usr/cerna/i012.html

Další komentáře

Předmět je vyučován každoročně.