Předmět Složitost (IA012)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu IA012 - Složitost, Fakulta informatiky, Masarykova univerzita (MU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Teorie výpočetní složitosti zkoumá kvantitativní vlastnosti a limityvýpočetních procesů. Kurs prezentuje strukturu prostoru algoritmickýchproblémů a rozvíjí techniky, které dovolují redukovat hledáníefektivních algoritmů pro celou třídu algoritmických problémů na hledáníefektivní metody pro klíčové algoritmické problémy. Teorie klasifikujeproblémy podle jejich výpočetní složitosti na prakticky zvladatelné anezvladatelné a ukazuje důvody nezvladatelnosti (praktickéneřešitelnosti) problémů. Skoumá se, do jaké míry můžou posunouthranici zvladatelnosti techniky jako randomizace, aproximace aparalelní postupy řešení problémů.
Osnova
Struktura a vlastnosti časových složitostních tříd. Vztahdeterminizmu a nedeterminizmu.Struktura a vlastnosti prostorových složitostních tříd. Vztahdeterminizmu a nedeterminizmu.Nezvladatelné problémy. Nekonečnost hierarchie složitostníchtříd. Polynomiální hierarchie. Relativizace. Neuniformní výpočetnísložitost.Pravděpodobnostní složitostní třídy a jejich struktura.Aproximativní složitostní třídy a neaproximovatelnost.Alternování a hry. Interaktivní protokoly a interaktivnídůkazové systémy.Techniky pro získavaní dolních odhadů složitosti. Kolmogorovskásložitost.Deskriptivní složitost.
Literatura
SCHÖNING, Uwe a Randall PRUIM. Gems of theoretical computer science. Berlin: Springer, 1998. x, 320 s. ISBN 3-540-64425-3. infoSIPSER, Michael. Introduction to the theory of computation. Boston: PWS Publishing Company, 1997. xv, 396 s. ISBN 0-534-94728-X. infoPAPADIMITRIOU, Christos H. Computational complexity. Reading, Mass.: Addison Wesley Longman, 1994. xv, 523 s. ISBN 0-201-53082-1. info
Požadavky
Předpokládá se znalost základních pojmů v rozsahu přednášky IB107 Vyčíslitelnost a složitost.
Garant
prof. RNDr. Mojmír Křetínský, CSc.
Vyučující
prof. RNDr. Ivana Černá, CSc.RNDr. Nikola Beneš, Ph.D.RNDr. Mária Svoreňová