Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Data a datové struktury

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
17PBIDDS Z,ZK 5 2P+2C česky
Přednášející:
Cvičící:
Předmět zajišťuje:
katedra biomedicínské informatiky
Anotace:

Přehled základních datových struktur a jejich použití. Specifikace abstraktních datových typů (ADT). Specifikace a implementace ADT: seznamy, zásobník, fronta, množina, pole, vyhledávací tabulka, graf, binární strom. Dynamické datové struktury a operace s nimi (efektivní vyhledávání, třídění, ukládání datových struktur atd.). Reprezentace datových struktur, strategie pro volbu vhodné datové struktury.

Požadavky:

U zkoušky budou 4 příklady. 3 příklady budou z látky odpřednášené mgr. Krupičkou a 1 příklad z látky odpřednášené dr. Kaulerem.

Každý příklad bude hodnocen 0-25 body. Celkového hodnocení podle stupnice ECTS. Příklady budou početní, případně „kreslící“, ale ne teoretické. Na zkoušku je 1 hodina (60 minut). Ke zkoušce jsou povoleny papíry, propiska/tužka, případně jednoduchá kalkulačka.

Bližší informace o zkoušce můžete najít níže na stránce předmětu.

Podmínky zápočtu jsou absolvování všech cvičení (maximálně 3 omluvené absence) a úspěšné zvládnutí dvou testů (v půlce a na konci semestru) každý minimálně na 50%. Druhý test může být nahrazený zápočtovou úlohou.

Osnova přednášek:

1. Základní pojmy a označení (přirozená čísla, množiny, matematická indukce, relace, relace ekvivalence, funkce, uspořádané množiny).

2. Míry složitosti. Prostředky pro popis složitosti algoritmů a operací nad datovými strukturami. Složitost problémů.

3. Úvod do teorie grafu. Prohledávání do hloubky a do šířky na neorientovaném grafu detekce souvislých komponent, prohledávání do hloubky na orientovaném grafu, tranzitivní uzávěr, topologické číslování.

4. Rovinné kreslení grafů. Počet koster úplného grafu. Nezávislost grafu.

5. Stromy - definice základních pojmů a charakteristika (isomorfismus, kostra grafu, problém minimální kostry, algoritmy na hledání minimální kostry).

6. Stromové datové struktury:haldy, binární vyhledávací stromy, AVL stromy, červeno-černé stromy, operace nad nimi (operace MEMBER, INSERT, DELETE, JOIN, SPLIT)

7. B-stromy, haldy, Fibonacciho haldy. B*-stromy, (a,b)-stromy. Srovnání paralelního přístupu pomocí B-stromů a (a,b)-stromů. Propojení s hardware.

8. Třídění polí - bubble sort, heap sort quicksort, mergsort, hledání k-tého prvku. Vyhledávání v uspořádaném poli.

9. Algoritmy rozděl a panuj (binární vyhledávání a merge sort, hledání mediánu v lineárním čase)

10. Hašování - definice a použití. Univerzální hašování, jeho vlastnosti a způsob jeho použití. Návrh perfektního hašování.

11. Kódování, komprese. Samoopravitelné kódy.

12. Šifrování - symetrická, asymetrická šifra - šifrování s otevřeným klíčem (RSA šifra) volitelně DES a podobné algoritmy a další kryptografické protokoly.

13. Logické a fyzické schéma souboru, logický a fyzický záznam. Kódování a komprese dat. Ukládání dat na fyzické zařízení. Popis hardwaru.

14. Základní databázové operace. Jazyk SQL.

Osnova cvičení:

1. Základní definice, kombinatorické počítání.

2. Automaty

3. Míra složitosti. Ukázky a počítání složitosti algoritmů.

4. Ukázky grafových algoritmů.

5. Kreslení grafů, počet koster. Rovinné grafy.

6. Stromy

7. Zápočtový test

8. Implementace stromové datové struktury

9. Operace nad stromy Insert, member, delete, join.

10. Implementace algoritmů pro třídění dat.

11. Vyhledávání v datové struktuře.

12. Vyhledávání v souboru.

13. Ukázka a implementace hašování

14. 2. zápočtový test.

Cíle studia:
Studijní materiály:

[1] J. Pokorný, I. Halaška: Databázové systémy, skriptum FEL ČVUT, 2. vyd., Praha, Vydavatelství ČVUT, 2003. 148 s. ISBN 80-01-02789-9.

[2] Piotr Wroblewski: Algoritmy, Datové struktury a programovací techniky, Computer Press, 2005

[3] Marc DeLisle: phpMyAdmin - efektivní správa MySQL, Zoner Press, 2004

[4] Thomas Erl: SOA Servisně orientovaná architektura, Computer Press, 2009

Poznámka:
Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 18. 10. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet2789206.html