FI:U320 Výpočetní modely I - Informace o předmětu

U320 Výpočetní modely I

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

• Učitelství výpočetní techniky pro střední školy (program FI, M-IN)
• Učitelství výpočetní techniky pro střední školy (program FI, M-SS)

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.

• Statistika zápisu (zima 1996, nejnovější)
  
• Permalink: https://is.muni.cz/predmet/fi/zima1996/U320