Datové struktury

Garant předmětu:

Michal Opler

Přednášející:

Radek Hušek, Michal Opler

Cvičící:

Radek Hušek, Michal Opler

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Předmět představuje pokročilejší datové struktury včetně analýzy jejich složitosti.

Požadavky:

Předpokládáme, že student ovládá základní znalosti algoritmizace (které si mohl osvojit v předmětech BI-PA1 a BI-PA2) a teorie grafů (BI-AG1: Algoritmy a grafy 1). Výhodou je, pokud student absolvoval nebo souběžně absolvuje kurz Algoritmy a grafy 2 (BI-AG2), ale není to podmínkou.

Osnova přednášek:

1. (a,b)-stromy a červeno-černé stromy

2. Persistentní varianty stromů a jejich motivace

3. List labelling

4. Úvod do randomizovaných struktur: treapy

5. Hešování I: systémy funkcí

6. Hešování II: analýza lineárního přidávání

7. Hešování III : Bloomovy filtr

8. Binomiální haldy

9. Fibonacciho haldy

10. Počítání bodů v rovině (2D range trees)

11. Heavy-light dekompozice

12. Vyhledávání v textu

13. Rezerva (dynamizace datových struktur)

Osnova cvičení:

Cvičení sestává z řešení zadaných úloh na témata probíraná na přednáškách.

Cíle studia:

Studijní materiály:

- Martin Mareš, Tomáš Valla: Průvodce labyrintem algoritmů, CZ.NIC, 2017

- 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

- T. H. Cormen, C.E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. Third edition, MIT Press, 2009.

- Martin Mareš: Lecture notes on data structures. Dostupné online z https://mj.ucw.cz/vyuka/dsnotes/

- Mikkel Thorup: Lecture Notes on Linear Probing with 5-Independent Hashing, 2015. Dostupné online z https://arxiv.org/abs/1509.04549

- Mikkel Thorup: High Speed Hashing for Integers and Strings, 2015. Dostupné online z https://arxiv.org/abs/1504.06804

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/BI-DAS/

Další informace:

https://courses.fit.cvut.cz/BI-DAS/

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů:

• Bc. specializace Informační bezpečnost, 2021 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2021 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2021 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2021 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2021 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2021 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2021 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2021 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2021 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2021 (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Bc. specializace Informační bezpečnost, 2024 (volitelný předmět)
• Bc. program, pro fázi studia bez specializace, 2024 (volitelný předmět)
• Bc. specializace Manažerská informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika, 2024 (volitelný předmět)
• Bc. specializace Softwarové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Webové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové sítě a Internet, 2024 (volitelný předmět)
• Bc. specializace Počítačové inženýrství, 2024 (volitelný předmět)
• Bc. specializace Počítačové systémy a virtualizace, 2024 (volitelný předmět)
• Bc. specializace Umělá inteligence, 2024 (volitelný předmět)
• Bc. specializace Teoretická informatika, 2024 (volitelný předmět)
• Bc. specializace Počítačová grafika s vynecháním BI-SVZ (volitelný předmět)