M7140 Složitost

Přírodovědecká fakulta
podzim 2000
Rozsah
3/0/0. 5 kr. Ukončení: zk.
Vyučující
prof. RNDr. Ivana Černá, CSc. (přednášející)
Garance
prof. RNDr. Ivana Černá, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Omezení zápisu do předmětu
Předmět je určen pouze studentům mateřských oborů.
Mateřské obory/plány
  • Matematika (program PřF, M-MA, směr Diskrétní matematika)
  • Matematika (program PřF, N-MA, směr Diskrétní matematika)
Cíle předmětu
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
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích podzim 1999.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/sci/podzim2000/M7140