Jak Začít?

Máš v počítači zápisky z přednášek
nebo jiné materiály ze školy?

Nahraj je na studentino.cz a získej
4 Kč za každý materiál
a 50 Kč za registraci!




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.