Algoritmy a datové struktury I - NTIN060

• Anglický název: Algorithms and Data Structures I
• Podoba výuky: přednáška+cvičení
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2015 do 2015
• Počet semestrů výuky: 1
• Semestr: letní
• E-Kredity: 5
• Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
• Počet míst: neomezen
• Maximální kapacita předmětu: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Forma uskutečňování: prezenční
• Možnost opakovaného zápisu: 2 / 2 / 2 / 2
• Garant: prof. RNDr. Luděk Kučera, DrSc.; prof. RNDr. Ondřej Čepek, Ph.D.
• Vyučující: RNDr. Jan Bok, Ph.D.; prof. RNDr. Ondřej Čepek, Ph.D.; RNDr. Jan Hric; RNDr. Radek Hušek, Ph.D.; RNDr. Miloš Chromý, Ph.D.; doc. Mgr. Martin Koutecký, Ph.D.; prof. RNDr. Luděk Kučera, DrSc.; RNDr. Petr Kučera, Ph.D.; Mgr. Vladan Majerech, Dr.; Mgr. Jan Musílek
• Třída: Informatika Bc.
• Kategorizace předmětu: Informatika > Teoretická informatika

Anotace

čeština

Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)

angličtina

A course about basic types of algorithms and data structures needed for their implementation.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)

Cíl předmětu

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

Poslední úprava: T_KTI (23.05.2008)

Literatura

• Cormen, Leiserson, Rivest, Stein : Introduction to algorithms (2nd Edition), Mc Graw Hill 2001
• Videozáznamy přednášek

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

Sylabus

čeština

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)

.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)

angličtina

Asymptotic notation.

Tree structures, binary search trees, AVL trees, Red-black trees.

Hashing, solving of collisions, analysis of average case.

Sorting. Analysis of average case for quicksort, randomization. Lower bound for sorting (decision trees), linear-time sorting based on indexing by keys.

Graph algorithms, depth-first search, breadth-first search, strongly connected components, transitive closure, topological sorting.

Extreme paths in graphs. Method of critical path - PERT. Dijkstra alg., Bellman-Ford alg. (searching of negative cycles), Floyd-Warshall alg. for all paths.

Minimal spanning tree. Kruskal alg., Prim-Jarnik alg.

Method Divide and conquer. General schema, solving of recurrent equations. Master theorem. Applications: binary searching, mergesort, Strassen alg.

Eucleid alg., LUP decomposition.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2018)