I017 Výpočetní složitost I

Fakulta informatiky
zima 1996
Rozsah
2/0. 2 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řednáška navazuje na kurs I012 Složitost.
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
  • Více o složitostních třídách; jejich struktura a vlastnosti. Srovnání různých složitostních mír.
  • Techniky pro získávání dolních odhadů složitosti.
  • Polynomiální hierarchie.
  • Výpočty, které počítají.
  • Alternování a hry. Interaktivní protokoly.
  • Interaktivní důkazové systémy. Důkazy s nulovou znalostí a transparentní důkazy. Pravděpodobnostní ověřování důkazů a programů.
Informace učitele
http://www.fi.muni.cz/usr/cerna/i017.html
Předmět je zařazen také v obdobích zima 1995, zima 1997, podzim 1998, jaro 2000, jaro 2001, jaro 2002, jaro 2003.