Složitost - NTIN063

• Anglický název: Complexity
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 4
• Rozsah, examinace: letní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. 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
• Je korekvizitou pro: NTIN081
• Je neslučitelnost pro: NTIX063
• Je záměnnost pro: NTIX063

Anotace

čeština

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.

Poslední úprava: T_KTI (28.04.2015)

angličtina

This course extends the basic course on computational complexity. It introduces the students to the concepts of polynomial hierarchy classes, probabilistic computation, oracle computation, non-uniform computational models and the PCP theorem.

Poslední úprava: T_KTI (28.04.2015)

Cíl předmětu

čeština

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

Poslední úprava: T_KTI (23.05.2008)

angličtina

The aim is to learn more advanced topics from the complexity theory, complexity classes, their properties and mutual relations.

Poslední úprava: Čepek Ondřej, prof. RNDr., Ph.D. (26.09.2020)

Podmínky zakončení předmětu

čeština

K udělení zápočtu je třeba vyřešit dostatečné množství domácích úkolů. Předmět bude zakončen ústní zkouškou, která může s ohledem na situaci probíhat i distančně.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (30.04.2020)

angličtina

Credit is given for solving enough homework assignments. The lecture is finished with an oral exam. Depending on the situation, it is possible that the exam can proceed remotely.

Poslední úprava: Kučera Petr, RNDr., Ph.D. (30.04.2020)

Literatura

čeština

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 )

Poslední úprava: T_KTI (28.04.2015)

angličtina

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

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

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

Poslední úprava: T_KTI (28.04.2015)

Sylabus

čeština

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.

Poslední úprava: T_KTI (28.04.2015)

angličtina

1) Oracle Turing machines.

2) Polynomial hierarchy (definitions based on oracles and on alternating quantifiers, proof of their equivalence)

3) Quantified boolean formulas QBF and their completenes for PSPACE and Σi.

4) Nondeterministic hierarchy theorems.

5) Log-space reducibility, P-completeness and its consequences.

6) Szelepcsenyi-Immerman theorem, NL=coNL.

7) Non-uniform computational models - advice functions, boolean circuits, classes NC and P/poly, functions with

maximum circuit size.

8) Probabilistic algorithms - classes RP, coRP, ZPP, and BPP.

9) Error reduction in BPP, BPP is in P/poly, BPP is in Σ2.

10) NP-completeness of UNIQUE-SAT (probabilistic reduction)

11) PCP theorem (without proof) and its applications in inaproximability.

Poslední úprava: T_KTI (28.04.2015)

Požadavky k zápisu

TBA

Poslední úprava: Hric Jan, RNDr. (07.06.2019)