|
|
|
||
Poslední úprava: T_KTI (20.04.2004)
|
|
||
Poslední úprava: T_KTI (23.05.2008)
Naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti. |
|
||
Poslední úprava: prof. RNDr. Ondřej Čepek, Ph.D. (08.04.2004)
L. Kučera: Kombinatorické algoritmy J. Plesník: Grafové algoritmy Cormen, Leiserson, Rivest : Introduction to algorithms, Mc Graw Hill 1990 Kozen : Design and analysis of algorithms, Springer-Verlag 1992 Tarjan : Data structures and network algorithms, SIAM, 1983 Garey, Johnson : Computers and intractability - a guide to the theory of NP-completeness, W.H.Freeman 1978 |
|
||
Poslední úprava: T_KTI (20.04.2004)
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. |