Předmět Vyčíslitelnost a složitost 2 (KIP / VYSL2)
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 / VYSL2 - Vyčíslitelnost a složitost 2, Přírodovědecká fakulta, Ostravská univerzita v Ostravě (OU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
1. Problémy typu ANO/NE. Složitost problému; třídy časové a prostorové složitosti. Složitost algoritmu jako horní odhad složitosti problému. Dolní odhady, obtížnost jejich získávání.2. Nedeterministické Turingovy stroje (NDTM), příklady NDTM.3. Jazyk akceptovatelný NDTM. Změna časové a prostorové složitosti pří přechodu od NDTM k DTM.4. 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ů (jazyků). 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.6. Idea důkazu NP-úplnosti problému splnitelnosti booleovských formulí (Cookova věta).7.- 8. Využití polynomiální redukovatelnosti k důkazu NP-úplnosti dalších problémů: 3CNF, k-vrcholové pokrytí, H-batoh, Partition, SubsetSum.9. Problém 2CNF a důkaz jeho náležení k třídě P.10. Algoritmy s návratem pro efektivní prohledávání.11.-12. 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ů.
Získané způsobilosti
- znalost hlubších vztahů teorie vyčíslitelnosti a složitosti- dobrá znalost vlastností formalizací pojmu algoritmu (Turingův stroj, rekurzivní funkce, PL-programy) a jejich ekvivalence- schopnost konstrukce Turingových strojů, rekurzivních funkcí, PL-programů včetně výpočtů složitosti- složitější NP úplné problémy a jejich převeditelnost
Literatura
A. Aho, J. Hopcroft, J. Ullman. The design and analysis of computer algorithms, Addison-Wesley, London 1974. U. Manber. Introduction to Algorithms, Addison-Wesley.
Požadavky
test (25 b.), samostatný úkol (25 b.), zkouška z teorie (50 b.);hodnocení dle platných předpisů na základě bodů (škála 0-100 b.)
Garant
prof. Irina Perfiljeva, CSc.
Vyučující
prof. Irina Perfiljeva, CSc.prof. Irina Perfiljeva, CSc.