Data a datové struktury

Garant předmětu:

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í (povolené jsou 3 absence) a úspěšné zvládnutí zápočtových úloh. První část tvoří test v polovině semestru obsahující teoretickou část cvičení. Druhou povinnou složkou zápočtu je úspěšné vypracování praktické části na danou problematiku (programovací úloha), student následně vypracovanou úlohu prezentuje pro ověření znalostí, autorství a pochopení problematiky.

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:

Povinná literatura (viz. odkazy na začátku stránky):

[1]ČERNÝ, Jakub. Základní grafové algoritmy. V Praze: ČVUT, 2013. ISBN 978-80-01-05258-7.

[2] Mareš Martin, Valla Tomáš. Průvodce labyrintem algoritmů, Edice CZ.NIC. ISBN 978-80-88168-22-5

Doporučená literatura:

[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ů:

• Bakalářská studijní specializace Biomedicínská informatika (povinný předmět)
• Bakalářská studijní specializace Informační a komunikační technologie (povinný předmět)
• Bakalářský studijní program Informatika a kybernetika ve zdravotnictví - společný první ročník (povinný předmět)
• Bakalářská studijní specializace Biomedicínská informatika (povinný předmět)
• Bakalářská studijní specializace Informační a komunikační technologie (povinný předmět)