U320 Výpočetní modely I

Fakulta informatiky
zima 1996
Rozsah
2/1. 0 kr. Ukončení: z.
Vyučující
doc. Ing. Lenka Carr Motyčková, CSc. (přednášející)
Garance
Kontaktní osoba: doc. Ing. Lenka Carr Motyčková, CSc.
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • Turingovy stroje, kompozitní diagram.
  • Nedeterministický a vícepáskový T.s.
  • Jazyky přijímané T. stroji.
  • Jazyky nepřijímané T. stroji.
  • Jazyky (problémy) rozhodnutelné T. stroji.
  • Problém zastavení a redukce dalších nerozhodnutelných problémů.
  • Parciálně rekurzívní funkce.
  • Church - Turingova téze.
  • Asymptotická složitost, věta o lineárním urychlení.
  • Třída P (RAM model).
  • Třída NP, P-NP problém.
  • Úplnost, redukce, Cookova věta.
  • Příklady redukcí mezi NP-úplnými problémy.
Předmět je zařazen také v obdobích zima 1995, zima 1997.