Předmět Složitost I (NTIN062)
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 NTIN062 - Složitost I, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
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
Naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti.
Sylabus
1. Časová složitost algoritmů a prostředky pro její popis.2. Algoritmy typu Rozděl & Panuj (hledání mediánu v lineárním čase, Strassenův algoritmus na násobení matic), metody řešení rekurentních rovnic popisujících časovou složitost těchto algoritmů.3. Hladové algoritmy na váženém matroidu a jejich aplikace (hledání minimální kostry grafu, rozvrhovací problémy).4. Grafové algoritmy založené na DFS (hledání dvojsouvislých komponent grafu, topologické třídění a hledání silně souvislých komponent orientovaného grafu) a na BFS (hledání planárního separátoru v lineárním čase).5. Dolní odhady složitosti problémů, rozhodovací stromy, dolní odhad pro třídění pomocí porovnávání prvků.6. Amortizovaná složitost, binomiální a Fibonacciho haldy a jejich použití v Dijkstrově algoritmu na hledání nejkratších cest v grafu.7. Formální definice tříd P a NP, polynomiální převoditelnost problémů, pojem NP-úplnosti, příklady NP-úplných problémů, důkazy NP-úplnosti.8. Pseudopolynomiální algoritmy a silná NP-úplnost.9. Početní úlohy, třída #P, #P-úplnost.10.Aproximace NP-těžkých úloh, úplně polynomiální aproximační schémata.
Literatura
L. Kučera: Kombinatorické algoritmy J. Plesník: Grafové algoritmy Cormen, Leiserson, Rivest : Introduction to algorithms, Mc Graw Hill 1990Kozen : Design and analysis of algorithms, Springer-Verlag 1992 Tarjan : Data structures and network algorithms, SIAM, 1983Garey, Johnson : Computers and intractability - a guide to the theory of NP-completeness, W.H.Freeman 1978
Garant
doc. RNDr. Ondřej Čepek, Ph.D.