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

Detail předmětu

Složitost

SLO Ak. rok 2007/2008 letní semestr 5 kreditů

Předmět není v tomto roce otevřen
Zavřít
Tento předmět pokrývá následující témata: Modely výpočtů (skeletový jazyk, Stroje typu RAM,  RASP a jejich vztah k Turingovým strojům), časová složitost, složitostní třídy jazyků, P a NP jazyky, NP-úplnost, významné NP-úplné jazyky a problémy, problém splnitelnosti a jeho varianty, NP a co-NP jazyky, prostorová složitost, PS a NPS jazyky, PS-úplné jazyky, pravděpodobnostní složitostní třídy,  aplikace teorie výpočertní složitosti - jednosměrné funkce a kryptografie.

Garant předmětu

Jazyk výuky

česky, anglicky

Zakončení

zkouška (písemná)

Rozsah

26 hod. přednášky, 26 hod. projekty

Bodové hodnocení

70 zkouška, 30 projekty

Zajišťuje ústav

Získané dovednosti, znalosti a kompetence z předmětu

Znalost 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í složitosti, nutnou k pochopení praktických možností algoritmického řešení problémů na fyzikálně realizovatelných výpočetních systémech.

Literatura studijní

  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  • Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley 2001, ISBN 0-201-44124-1

Literatura referenční

  • Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
  • Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley 2001, ISBN 0-201-44124-1

Osnova přednášek

  • Úvod, složitost časová a prostorová.
  • Modely výpočtů. Skeletový jazyk.
  • Stroje typu RAM,  RASP a jejich vztah k Turingovým strojům.
  • Nedeterminismus. Stroje s orákulem. Reducibilita.
  • Třídy P a NP. Příklady: Kruskal, obchodní cestující.
  • NP-úplnost. NP-úplné problémy.
  • Problém splnitelnosti a jeho varianty.
  • Další NP-úplné problémy.
  • NP a co-NP jazyky.
  • Prostorová složitost, PS a NPS jazyky.
  • PS-úplné jazyky.
  • Pravděpodobnostní složitostní třídy jazyků - třídy RP a ZPP.
  • Aplikace: jednosměrné funkce a kryptografie.

Osnova ostatní - projekty, práce

  • Projekt na téma Matematické modely výpočtů.
  • Projekt na téma Složitost.

Průběžná kontrola studia

Hodnocení projektů.
Nahoru