Název:

Složitost (v angličtině)

Zkratka:SLOa
Ak.rok:2019/2020
Semestr:letní
Studijní plán:
ProgramObor/
specializace
RočníkPovinnost
IT-MGR-2MBI-volitelný
IT-MGR-2MBS-volitelný
IT-MGR-2MGM-volitelný
IT-MGR-2MGMe-povinně volitelný - skupina M
IT-MGR-2MIN-povinně volitelný - skupina B
IT-MGR-2MIS1.volitelný
IT-MGR-2MMM-povinně volitelný - skupina L
IT-MGR-2MPV-volitelný
IT-MGR-2MSK-volitelný
MITAINADE-volitelný
MITAINBIO-volitelný
MITAINCPS-volitelný
MITAINEMB-volitelný
MITAINGRI-volitelný
MITAINHPC-volitelný
MITAINIDE-volitelný
MITAINISD-volitelný
MITAINISY-volitelný
MITAINMAL-volitelný
MITAINMAT-povinný
MITAINNET-volitelný
MITAINSEC-volitelný
MITAINSEN-volitelný
MITAINSPE-volitelný
MITAINVER-volitelný
MITAINVIZ-volitelný
Vyučovací jazyk:angličtina
Aktuální informace:
This course is instructed in English, and it is intended for incoming Erasmus+ students, too.

Informace pro zapsané:http://www.fit.vutbr.cz/study/courses/SLOa/private/
Kredity:5 kreditů
Ukončení:zkouška (kombinovaná)
Výuka:
hod./sempřednáškasem./cvič.lab. cvič.poč. cvič.jiná
Rozsah:2600026
 zkouškatestycvičenílaboratořeostatní
Body:6800032
Garant:Rogalewicz Adam, doc. Mgr., Ph.D. (UITS)
Zástupce garanta:Vojnar Tomáš, prof. Ing., Ph.D. (UITS)
Přednášející:Rogalewicz Adam, doc. Mgr., Ph.D. (UITS)
Cvičící:Rogalewicz Adam, doc. 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: 
Teoretická informatika (TIN), UITS
Navazující:
Kryptografie (KRY), UITS
Paralelní a distribuované algoritmy (PRL), UITS
Statická analýza a verifikace (SAV), UITS
Nahrazuje:
Vyčíslitelnost a složitost (VSL), UITS
Rozvrh:
DenVýukaTýdenMístnostOdDoPSKSkupiny
PopřednáškavýukyA112 10:0011:501EIT 1MIT 2EIT 2MIT INTE xx
 
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ů.
Proč je předmět vyučován:
  Je důležité si uvědomit, že existují úlohy (často nazývané problémy), které jsou velmi těžko řešitelné pomocí počítačů. Technicky korektní algoritmus pro takovéto těžké úlohy často nemusí fungovat na reálných vstupech. Cílem předmětu je seznámit studenty s teoretickými základy, která stojí za klasifikací úloh na prakticky řešitelné a obecně neřešitelné. Dále pak představuje možnosti řešení těžkých úloh pomocí přibližných a nehodnostních algoritmů stejně tak jako možnosti využití těžkých úloh v rámci kryptografie.
Osnova přednášek:
 
  1. Úvod, Turingovy stroje, složitost časová a prostorová.
  2. Alternativní modely výpočtů, skeletový jazyk, stroje typu RAM, RASP a jejich vztah k Turingovým strojům.
  3. Asymptotické odhady složitosti, třídy složitosti, determinismus a nedeterminismus z pohledu složitosti.
  4. 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.
  5. Blumův teorém. Gap theorem.
  6. Redukovatelnost, pojem úplnosti tříd složitosti, nejběžnější případy úplnosti.
  7. Třídy P a NP a jejich vlastnosti. NP-úplné problémy, problém splnitelnosti a jeho varianty.
  8. Problém obchodního cestujícího, problém batohu a další významné NP-úplné problémy.
  9. NP optimalizační problémy a jejich deterministické řešení: pseudo-polynomiální algoritmy, parametrizovaná složitost.
  10. Aproximační algoritmy, neaproximovatelnost.
  11. Pravděpodobnostní algoritmy a pravděpodobnostní třídy složitosti.
  12. Složitost a kryptografie.
  13. 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
  • Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821
  • 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
  • Papadimitriou, C. H.: Computational Complexity, Addison-Wesley, 1994, ISBN 0201530821
  • Arora, S., Barak, B.: Computational Complexity: A Modern Approach, Cambridge University Press, 2009, ISBN: 0521424267. Dostupné online.
  • 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 projekty - každý za 8 bodů (doporučený minimální zisk z projektů je 15 bodů).
  • Závěrečná zkouška: 68 bodů.
 

Vaše IPv4 adresa: 54.234.208.87