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

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

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.

angličtina

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

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.

Cíl předmětu

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

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

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

čeština

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

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é.

angličtina

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

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.

Literatura

čeština

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

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

angličtina

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

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

Požadavky ke zkoušce

čeština

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

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

angličtina

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

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

Sylabus

čeština

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

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.

angličtina

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

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.

Vstupní požadavky

čeština

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

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

angličtina

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

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