PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   Přihlásit přes CAS
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 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: ne
Stav předmětu: zrušen
Jazyk výuky: čeština
Způsob výuky: prezenční
Garant: doc. 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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
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.
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: doc. 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 -
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.

 
Univerzita Karlova | Informační systém UK