Fakulta informačních technologií VUT v Brně

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

Jazyk výuky

česky, anglicky

Zakončení

zápočet+zkouška (písemná)

Rozsah

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

Bodové hodnocení

75 zkouška, 20 půlsemestrální test, 5 projekty

Zajišťuje ústav

Přednášející

Cvičící

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

Dovednosti, znalosti a kompetence obecné

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.

Osnova ostatní - projekty, práce

  • 5 domácích úloh v průběhu semestru

Průběžná kontrola studia

Domácí úlohy - 5 bodů.
Půlsemetrální zkouška - 20 bodů.
Nahoru