Předmět Algoritmy a datové struktury I (NTIN060)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu NTIN060 - Algoritmy a datové struktury I, Matematicko-fyzikální fakulta, Univerzita Karlova v Praze (UK).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Naučit základní datové struktury, algoritmy a metody teoretické informatiky
Sylabus
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 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) .
Literatura
Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001 Videozáznamy přednášek
Garant
prof. RNDr. Luděk Kučera, DrSc.doc. RNDr. Ondřej Čepek, Ph.D.