Předmět Vyčíslitelnost a složitost (KIP / XVYS1)

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 KIP / XVYS1 - Vyčíslitelnost a složitost, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).

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

Obsah

1. Opakování intuitivních pojmů algoritmické vyčíslitelnosti, rozhodnutelnosti a částečné rozhodnutelnosti. Exaktní formalizace těchto pojmů. Deterministické Turingovy stroje (DTM), příklady. Univerzální Turingův stroj.2. Problém zastavení a jeho nerozhodnutelnost. Další nerozhodnutelné problémy, převoditelnost problémů. Churchova teze. Důkazy nerozhodnutelnosti. Enumerace Turingových strojů. Riceova věta.3. Algoritmy a jejich složitost. Třídy časové a prostorové složitosti. Problémy a jejich složitost. Složitost algoritmu jako horní odhad složitosti problému. Třídy časové složitosti. Strukturální složitost. Příklady výpočtů složitosti problémů.4. Nedeterministické Turingovy stroje (NDTM), příklady NDTM. Jazyk akceptovatelný NDTM. Změna časové a prostorové složitosti pří přechodu od NDTM k DTM. Třída P (=PTIME) a třída NP (=NPTIME) a jejich robustnost vůči výpočetním modelům. Příklady NP problémů. Polynomiální redukovatelnost problémů (jazyků).5. NP-úplné problémy. Otevřená otázka, zda P=NP. Problém SAT a jeho náležení k třídě NP. Idea důkazu NP-úplnosti problému splnitelnosti booleovských formulí (Cookova věta).6. Využití polynomiální redukovatelnosti k důkazu NP-úplnosti dalších problémů: 3CNF, k-vrcholové pokrytí, H-batoh, Partition, SubsetSum.7. Další třídy časové i prostorové složitosti a jejich vzájemné vztahy. Třídy PSPACE, EXPTIME, EXPSPACE. Idea rovnosti PSPACE=NPSPACE (Savitchova věta). Příklady PSPACE-úplných problémů.8. Primitivně rekurzivní funkce. Částečné rekurzivní funkce. Konstrukce konkrétních funkcí.9. PL-vyčíslitelné funkce. Model RAM. Důkaz ekvivalence s Turingovými stroji. Věta o rekurzi.10. "Greedy" algoritmy. Minimální kostra grafu. Metoda "rozděl a panuj", algoritmus MergeSort jako jeho příklad. Odhad složitosti řešením rekurentních rovnic. Strassenův algoritmus násobení dvou matic.11. Algoritmus nalezení nejlepšího pořadí násobení N matic. Algoritmy na grafech I: prohledávání do hloubky. Algoritmus nalezení Eulerova tahu.12. Algoritmy na grafech II: prohledávání do šířky. Dijkstrův algoritmus nalezení nejkratších cest. Algoritmus nalezení nejkratších cest v orientovaném grafu bez kružnic.

Získané způsobilosti

- znalost základů problematiky teorie vyčíslitelnosti a složitosti- dobrá znalost vlastností rozhodnutelných a nerozhodnutelných problémů, složitosti časové a prostorové, NPTIME vs.PTIME- schopnost konstrukce Turingových strojů, výpočtu složitosti algoritmů, - nejznámější NP-úplné problémy

Literatura

Pavliska, V. Vyčíslitelnost a složitost I., OU Ostrava, 2003. Pavliska V. Vyčíslitelnost a složitost II., OU Ostrava, 2003. U. Manber. Introduction to Algorithms, Addison-Wesley. Aho, A., Hopcroft, J., Ullman, J. The design and analysis of computer algorithms, Addison-Wesley, 1974. Jančar P. Teoretická informatika, VŠB Ostrava, 2010. Černá, I. Úvod do teorie složitosti, FI MUNI, 1993.

Požadavky

Zkoušku student absolvuje v souladu s platným Studijním řádem, zejména s důrazem na č. 32 a čl. 33 Studijního a zkušebního řádu OU.V průběhu semestru zpracuje student semestrální práci s maximálním bodovým ziskem 30 bodů. Ústní část zkoušky je pak hodnocena 70 body.

Garant

prof. Irina Perfiljeva, CSc.

Vyučující

RNDr. Michal Janošek, Ph.D.prof. Irina Perfiljeva, CSc.RNDr. Martin Žáček, Ph.D.doc. RNDr. PaedDr. Hashim Habiballa, PhD., Ph.D.RNDr. Michal Janošek, Ph.D.Mgr. Viktor PavliskaRNDr. Martin Žáček, Ph.D.