Analýza datových struktur - NTIN105

• Anglický název: Analysis of data structures
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: zimní
• E-Kredity: 2
• Rozsah, examinace: zimní s.:0/1, Z [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: zrušen
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: Mgr. Martin Mareš, Ph.D.
• Třída: Informatika Mgr. - volitelný
• Kategorizace předmětu: Informatika > Teoretická informatika
• Korekvizity : NTIN066

Anotace

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2018)

Doplňuje cvičení z Datových struktur I (NTIN066) o hlubší partie týkající se teoretické analýzy chování datových struktur.

angličtina

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2018)

Extends the exercise classes for Data Structures I (NTIN066) by deeper theoretical analysis of data structure behavior.

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

čeština

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

Zápočet se uděluje za aktivní účast na semináři. V případě nižší aktivity ji lze nahradit vyřešením zápočtové úlohy.

angličtina

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

Class credit is awarded for active participation in the classes. In cases of insufficient participation, it can be augmented by a final project.

Sylabus

čeština

Poslední úprava: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2018)

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: doc. Mgr. Jan Kynčl, Ph.D. (30.04.2018)

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.