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

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í:
Cvičící:
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 rekurze

10. Implemetace zásobníku,fronty

11. Implementace spojového seznamu

12. Implementace binárního vyhledávacího stromu

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

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.

[2] Mareš Martin, Valla Tomáš. Průvodce labyrintem algoritmů, Edice CZ.NIC. ISBN 978-80-88168-22-5 https://knihy.nic.cz/files/edice/pruvodce_labyrintem_algoritmu.pdf

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