Název:

Složitost

Zkratka:SLO
Ak.rok:2006/2007 (není otevřen)
Semestr:letní
Studijní plán:
ProgramOborRočníkPovinnost
IT-MGR-2MGM.-volitelný
IT-MGR-2MIN.2.volitelný
IT-MGR-2MIS.1.volitelný
IT-MGR-2MPS-volitelný
IT-MGR-2EITE2.volitelný
Vyučovací jazyk:čeština, angličtina
Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/SLO/private/
Kredity:5 kreditů
Ukončení:zkouška (písemná)
Výuka:
hod./sempřednáškasem./cvičenílab. cvičenípoč. cvičeníjiná
Rozsah:2600026
 zkouškatestycvičenílaboratořeostatní
Body:7000030
Garant:Honzík Jan M., prof. Ing., CSc., UIFS
Přednášející:Honzík Jan M., prof. Ing., CSc., UIFS
Janoušek Vladimír, doc. Ing., Ph.D., UITS
Fakulta:Fakulta informačních technologií VUT v Brně
Pracoviště:Ústav inteligentních systémů FIT VUT v Brně
Prerekvizity: 
Teoretická informatika (TIN), UITS
Navazující:
Formální analýza a verifikace (FAV), UITS
Kryptografie (KRY), UITS
Paralelní a distribuované algoritmy (PRL), UITS
Nahrazuje:
Vyčíslitelnost a složitost (VSL), UITS
 
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.
Anotace:
  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.
Získané dovednosti, znalosti a kompetence:
  Znalost teoretických i praktických mezích použitelnosti jakýchkoliv výpočetních systémů.
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.
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
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
Průběžná kontrola studia:
  Hodnocení projektů.
 

Vaše IPv4 adresa: 54.81.76.247
Přepnout na IPv6 spojení

DNSSEC [dnssec]