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.
• Vyučující: RNDr. Jiří Fink, Ph.D.; doc. Mgr. Petr Gregor, Ph.D.; Mgr. Petr Chmel; RNDr. David Mareček, Ph.D.; Mgr. Martin Mareš, Ph.D.; Mgr. Lukáš Ondráček; Mgr. Pavel Veselý, 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

Anotace

čeština

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)

angličtina

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

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)

Cíl předmětu

čeština

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)

angličtina

The course should provide a student with a deeper understanding of data structures and their behaviour on real computers.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)

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

angličtina

One has to get a passing grade from the tutorials before comming for an exam. To get a passing grade from the tutorials one has to earn sufficient

amount of points from the homeworks. Due to the specifics of the homeworks no make-ups are possible.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)

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

Poslední úprava: T_KTI (26.04.2016)

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

angličtina

Knowledge and understanding of the material covered during the class.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (14.01.2019)

Sylabus

čeština

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)

angličtina

Trees

(a,b)-trees

Splay trees

BB-α trees

Hashing

Choice of hash functions: universal hash functions, k-indepenence

Linear probing

Cuckoo hashing

Bloom filter

Text data structures

Suffix tree

Suffix array

Techniques for memory hierarchy

Parallel data structures

Multidimensional data structures

K-d trees

Range trees

Warning: The course is offered in English only in the summer term and in Czech only in the winter term.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (01.02.2019)

Vstupní požadavky

čeština

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

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

angličtina

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

Notice that Czech lectures and tutorials are in winter semesters while English lectures and tutorials are in summer semesters only.

Poslední úprava: Fink Jiří, RNDr., Ph.D. (20.09.2022)