PředmětyPředměty(verze: 861)
Předmět, akademický rok 2019/2020
  
Složitost - NTIN063
Anglický název: Complexity
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015 do 2019
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/1 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: RNDr. Petr Kučera, Ph.D.
doc. RNDr. Ondřej Čepek, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN062
K//Je korekvizitou pro: NTIN081
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: T_KTI (28.04.2015)
Přednáška rozšiřuje základní přednášku o výpočetní složitosti. Seznamuje s třídami polynomiální hierarchie, pravděpodobnostními výpočty, výpočty s orákuly, neuniformními modely výpočtu a PCP větou.
Cíl předmětu -
Poslední úprava: T_KTI (23.05.2008)

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

Podmínky zakončení předmětu -
Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

Literatura -
Poslední úprava: T_KTI (28.04.2015)

Arora S., Barak B. Computational Complexity: A Modern Approach. Cambridge University Press 2009

Balcázar, Díaz, Gabarró : Structural Complexity I, Springer Verlag 1988

Michal Černý, Výpočty I, II, III, Professional Publishing, 2011-2012

Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press 2008

V. 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 )

Sylabus -
Poslední úprava: T_KTI (28.04.2015)

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.

Požadavky k zápisu
Poslední úprava: RNDr. Jan Hric (07.06.2019)

TBA

 
Univerzita Karlova | Informační systém UK