Datové struktury I - NTIX066

• Anglický název: Data Structures I
• Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2022
• Semestr: oba
• E-Kredity: 5
• Rozsah, examinace: 2/1, 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
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Další informace: https://ktiml.mff.cuni.cz/~fink/teaching/data_structures_I/
• Poznámka: předmět lze zapsat v ZS i LS
• Garant: RNDr. Jiří Fink, Ph.D.; Mgr. Martin Mareš, Ph.D.; doc. Mgr. Petr Gregor, 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
• Neslučitelnost : NTIN066
• Záměnnost : NTIN066
• Je neslučitelnost pro: NTIN066
• Je záměnnost pro: NTIN066

Anotace

čeština

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.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

angličtina

The basic course about construction of efficient data structures, mandatory for Master's students. Search trees, heaps, hashing. Worst-case, average-case and amortized complexity of data structures. Self-adjusting data structures. Behavior and analysis of data structures on systems with memory hierarchy. The lecture builds on the lectures Algorithms and Data Structures I and II and Programming I and II from the bachelor study.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

Cíl předmětu

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

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

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

čeština

Ke splnění předmětu je nutné získat zápočet a složit zkoušku.

Zápočet se udílí za získání požadovaného počtu bodů za domácí úkoly řešené během semestru. Vzhledem k povaze domácích úkolů nejsou náhradní termíny zápočtu přípustné.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

angličtina

It is necessary to obtain class credit and pass the exam.

Class credit is given for reaching the required number of points for assignments solved during the semester.

The character of the assignments does not allow repeated attempts to obtain credit.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

Literatura

čeština

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

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

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, Berlin, 1984

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

Požadavky ke zkoušce

čeština

Zkouška je ústní s písemnou přípravou. Zkouší se porozumění teorii prezentované na přednášce.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

angličtina

The exam is oral with written preparation. To pass the exam, understanding of material presented at the lecture is required.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

Sylabus

čeština

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.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

angličtina

Trees

• (a,b)-trees and their variants

• Move-to-Front strategy for lists, Splay trees

• other solutions: AVL trees, red-black trees, BB-alpha trees

Heaps

• regular heaps

• binomial heaps

• Fibonacci heaps

Techniques for memory hierarchy

• I/O model, cache-oblivious analysis, LRU strategy for on-line paging

• examples: matrix transposition and multiplication, van Emde-Boas tree layout

• cache-aware techniques

Hashing

• collisions and their resolution, analysis for uniformly distributed data

• selecting a hash function: universal hashing, good hash functions

• cuckoo hashing

Multidimensional data structures

• KD trees

• range trees

Warning: The course will be given since 2018/19 in English only in the summer term (instead of the winter term in previous years) and in Czech only in the winter term.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

Vstupní požadavky

čeština

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

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)

angličtina

Knowledge on the level of the undergraduate Algorithms and data structures.

Poslední úprava: Jedelský Petr, Mgr. (01.03.2021)