Předmět Složitost (NTIN063)

Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN063 - Složitost, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).

Materiál	Typ	Datum	Počet stažení

Cíl

Naučit další látku z teorie složitosti, třídy složitosti, jejich vlastnosti a vztahy.

Sylabus

1) Turingovy stroje s orákulem.2) Polynomiální hierarchie (definice pomocí orákulí a pomocí alternujicích kvantifikátorů, důkaz ekvivalence).3) Kvantifikované booleovské formule QBF a jejich úplnost pro PSPACE a Σi.4) Nedeterministická hierarchie.5) Log-space převoditelnost, P-úplnost a její důsledky.6) Věta Szelepcsenyi-Immermana a NL=coNL. 7) Neuniformní výpočetní modely - radicí funkce, booleovské obvody, třídy NC a P/poly, funkce s maximální velikostí obvodu.8) Pravděpodobnostní algoritmy - třídy RP, coRP, ZPP a BPP.9) Redukce chyby pro BPP, BPP je v P/poly, BPP je v Σ2.10) NP-úplnost UNIQUE-SAT (pravděpodobnostní redukce)11) PCP věta (bez důkazu) a její využití pro neaproximovatelnost.

Literatura

Arora S., Barak B. Computational Complexity: A Modern Approach. Cambridge University Press 2009Balcázar, Díaz, Gabarró : Structural Complexity I, Springer Verlag 1988Michal Černý, Výpočty I, II, III, Professional Publishing, 2011-2012Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008V. Majerech: Složitost a NP-úplnost (skripta v elektronické podobě ke stažení na stránkách KTIML -http://ktiml.mff.cuni.cz/index.php?select=teaching&section=source&lang=czech )

Garant

doc. RNDr. Ondřej Čepek, Ph.D.RNDr. Petr Kučera, Ph.D.