Název:

Vyčíslitelnost a složitost

Zkratka:VSL
Ak.rok:ukončen 2005/2006
Semestr:zimní
Vyučovací jazyk:čeština, angličtina
Informace veřejné:http://www.fit.vutbr.cz/study/courses/VSL/public/
Kredity:6 kreditů
Ukončení:zápočet+zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:39120014
 zkouškatestycvičenílaboratořeostatní
Body:7520005
Garant:Janoušek Vladimír, doc. Ing., Ph.D. (UITS)
Přednášející:Češka Milan, prof. RNDr., CSc. (UITS)
Janoušek Vladimír, doc. Ing., Ph.D. (UITS)
Cvičící:Janoušek Vladimír, doc. Ing., Ph.D. (UITS)
Křivka Zbyněk, Ing., Ph.D. (UIFS)
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Prerekvizity: 
Teoretická informatika 1 (TI1), UITS
Navazující:
Paralelní a distribuované algoritmy (PDA), UITS
 
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.
Anotace:
  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.
Požadované prerekvizitní znalosti a dovednosti:
  Základy teorie formálních jazyků.
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ů.
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
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.
Literatura studijní:
 
  • Brookshear J.G.: Theory of Computation, The Benjamin/Cummings Publishing Company, Inc, Redwood City, California 1989.
Průběžná kontrola studia:
  Domácí úlohy - 5 bodů.
Půlsemetrální zkouška - 20 bodů.
 

Vaše IPv4 adresa: 35.153.135.60