Detail předmětu
Vyčíslitelnost a složitost
VSL Ak. rok 2003/2004 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
Zajišťuje ústav
Získané dovednosti, znalosti a kompetence z předmětu
Povědomí o teoretických i praktických mezích použitelnosti jakýchkoliv výpočetních systémů. Znalost pojmů, nutných k pochopení problémů modelování, formální specifikace, automatizace návrhu, verifikace a umělé inteligence.
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 fyzikálně realizovatelných výpočetních systémech.
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.
Zařazení předmětu ve studijních plánech
- Program EI-BC-3, obor VTB, 1. ročník, volitelný
- Program EI-BC-3 (anglicky), obor VTB, 1. ročník, volitelný
- Program EI-MGR-3, obor VTN, 2. ročník, povinný
- Program EI-MGR-5, obor VTI, 2. ročník, povinný
- Program EI-MGR-5 (anglicky), obor VTI, 2. ročník, povinný