PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Datové struktury II - NTIN067
Anglický název: Data Structures II
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016 do 2016
Semestr: letní
E-Kredity: 3
Rozsah, examinace: letní s.:2/0 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
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. - Matematická lingvistika
Informatika Mgr. - Diskrétní modely a algoritmy
Kategorizace předmětu: Informatika > Teoretická informatika
Korekvizity : NTIN066
Anotace -
Poslední úprava: T_KTI (25.04.2016)

Přednáška navazuje na přednášku NTIN066 Datové struktury I. Bude věnována pokročilejším technikám návrhu a analýzy datových struktur: deterministická reprezentace statických množin, datové struktury pro celočíselné universum, základní grafové datové struktury, dynamické cache-oblivious vyhledávací stromy, dynamizace a persistence, úsporné datové struktury, výpočty v proudovém modelu.
Cíl předmětu
Poslední úprava: T_KTI (25.04.2016)

Naučit pokročilejší datové struktury a metody jejich návrhu a analýzy.

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

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

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

Učební text na webové stránce KTIML

Sylabus -
Poslední úprava: T_KTI (25.04.2016)

Statické slovníky:

• perfektní hešování FKS

• deterministické slovníky (Hagerup, Miltersen, Pagh)

• redukce universa

Celočíselné datové struktury:

• van Emde-Boasovy stromy

• x-fast a y-fast stromy

• Fusion trees

Grafové datové struktury:

• dekompozice stromů na lehké a těžké hrany

• aktualizace cest pomocí líného vyhodnocování

• Link-Cut stromy (Sleator, Tarjan)

• inkrementální komponenty souvislosti (Union-Find)

Obecné techniky transformace struktur:

• semidynamizace a dynamizace

• persistence

Cache-oblivious struktury:

• Ordered File Maintenance

• B-stromy

Úsporné datové struktury:

• řetězce nad nebinární abecedou

• úsporná reprezentace stromů

Výpočty v proudovém modelu:

• deterministické hledání častých prvků

• randomizované hledání častých prvků

• odhad počtu různých prvků

 
Univerzita Karlova | Informační systém UK