PředmětyPředměty(verze: 807)
Předmět, akademický rok 2017/2018
   Přihlásit přes CAS
Algoritmy a datové struktury I - NTIN060
Anglický název: Algorithms and Data Structures I
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2017
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Garant: Mgr. Martin Mareš, Ph.D.
doc. RNDr. Ondřej Čepek, Ph.D.
Mgr. Jan Hubička, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
Anotace -
Poslední úprava: G_I (24.05.2004)

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.
Cíl předmětu
Poslední úprava: T_KTI (23.05.2008)

Naučit základní datové struktury, algoritmy a metody teoretické informatiky

Literatura
Poslední úprava: RNDr. Jan Hric (03.10.2017)

  • Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001
  • M.Mareš, T.Valla : Průvodce labyrintem algoritmů, CZ.NIC z.s.p.o. Praha 2017, 978-80-88168-19-5, http://pruvodce.ucw.cz/
  • Videozáznamy přednášek
Sylabus -
Poslední úprava: doc. RNDr. Jiří Fiala, Ph.D. (07.06.2016)

Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami:

měření velikosti dat, počet kroků algoritmu jako funkce velikosti dat

asymptotická notace

Stromové datové struktury:

binární vyhledávací stromy

AVL stromy

červeno-černé stromy

volitelně B-stromy

Hašování:

popis jednoduchých strategií řešení kolizí

analýza časové složitosti vyhledávání v průměrném případě

Třídění:

analýza průměrného případu pro Quicksort, randomizovaný Quicksort

dolní odhad složitosti porovnávacích třídících algoritmů (rozhodovací stromy)

třídění v lineárním čase na základě adresování pomocí klíčů (víceprůchodové pro znakové klíče)

Základní grafové algoritmy:

prohledávání do hloubky a do šířky na neorientovaném grafu

detekce souvislých a silně souvislých komponent

prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování

Extremální cesty v grafech:

extremální cesty v acyklickém orientovaném grafu, metoda kritické cesty

Dijkstrův algoritmus (zopakování binární haldy, srovnání implementace polem a binární haldou)

Bellman-Fordův algoritmus (hledání záporných cyklů)

volitelně Floyd-Warshallův algoritmus

Minimální kostra grafu:

algoritmus Borůvka-Kruskal

algoritmus Jarník-Prim

volitelně popis pomocí vážených matroidů

Algoritmy rozděl a panuj:

obecné schéma algoritmů typu rozděl a panuj, souvislost jejich složitosti s rekurentními rovnicemi

substituční metoda řešení rekurentních rovnic a "master theorem (kuchařka)"

jednoduché aplikace: binární vyhledávání a mergersort

složitější aplikace: Strassenovo násobení matic, volitelně hledání mediánu v lin. čase v nejhorším případě

Algoritmy lineární algebry:

Euklidův algoritmus

LUP dekompozice matic a její využití

volitelně vlastní čísla a vektory - numerický výpočet, aplikace (Google PageRank, minimální řez grafu)

.

 
Univerzita Karlova | Informační systém UK