FI:I017 Strukturní složitost - Informace o předmětu

I017 Strukturní složitost

Fakulta informatiky
jaro 2002

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

Rozvrh

St 8:00–9:50 B003

Předpoklady

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ů.
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ě.