Data a datové struktury

Přednášející:

Radim Krupička, Marcel Jiřina (gar.), Jan Kauler

Cvičící:

Radim Krupička

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. 2 příklady budou z látky odpřednášené doc. Jiřinou, 1 příklad 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%.

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. Míra složitosti. Ukázky a počítání složitosti algoritmů.

3. Ukázky grafových algoritmů.

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

5. 1. Zápočtový test

6. Pole, struktury, ukazatele v jazyku C.

7. Implementace stromové datové struktury

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

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

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

11. Vyhledávání v souboru.

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

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

14. Zápočet

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:

Rozvrh na zimní semestr 2011/2012:

Rozvrh není připraven

Rozvrh na letní semestr 2011/2012:

	06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po
Út
St	místnost KL:B-505 Krupička R. 10:00–11:50 (přednášková par. 1 paralelka 1) Kladno FBMI Počítačová učebnamístnost KL:B-505 Krupička R. 12:00–13:50 (přednášková par. 1 paralelka 2) Kladno FBMI Počítačová učebnamístnost KL:B-415 Jiřina M. Kauler J. 14:00–15:50 (přednášková par. 1) Kladno FBMI Počítačová učebna
Čt
Pá

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

• Bakalářský studijní obor Biomedicínská informatika - prezenční (povinný předmět)
• Bakalářský studijní obor Biomedicínská informatika - prezenční (povinný předmět)