Datové struktury 2 - NTIN067

• Anglický název: Data Structures 2
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: letní
• E-Kredity: 3
• Rozsah, examinace: letní s.:2/0, 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
• Způsob výuky: prezenční
• Garant: RNDr. Jiří Fink, 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

čeština

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.

Poslední úprava: T_KTI (25.04.2016)

angličtina

This course extends NTIN066 Data Structures I. It covers more advanced techniques of design and analysis of data structures: deterministic representation of static sets, data structures for integers, basic data structures for graphs, dynamic cache-oblivious search trees, dynamization, persistence, succinct data structures, computation in stream model.

Poslední úprava: T_KTI (25.04.2016)

Cíl předmětu

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

Poslední úprava: T_KTI (25.04.2016)

Podmínky zakončení předmětu

Předmět je zakončen zkouškou, u níž se ověřuje porozumění látce z přednášky a schopnost aplikovat ji na řešení obdobných problémů.

Poslední úprava: Mareš Martin, Mgr., Ph.D. (02.03.2018)

Literatura

čeština

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

Poslední úprava: T_KTI (26.04.2016)

angličtina

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

Poslední úprava: T_KTI (26.04.2016)

Sylabus

čeština

Statické slovníky:

• perfektní hešování FKS

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

Celočíselné datové struktury:

• van Emde-Boasovy stromy

• x-fast a y-fast stromy

Haldy:

• binomiální haldy

• Fibonacciho haldy

Splay stromy:

• vážená analýza

• working set bound

• statická a dynamická optimalita

Grafové datové struktury:

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

• Link-Cut stromy (Sleator, Tarjan)

Obecné techniky transformace struktur:

• semidynamizace a dynamizace

• persistence

Cache-oblivious struktury:

• van Emde-Boasovské uložení binárních stromů

• Ordered File Maintenance

• cache-oblivious 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ů

Poslední úprava: Hric Jan, RNDr. (10.05.2024)

angličtina

Static dictionaries:

• FKS perfect hashing

• deterministic dictionaries (Hagerup, Miltersen, Pagh)

• reduction of universe

Integer data structures:

• van Emde-Boas trees

• x-fast a y-fast trees

• Fusion trees

Graph data structures:

• heavy-light decomposition of trees

• path updates based on lazy evaluation

• Link-Cut trees (Sleator, Tarjan)

• incremental connectivity (Union-Find)

General transforms of data structures:

• semidynamization and dynamization

• persistence

Cache-oblivious structures:

• Ordered File Maintenance

• B-trees

Succinct data structures:

• strings over non-binary alphabets

• succinct representation of trees

Computation in stream model:

• determinisitic search for frequent elements

• randomized search for frequent elements

• estimating the number of distinct elements

Poslední úprava: T_KTI (25.04.2016)