PředmětyPředměty(verze: 804)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Základy složitosti a vyčíslitelnosti - NTIN090
Anglický název: Introduction to Complexity and Computability
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2015
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní 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í
Další informace: http://ktiml.mff.cuni.cz/~kucerap/NTIN090/index.html
Garant: doc. RNDr. Ondřej Čepek, Ph.D.
RNDr. Petr Kučera, Ph.D.
Třída: Informatika Mgr. - učitelské studium informatiky
Informatika Mgr. - Softwarové systémy
Informatika Mgr. - Matematická lingvistika
M Mgr. MSTR
M Mgr. MSTR > Povinně volitelné
Kategorizace předmětu: Informatika > Teoretická informatika
Záměnnost : {Složitost I a Vyčíslitelnost I}
Neslučitelnost : NTIN062, NTIN064
Je záměnnost pro: NTIN062
Anotace -
Poslední úprava: T_KTI (28.04.2015)

Přednáška seznamující se základy teorie algoritmů, efektivní vyčíslitelnosti a teorie složitosti. První část přednášky je věnována základům vyčíslitelnosti: Turingovy stroje. RAM. Rekurzivní a rekurzivně spočetné jazyky a množiny. Algoritmicky nerozhodnutelné problémy. Druhá část přednášky je věnována studiu tříd časové a prostorové složitosti: Ekvivalence PSPACE a NPSPACE. Věty o hierarchiích. Třída NP. Polynomiální převoditelnost problémů. Důkazy NP-úplnosti. Aproximační algoritmy a schémata.
Cíl předmětu -
Poslední úprava: T_KTI (23.05.2008)

Naučit základy teorie složitosti a vyčíslitelnosti.

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

Stránky k předmětu (kde je možno najít prezentaci z přednášky a skripta): http://ktiml.mff.cuni.cz/~kucerap/NTIN090/index-en.html

Sipser, M. Introduction to the Theory of Computation. Vol. 2. Boston: Thomson Course Technology, 2006.

Demuth O., Kryl R., Kučera A.: Teorie algoritmů I, II. SPN, 1984, 1989

Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987

Odifreddi P.: Classical recursion theory, North-Holland, 1989

Garey, Johnson. Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978

Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009 (Draft ke stažení online).

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

1) Turingovy stroje a jejich varianty. Churchova-Turingova teze

2) Halting problém.

3) RAM a jeho ekvivalence s Turingovými stroji. Algoritmicky vyčíslitelné funkce.

4) Rekurzivní a rekurzivně spočetné jazyky a množiny a jejich vlastnosti.

5) 1-převoditelnost a m-převoditelnost, 1-úplné a m-úplné množiny.

6) Riceova věta.

7) Nedeterministické Turingovy stroje, základní třídy složitosti, třídy P, NP, PSPACE, EXP.

8) Savičova věta - ekvivalence tříd PSPACE a NPSPACE.

9) Věty o deterministické prostorové a časové hierarchii.

10) Polynomiální převoditelnost problémů, pojmy NP-těžkosti a NP-úplnosti.

11) Cook-Levinova věta, příklady NP-úplných problémů, důkazy NP-úplnosti.

12) Pseudopolynomiální algoritmy a silná NP-úplnost.

13) Aproximace NP-těžkých optimalizačních úloh. Aproximační algoritmy a schémata.

14) Třídy co-NP a #P.

 
Univerzita Karlova | Informační systém UK