PředmětyPředměty(verze: 945)
Předmět, akademický rok 2023/2024
   Přihlásit přes CAS
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 2021
Semestr: letní
E-Kredity: 5
Rozsah, examinace: letní s.:2/2, Z+Zk [HT]
Počet míst: 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
Způsob výuky: prezenční
Způsob výuky: prezenční
Garant: prof. RNDr. Ondřej Čepek, Ph.D.
Mgr. Martin Mareš, Ph.D.
doc. Mgr. Jan Hubička, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Teoretická informatika
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 Mareš, Ph.D. (06.02.2023)

Je třeba získat zápočet a složit zkoušku (v libovolném pořadí).

Pro zápočet je třeba získat 100 bodů z alespoň 150 možných udělovaných průběžně za řešení domácích úloh, písemné testy a další aktivity. Z průběžné povahy kontroly neplyne nárok na vypisování opravných termínů testů ani zadání náhradních domácích úloh.

V důvodných případech (dlouhodobá nemoc, pobyt v zahraničí, apod.) může cvičící stanovit individuální podmínky na udělení zápočtu.

Zkouška může být písemná, ústní nebo kombinovaná. Zkouška může mít kontaktní nebo distanční formu. Formu zkoušky určuje vyučující.

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: RNDr. Jan Hric (13.05.2022)

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