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
F7PBKDDS Z,ZK 5 2P+2C česky
Přednášející:
Radim Krupička (gar.)
Cvičící:
Radim Krupička (gar.)
Předmět zajišťuje:
katedra biomedicínské informatiky
Anotace:

Cílem předmětu je seznámit studenty se základními datovými strukturami a jejich použití. Před popisem datových struktur studenti získají základní znalosti diskrétní matematiky, složitosti, automatů a grafových algoritmů, které následně využijí k popisu datových struktur a algoritmů pro práce s nimi. Z datových struktur budou probrány: 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í, hašování, ukládání datových struktur atd.). Reprezentace datových struktur, strategie pro volbu vhodné datové struktury, jejich kódování komprese a ukládání.

Požadavky:

Pro získání zápočtu budou potřeba 2 zápočtové testy. První test bude v půlce semestru z příkladů řešených na papíře, druhý test bude praktický, programovací. Druhý test bude možné nahradit zápočtovou úlohou. Zkouška bude písemná s ústním dozkoušením.

Osnova přednášek:

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í:

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. Hledání toku v síti a nejkratší cesty.

7. Stromy, BVS, AVL, haldy

8. Zápočtový test

9. Implementace zásobníků fronty

10. Prohledávání do šířky, do hloubky

11. Implementace stromové struktury

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

13. Vyhledávání v datové struktuře, hašování

14. 2. zápočtový test

Cíle studia:
Studijní materiály:

Povinná literatura:

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

Doporučená literatura:

[1]WRÓBLEWSKI, Piotr. Algoritmy: datové struktury a programovací techniky. Přeložil Marek MICHÁLEK, přeložil Bogdan KISZKA. Brno: Computer Press, 2004. ISBN 80-251-0343-9.

[2]RYANT, Ivan. Algoritmy a datové struktury objektově. V Praze: Ivan Ryant, 2017. ISBN 978-80-270-1660-0.

[3]VIRIUS, Miroslav. Základy algoritmizace. [1. verze pro screenreader]. Česká republika: [Centrum TEREZA], 2010

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 15. 10. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet5956206.html