I017 Strukturní složitost

Fakulta informatiky
jaro 2003
Rozsah
2/0. 2 kr. (plus ukončení). 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
prof. RNDr. Mojmír Křetínský, CSc.
Katedra teorie programování – Fakulta informatiky
Kontaktní osoba: prof. RNDr. Ivana Černá, CSc.
Rozvrh
Út 10:00–11:50 B410
Předpoklady
I012 Složitost
Kurz je určen studentům 5-letého magisterského studia a v jarním semestru 2002/03 se otevírá naposledy.
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ů.
  • Kolmogorovská složitost. Důkazy dolních odhadů složitosti založené na Kolmogorovské složitosti.
  • Deskriptivní složitost.
Literatura
  • SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998, x, 320. ISBN 3540644253. info
  • Complexity theory retrospective. Edited by Lane A. Hemaspaandra - Alan L. Selman. New York: Springer-Verlag, 1997, xi, 339. ISBN 0387949739. info
  • GRUSKA, Jozef. Foundations of computing. London: International Thompson Computer Press, 1997, xv, 716 s. ISBN 1-85032-243-0. info
  • BALCÁZAR, José Luis, Josep DÍAZ a Joaquim GABARRÓ. Structural complexity I. Berlín: Springer-Verlag, 1995, xiii, 208. ISBN 3-540-58384-X. info
  • PAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994, xv, 523 s. ISBN 0-201-53082-1. info
Metody hodnocení
Během semestru studenti samostatně řeší zadané problémy. Řešení jsou základem pro určení závěrečného hodnocení.
Informace učitele
http://www.fi.muni.cz/usr/cerna/i017.html
Další komentáře
Předmět je vyučován každoročně.
Předmět je zařazen také v obdobích zima 1995, zima 1996, zima 1997, podzim 1998, jaro 2000, jaro 2001, jaro 2002.
  • Statistika zápisu (nejnovější)
  • Permalink: https://is.muni.cz/predmet/fi/jaro2003/I017