I012 Složitost

Fakulta informatiky
zima 1995
Rozsah
0/0. 3 kr. 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
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Předpoklady
Předpokladem pro zápis je absolvování přednášky I005 Formální jazyky a automaty 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.
Informace učitele
http://www.fi.muni.cz/usr/cerna/i012.html
Předmět je zařazen také v obdobích zima 1996, zima 1997, podzim 1998, podzim 1999, podzim 2000, podzim 2001, podzim 2002, podzim 2003.