M7140 Složitost

Přírodovědecká fakulta
podzim 1999
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)
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
Další komentáře
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 2000.