Datové struktury 1 - NTIN066
Anglický název: Data Structures 1
Zajišťuje: Katedra teoretické informatiky a matematické logiky (32-KTIML)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2020
Semestr: oba
E-Kredity: 6
Rozsah, examinace: 2/2, 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, anglič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: prof. Mgr. Michal Koucký, Ph.D.
RNDr. Jiří Fink, Ph.D.
Mgr. Martin Mareš, 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 : NTIX066
Záměnnost : NTIX066
Je korekvizitou pro: NTIN067, NTIN105
Je neslučitelnost pro: NTIX066
Je záměnnost pro: NTIX066
Výsledky anket   Termíny zkoušek   Rozvrh ZS   Rozvrh LS   Nástěnka   
Anotace -
Základní přednáška o konstrukci efektivních datových struktur. Vyhledávací stromy, hešování, struktury pro práci s řetězci. Analýza nejhoršího, amortizovaného a očekávaného chování datových struktur. Samoupravující se datové struktury. Chování datových struktur na systémech s paměťovou hierarchií. Přednáška volně navazuje na přednášky Algoritmizace, Algoritmy a datové struktury 1 a Algoritmy a datové struktury 2 z bakalářského studia.
Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)
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: T_KTI (25.04.2016)
Podmínky zakončení předmětu -

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: Mareš Martin, Mgr., Ph.D. (15.10.2019)
Literatura -

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: T_KTI (26.04.2016)
Požadavky ke zkoušce -

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

Poslední úprava: Mareš Martin, Mgr., Ph.D. (01.03.2019)
Sylabus -

Stromy

(a,b)-stromy

Splay stromy

BB-α stromy

Hešování

výběr hešovací funkce: univerzální hešování, k-nezávislost

lineární přidávání

kukačkové hešování

Bloomovy filtry

Práce s řetězci

Sufixové stromy

Sufixové pole

Techniky pro paměťovou hierarchii

Paralelní datové struktury

Vícerozměrné datové struktury

K-d stromy

Range trees (intervalové stromy)

Upozornění: Předmět se bude vyučovat v českém jazyce pouze v zimním semestru a v anglickém jazyce pouze v letním semestru.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2019)
Vstupní požadavky -

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

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