This is a basic course on the complexity of algorithms. Roughly the first half of the course is devoted to the study of concrete algorithms of various types (graph algorithms, divide and conquer algorithms, greedy algorithms) which work in polynomial time. The time complexity is analyzed both "classically" (worst case analysis) and in an amortized manner. The second half of the course is then devoted to the study of the NP class, polynomial reducibility among problems, and NP-completeness proofs for various problems. The course concludes with several topics related to NP-completeness.
Last update: T_KTI (20.04.2004)
Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Aim of the course - Czech
Last update: T_KTI (23.05.2008)
Naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti.
Literature - Czech
Last update: 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
Syllabus -
Last update: T_KTI (20.04.2004)
1. Time complexity of algorithms, asymptotic notation.
2. Divide and conquer algorithms (linear time median algorithm, Strassen's matrix multiplication), methods for solving recursive equations which describe the complexity of such algorithms.
3. Greedy algorithms on weighted matriods, their applications (minimum spanning tree, scheduling problems).
4. Graph algorithms based on DFS and BFS.
5. Lower bounds for time complexity of problems, decision trees, lower bound for sorting by comparisons.
6. Amortized complexity, binomial and Fibonacci heaps and their application in Dijkstra's algorithm.
7. Formal definitions of classes P and NP, polynomial reducibility among decision problems, NP-completeness.
8. Pseudopolynomial algorithms and strong NP-completeness.
9. Counting problems, class #P, #P-completeness.
10.Approximations of NP-hard problems, completely polynomial approximation schemes.
Last update: 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.
