| Název: | Složitost |
|---|
| Zkratka: | SLO |
|---|
| Ak.rok: | 2011/2012 |
|---|
| Semestr: | letní |
|---|
| Studijní plán: | |
|---|
| 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 (kombinovaná) |
|---|
| Výuka: | | hod./sem | přednáška | sem./cvičení | lab. cvičení | poč. cvičení | jiná |
|---|
| Rozsah: | 26 | 0 | 0 | 0 | 26 |
|---|
| | zkouška | testy | cvičení | laboratoře | ostatní |
|---|
| Body: | 68 | 0 | 0 | 0 | 32 |
|---|
|
|---|
| Garant: | Vojnar Tomáš, prof. Ing., Ph.D., UITS |
|---|
| Přednášející: | Rogalewicz Adam, Mgr., Ph.D., UITS |
|---|
| Cvičící: | Rogalewicz Adam, Mgr., Ph.D., UITS |
|---|
| Fakulta: | Fakulta informačních technologií VUT v Brně |
|---|
| Pracoviště: | Ústav inteligentních systémů FIT VUT v Brně |
|---|
| Prerekvizity: | |
|---|
| Navazující: | |
|---|
| Nahrazuje: | |
|---|
| | | Cíle předmětu: |
|---|
Seznámit studenty s teorií výpočetní 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. Seznámit studenty s vybranými přístupy k řešení výpočetně složitých problémů. | | Anotace: |
|---|
Turingovy stroje jako základní výpočetní model pro analýzu výpočetní složitosti, časová a prostorová složitost výpočtů na Turingových strojích. Alternativní modely výpočtů, skeletový jazyk, stroje RAM a RASP a jejich vztah k Turingovým strojům z hlediska výpočetní složitosti. Asymptotické odhady složitosti, pojem tříd složitosti založených na časově a prostorově zkonstruovatelných funkcích, typické příklady tříd složitosti. Vlastnosti tříd složitosti: význam determinismu a nedeterminismu v oblasti výpočetní složitosti, Savitchův teorém, vztah prostoru a času, uzavřenost tříd složitosti vůči doplňku, ostrost vztahů mezi třídami. Některé pokročilé vlastnosti tříd složitosti: Blumův teorém, gap theorem (a jeho vztah k definici tříd složitosti na základě časově a prostorově zkonstruovatelných funkcí). Redukovatelnost a pojem úplnosti tříd složitosti. Příklady problémů úplných pro různé třídy složitosti. Hlubší diskuse tříd P a NP s důrazem na NP-úplné problémy (problém splnitelnosti apod.). Vztah rozhodovacích a optimalizačních problémů. Metody řešení výpočetně složitých optimalizačních problémů: deterministické přístupy, aproximace, pravděpodobnostní algoritmy. Vztah výpočetní složitosti a kryptografie. Hlubší diskuse PSPACE-úplných problémů, výpočetní složitost typických problémů z oblasti formální verifikace. | | Požadované prerekvizitní znalosti a dovednosti: |
|---|
Teorie formálních jazyků a rozhodnutelnosti na magisterské úrovni. | | Získané dovednosti, znalosti a kompetence: |
|---|
Znalost teoretických i praktických mezí použitelnosti výpočetních systémů. Schopnost použít vybrané přístupy k řešení výpočetně složitých problémů. | | Osnova přednášek: |
|---|
- Úvod, Turingovy stroje, složitost časová a prostorová.
- Alternativní modely výpočtů, skeletový jazyk, stroje typu RAM, RASP a jejich vztah k Turingovým strojům.
- Asymptotické odhady složitosti, třídy složitosti, determinismus a nedeterminismus z pohledu složitosti.
- Souvislosti prostoru a času z pohledu složitosti, uzavřenost tříd složitosti vůči doplňku, ostrost inkluzí mezi třídami složitosti.
- Blumův teorém. Gap theorem.
- Redukovatelnost, pojem úplnosti tříd složitosti, nejběžnější případy úplnosti.
- Třídy P a NP a jejich vlastnosti. NP-úplné problémy, problém splnitelnosti a jeho varianty.
- Problém obchodního cestujícího, problém batohu a další významné NP-úplné problémy.
- NP optimalizační problémy a jejich deterministické řešení: pseudo-polynomiální algoritmy, parametrizovaná složitost.
- Aproximační algoritmy, neaproximovatelnost.
- Pravděpodobnostní algoritmy a pravděpodobnostní třídy složitosti.
- Složitost a kryptografie.
- PSPACE-úplné problémy. Složitost a formální verifikace.
| | Osnova ostatní - projekty, práce: |
|---|
|
Čtyři dílčí domácí úlohy zaměřené na různé aspekty probírané látky. | | Literatura referenční: |
|---|
- Gruska, J.: Foundations of Computing, International Thomson Computer Press, 1997, ISBN 1-85032-243-0
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- 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
- Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity, Prentice Hall International Series in Computer Science, 1994, ISBN 0-13915-380-2
- Hopcroft, J.E. et al: Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 2001, ISBN 0-201-44124-1
- Goldreich, O.: Computational Complexity: A Conceptual Perspective, Cambridge University Press, 2008, ISBN 0-521-88473-X
- Kozen, D.C.: Theory of Computation, Springer, 2006, ISBN 1-846-28297-7
| | Průběžná kontrola studia: |
|---|
- Čtyři opravované domácí úlohy - každá za 8 bodů.
- Závěrečná zkouška: 68 bodů.
- Podmínka zápočtu: min. 15 bodů získaných v průběhu semestru.
- Hranice pro úspěšnou zkoušku podle pravidel ECTS: 50 bodů.
| | Podmínky zápočtu: |
|---|
Celkový zisk minimálně 15 bodů z domácích úloh. | | |
|
Fakulta informačních technologií