Složitost I - NTIN062

• Anglický název: Complexity I
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2017
• Semestr: zimní
• E-Kredity: 5
• Rozsah, examinace: zimní s.:2/1, Z+Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: zrušen
• Jazyk výuky: čeština
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: prof. RNDr. Ondřej Čepek, Ph.D.
• Třída: Informatika Mgr. - Teoretická informatika; Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Teoretická informatika
• Záměnnost : NTIN090
• Je korekvizitou pro: NTIN063, NTIX063
• Je neslučitelnost pro: NTIX090, NTIN090
• Je prerekvizitou pro: NTIN023
• Ve slož. záměnnosti pro: NTIN090, NTIX090

Anotace

čeština

Poslední úprava: 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.

angličtina

Poslední úprava: T_KTI (20.04.2004)

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.

Cíl předmětu

Poslední úprava: T_KTI (23.05.2008)

Naučit základy z teorie složitosti algoritmů, včetně NP-úplnosti a převoditelnosti.

Literatura

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

Sylabus

čeština

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.

angličtina

Poslední úprava: 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.