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
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
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ě.
Předmět je zařazen také v obdobích zima 1995, zima 1996, zima 1997, podzim 1998, podzim 1999, podzim 2000, podzim 2002, podzim 2003.