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

I012 Složitost

Rozsah

3/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

• Informatika (program FI, B-IN)
• Informatika (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)
• Výpočetní technika (program FI, B-IN)

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

• Statistika zápisu (zima 1996, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/zima1996/I012