PředmětyPředměty(verze: 845)
Předmět, akademický rok 2018/2019
   Přihlásit přes CAS
Analýza datových struktur - NTIN105
Anglický název: Analysis of data structures
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2018 do 2018
Semestr: oba
E-Kredity: 2
Rozsah, examinace: 0/1 Z [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í
Poznámka: předmět lze zapsat v ZS i LS
Garant: Mgr. Martin Mareš, Ph.D.
Třída: Informatika Mgr. - volitelný
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN066
Anotace -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (30.04.2018)
Doplňuje cvičení z Datových struktur I (NTIN066) o hlubší partie týkající se teoretické analýzy chování datových struktur.
Podmínky zakončení předmětu -
Poslední úprava: Mgr. Martin Mareš, Ph.D. (15.10.2018)

Zápočet se uděluje za aktivní účast na semináři. V případě nižší aktivity ji lze nahradit vyřešením zápočtové úlohy.

Sylabus -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (30.04.2018)

Haldy

• regulární halda

• binomiální halda

• Fibonacciho halda

Stromy

• (a,b)-stromy a jejich varianty

• strategie Move-to-Front pro seznamy, Splay stromy

• přehled ostatních řešení: AVL stromy, červeno-černé stromy, BB-α stromy

Techniky pro paměťovou hierarchii

• I/O model, cache-oblivious analýza, strategie LRU pro on-line stránkování

• příklady: transpozice a násobení matic, van Emde-Boasovo rozložení vyhledávacích stromů

• cache-aware techniky

Hašování

• řešení kolizí, analýza pro uniformně rozdělená data

• výběr hešovací funkce: univerzální hešování a dobré hešovací funkce

• kukačkové hešování

Vícerozměrné datové struktury

• KD stromy

• range trees (intervalové stromy)

Upozornění: Předmět se bude vyučovat od 2018/19 v českém jazyce pouze v zimním semestru a v anglickém jazyce pouze v letním semestru.

 
Univerzita Karlova | Informační systém UK