Detail předmětu

Vyčíslitelnost a složitost

VSL Ak. rok 2005/2006 zimní semestr 6 kreditů

Aktuální akademický rok

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

Janoušek Vladimír, doc. Ing., Ph.D. (UITS)

Jazyk výuky

česky

Zakončení

zápočet+zkouška

Rozsah

  • 39 hod. přednášky
  • 12 hod. cvičení
  • 14 hod. projekty

Zajišťuje ústav

Ústav inteligentních systémů (UITS)

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ů.

Nahoru