PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Datové struktury I - NTIN066
Anglický název: Data Structures I
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016 do 2016
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/1 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. Jiří Fink, Ph.D.
doc. Mgr. Michal Koucký, Ph.D.
Mgr. Martin Mareš, Ph.D.
Třída: Informatika Mgr. - Teoretická informatika
Informatika Mgr. - Softwarové systémy
Informatika Mgr. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Teoretická informatika
Je korekvizitou pro: NTIN067
Anotace -
Poslední úprava: T_KTI (25.04.2016)

Základní přednáška o konstrukci efektivních datových struktur. Vyhledávací stromy, haldy, hešování. Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové struktury. Chování a analýza datových struktur na systémech s paměťovou hierarchií. Přednáška volně navazuje na Algoritmy a datové struktury I a II a Programování I a II bakalářského studia.
Cíl předmětu
Poslední úprava: T_KTI (25.04.2016)

Naučit pokročilejší datové struktury včetně teoretické analýzy a experimentů s chováním na reálných počítačích.

Literatura -
Poslední úprava: T_KTI (26.04.2016)

D. P. Mehta, S. Sahni eds.: Handbook of Data Structures and Applications. Chapman & Hall/CRC, Computer and Information Series, 2005

A. Koubková, V. Koubek: Datové struktury I. MATFYZPRESS, Praha 2011

K. Mehlhorn: Data Structures and Algorithms I: Sorting and Searching. Springer-Verlag, Berlin, 1984

Sylabus -
Poslední úprava: T_KTI (25.04.2016)

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)

Vstupní požadavky -
Poslední úprava: T_KTI (28.04.2015)

Predpoklady: Znalosti na úrovni bakalářské přednášky Algoritmy a datové struktury.

 
Univerzita Karlova | Informační systém UK