Předmět Algoritmy a výpočetní složitost (KMA / AVS)
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 KMA / AVS - Algoritmy a výpočetní složitost, Fakulta aplikovaných věd, Západočeská univerzita v Plzni (ZČU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
Materiál | Typ | Datum | Počet stažení |
---|
Další informace
Obsah
Výpočetní modelyTuringovy stroje, jazyky a reducibilitaTřídy časové složitosti, třída PTřída NP, struktura třídy NPVýpočetní složitost optimalizačních úloh, aproximovatelnostHierarchie tříd složitostiTřídy paměťové složitostiPravděpodobnostní algoritmy a třídy složitostiInteraktivní důkazové systémy, PCP třídyZáklady Kolmogorovy teorie složitosti
Získané způsobilosti
Úspěšný absolvent získá především pevné formální základy výpočetních modelů a široký přehled tříd výpočetní složitosti. Bude schopen především- odhadnout a dokázat výpočetní složitost (časovou a paměťovou) daného algoritmu,- stanovit aproximovatelnost dané optimalizační úlohy,- převést řešení dané úlohy na řešení úlohy již známé a určit složitost převodu,- rozhodnout o vhodnosti řešení dané úlohy pravděpodobnostním algoritmem.
Literatura
Hromkovič, Juraj. Algorithmics for hard problems : introduction to combinatorial optimization, randomization, approximation, and heuristics. 2nd ed. Berlin : Springer, 2003. ISBN 3-540-44134-4.Sedgewick, Robert; Flajolet, Philippe. An introduction to the analysis of algorithms. Boston : Addison-Wesley, 1996. ISBN 0-201-40009-X.Papadimitriou. Computational Complexity. 1995. Kučera, Luděk. Kombinatorické algoritmy. 2. nezm. vyd. Praha : SNTL, 1989. Fiat, Woeginger (eds.). Online Algorithms. 1998.
Požadavky
Zápočet: písemný testZkouška: jen ústní část, dvě otázky z probírané látky
Garant
Doc. Ing. Roman Čada, Ph.D.
Vyučující
Doc. Ing. Roman Čada, Ph.D.Doc. Ing. Roman Čada, Ph.D.