Detail předmětu
Vyčíslitelnost a složitost
VSL Ak. rok 2005/2006 zimní semestr 6 kreditů
Matematické modely výpočtů. Základní vlastnosti Turingových strojů, modulární stavba. Vícepáskové a nedeterministické TS. TS jako akceptory jazyků. Základní problém rozhodnutelnosti. Universální TS. Problém zastavení, Postův korespodenční problém. Vyčíslitelnost, primitivní rekurzívní funkce, parciální rekurzívní funkce. Turingova a Churchova teze. Algoritmická složitost, složitost problému. Asymptotická ohraničení složitostí. Složitost v kontextu různých výpočetních modelů, polynomiálně vázané modely. Deterministická rozhodnutelnost v polynomiálním čase. NP-jazyky a NP-problémy. NP-úplnost.
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 12 hod. cvičení
- 14 hod. projekty
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
Základní vědomosti o teorii vyčíslitelnosti a složitosti. Povědomí o teoretických i praktických mezích použitelnosti jakýchkoliv výpočetních systémů.
Povědomí o teoretických i praktických mezích použitelnosti jakýchkoliv výpočetních systémů.
Cíle předmětu
Seznámit studenty s matematickými modely výpočtů a s teorií vyčíslitelnosti a složitosti, nutnou k pochopení teoretických i praktických možností algoritmického řešení problémů na fyzicky realizovatelných výpočetních systémech.
Požadované prerekvizitní znalosti a dovednosti
Základy teorie formálních jazyků.
Literatura studijní
- Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.
Literatura referenční
- Martin, J.C.: Introduction to Languages and the Theory of Computation, McGraw-Hill, Inc., 1991.
- Saloma, A.: Computation and Automata, Cambridge University Press, 1985.
Osnova přednášek
- Matematické modely výpočtů.
- Základní vlastnosti Turingových strojů, modulární stavba.
- Vícepáskové a nedeterministické TS.
- TS jako akceptory jazyků.
- Základní problém rozhodnutelnosti.
- Universální TS. Problém zastavení, Postův korespodenční problém.
- Vyčíslitelnost, primitivní rekurzívní funkce, parciální rekurzívní funkce.
- Turingova a Churchova teze.
- Algoritmická složitost, složitost problému.
- Asymptotická ohraničení složitostí.
- Složitost v kontextu různých výpočetních modelů, polynomiálně vázané modely.
- Deterministická rozhodnutelnost v polynomiálním čase.
- NP-jazyky a NP-problémy. NP-úplnost.
Průběžná kontrola studia
Dosažení 50 procent bodů (10) z půlsemestrální zkoušky.
Kontrolovaná výuka
Domácí úlohy - 5 bodů.
Půlsemetrální zkouška - 20 bodů.