Datové struktury I (NTIN066)
Zimní semestr 2026/27 · 2/2 Z + Zk
The English version of this course is taught in the summer semester. Do not enroll in this course in the winter semester.
Přehled
Data Structures I je zásadním kurzem teoretické informatiky zaměřeným na analýzu, návrh a implementaci datových struktur operujících v hlavní paměti. Kurz pokrývá vyhledávací stromy, hešování, sufixová pole a datové struktury v paměťové hierarchii.
Výuka
Přednáška
| Termín | Místnost | Čas |
|---|---|---|
| Úterý | S3 | 14:00 – 15:30 |
Cvičení
Kurz obsahuje paralelní praktika vedená následujícím týmem:
| Cvičící | Den | Čas | Místnost |
|---|---|---|---|
| Jirka Fink | Úterý | 14:00 | S3 |
| Pondělí | 10:40 | S10 | |
| Čtvrtek | 12:20 | S7 | |
| Čtvrtek | 14:00 | S7 | |
| Pavel Veselý | Středa | 9:00 | S1 |
| Petr Chmel | Pátek | 9:00 | S1 |
| Tomáš Domes | Čtvrtek | 15:40 | S6 |
Sylabus přednášek
(Časový rozvrh bude aktualizován v průběhu semestru. Přednáška 17. 11. odpadá — státní svátek.)
- R. E. Tarjan — pozvaná přednáška (Matematické kolokvium) (29. 9.)
- Úvod, amortizovaná složitost a BB[α]-stromy (6. 10.) slide handout
- Splay stromy (13. 10.) slide handout
- (a,b)-stromy, B-stromy, Paměťová hierarchie (20. 10.)
- Cache-oblivious algoritmy a stránkovací strategie (LRU vs. OPT) (27. 10.)
- Úvod do hešování, výběr hešovací funkce (3. 11.)
- Další hešovací funkce (10. 11.)
- Kolize: separované řetězce, otevřená adresace (24. 11.)
- Kukaččí hešování, Bloomovy filtry (1. 12.)
- Sufixová pole (8. 12.)
- Geometrické datové struktury (15. 12.)
- Paralelní datové struktury (5. 1.)
Podmínky zápočtu
Zápočet se uděluje za vypracování domácích úkolů:
- 7 programovacích úkolů × 10 bodů
- 3 experimentální úkoly × 15 bodů
- Podmínka: Celkem min. 75 bodů
Pravidla a další informace najdete na gitu
Materiály a odevzdávání:
Zkouška
Ústní zkouška s písemnou přípravou. Termíny a registrace jsou v SISu.
Zkontrolujte si den před zkouškou čas příchodu, protože SIS mění harmonogram podle aktuálního počtu přihlášených studentů.
Literatura
- M. Mareš. Lecture notes on data structures. 2019. （základní text）
- M. Mareš, T. Valla. Průvodce labyrintem algoritmů. CZ.NIC, 2017. ISBN 978-80-88168-07-1.
- A. Koubková, V. Koubek. Datové struktury I. MATFYZPRESS, 2011.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (3rd ed.). MIT Press, 2009.
- K. Mehlhorn. Data Structures and Algorithms I: Sorting and Searching. Springer, 1984.
- M. Thorup. High Speed Hashing for Integers and Strings. 2014.
Doplňující zdroje
- Stránky Martina Mareše — materiály a videa přednášek
- Stránky Pavla Veselého — materiály a videa přednášek
- Stránky Michala Kouckého
- Videa Petra Gregora na UK Stream
Vstupní předpoklady
Předpokládá se znalost:
- Programování: Python nebo C/C++, ladění
- Algoritmy: Základní datové struktury (zásobník, fronta, halda), třídění
- Pravděpodobnost: diskrétní pravděpodobnost
- Architektura: Základy počítačových systémů
Pokud trávíte hodně času laděním programů, doporučuji souběžně absolvovat Implementace datových struktur (NTIN106) — pokročilé techniky efektivní implementace.