Předmět Základy složitosti a vyčíslitelnosti (NTIN090)

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 NTIN090 - Základy složitosti a vyčíslitelnosti, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).

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

Cíl

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

Sylabus

1) Turingovy stroje a jejich varianty. Churchova-Turingova teze2) 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.

Literatura

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.htmlSipser, 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, 1989Soare R.I.: Recursively enumerable sets and degrees. Springer-Verlag, 1987Odifreddi P.: Classical recursion theory, North-Holland, 1989Garey, Johnson. Computers and intractability - a guide to the theory of NP-completeness, W.H. Freeman 1978Arora S., Barak B.: Computational Complexity: A Modern Approach. Cambridge University Press 2009 (Draft ke stažení online).

Garant

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