PředmětyPředměty(verze: 877)
Předmět, akademický rok 2020/2021
  
Algoritmy a datové struktury 1 - NTIN060
Anglický název: Algorithms and Data Structures 1
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2019
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: RNDr. Jan Hric
Mgr. Martin Mareš, Ph.D.
Mgr. Jan Hubička, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
N//Je neslučitelnost pro: NPRG062
Anotace -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (01.02.2018)
Úvodní přednáška o základních typech algoritmů a datových strukturách potřebných pro jejich implementaci. Navazuje na výklad v přednášce NPRG062 Algoritmizace v předchozím semestru.
Cíl předmětu
Poslední úprava: T_KTI (23.05.2008)

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

Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Koutecký, Ph.D. (30.04.2020)

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí). Zápočet se uděluje za řešení domácích úkolů a případných dodatečných úkolů na konci semestru. Povaha kontroly podmínek k udělení zápočtu vylučuje možnost jejího opakování, což znamená, že když nenasbíráte dostatek bodů, zápočet nelze získat jinak.

Zkouška se skládá z písemné a ústní části. Písemná část předchází části ústní, její nesplnění znamená, že termín zkoušky je hodnocen známkou nevyhověl(a) a ústní částí se již nepokračuje.

Je pravděpodobné, že se značná část zkoušek či zápočtů může konat distanční formou. Závisí to na vývoji aktuální situace a o jakékoli změně budete včas informováni.

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
Požadavky ke zkoušce -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (02.03.2018)

Je třeba rozumět teorii z přednášky a být schopen ji aplikovat na řešení algoritmických úloh.

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

Volitelná témata v hranatých závorkách, zbytek je povinný.

1. 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
  • výpočetní model RAM
  • asymptotická notace

2. Stromové datové struktury

  • binární vyhledávací stromy
  • AVL stromy
  • (a,b)-stromy
  • [červeno-černé stromy]

3. Hešování

  • popis jednoduchých strategií řešení kolizí
  • analýza průměrné časové složitosti vyhledávání
  • univerzální hešování

4. 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)

5. Základní grafové algoritmy

  • prohledávání do hloubky na neorientovaném grafu, detekce mostů a artikulací
  • prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování

[detekce komponent silné souvislosti v lineárním čase]

6. 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ův-Fordův algoritmus (hledání záporných cyklů)
  • [Floydův-Warshallův algoritmus]

7. Minimální kostra grafu

  • Jarníkův a Borůvkův algoritmus
  • [Kruskalův algoritmus a datová struktura pro Union-Find]

8. Metoda 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í, Merge sort, násobení čísel (Karatsuba-Ofman)
  • složitější aplikace: Strassenovo násobení matic, [hledání mediánu v lin. čase v nejhorším případě]

9. Dynamické programování

  • obecný princip dynamického programování
  • editační vzdálenost řetězců
  • [optimální vyhledávací stromy]

 
Univerzita Karlova | Informační systém UK