|
Vyučující
|
-
Fikejz Jan, Ing. Ph.D.
-
Novotný Radek, Ing. Ph.D.
|
|
Obsah předmětu
|
Program přednášek: 1. Principy kódování řetězců (Huffmanovo kódování, LZ-kódování) 2. Algoritmy vyhledávání řetězců v bázových textech (KMP-algoritmus, vyhledávání pomocí konečného stavového automatu, Karp-Rabin algoritmus) 3. Znakový strom - statické a dynamické implementace 4. Haldově uspořádané struktury (binární, binomická, Fibonacciho a párová halda) 5. Implementace tabulek s využitím binárních vyhledávacích stromů (AVL-strom, treap, splay-strom) 6. Implementace tabulek s využitím k-cestných vyhledávacích stromů (2-3 strom, (a,b)-strom, B-strom) 7. Analýza složitosti algoritmů a používání heuristik v datových strukturách (amortizační analýza, analýza nejhoršího případu, move-to-front a transpoziční heuristika) 8. Organizace a zpracování souborů - fyzické vlastnosti externích paměťových médií 9. Sekvenční soubory a soubory s přímým přístupem 10. Neutříděný soubor s přímým přístupem a hashovaní soubor 11. Souvislý utříděný soubor a indexsekveční soubor 12. Hierarchická organizace indexových souborů (B+ strom) 13. Soubory s úplným/hustým indexem Program cvičení: 1. Zadání semestrální práce A, rozbor implementačních možností. 2. Rozpracování koncepce sem. práce A pomocí UML, samostatné práce studentů na implementaci semestrální práce A. 3. Průběžná individuální kontrola dílčí iterace vývoje sem. práce A. 4. Průběžná individuální kontrola dílčí iterace vývoje sem. práce A. 5. Zadání semestrální práce B, rozbor implementačních možností, individuální obhajoby sem. práce A. 6. Rozpracování koncepce sem. práce B pomocí UML, samostatná práce studentů na implementaci semestrální práce B, individuální, obhajoby sem. práce A. 7. Průběžná individuální kontrola dílčí iterace vývoje sem. práce B. 8. Průběžná individuální kontrola dílčí iterace vývoje sem. práce B. 9. Zadání semestrální práce C, rozbor implementačních možností, individuální obhajoby sem. práce B. 10. Rozpracování koncepce sem. práce C pomocí UML, samostatné práce studentů na implementaci semestrální práce C, individuální obhajoby sem. práce B. 11. Průběžná individuální kontrola dílčí iterace vývoje sem. práce C. 12. Potenciální zadání nepovinné semestrální práce D, rozbor implementačních možností, individuální obhajoby sem. práce C. 13. Individuální obhajoby semestrální práce C a potenciálně i D.
|
|
Studijní aktivity a metody výuky
|
Monologická (výklad, přednáška, instruktáž), Dialogická (diskuze, rozhovor, brainstorming), Nácvik dovedností
- Kontaktní výuka
- 52 hodin za semestr
- Semestrální práce
- 45 hodin za semestr
- Domácí příprava na výuku
- 20 hodin za semestr
- Příprava na zkoušku
- 33 hodin za semestr
|
|
Výstupy z učení
|
Cílem předmětu je studenty seznámit s teoretickými principy pokročilých datových struktur a s nimi spojených algoritmů, jejichž uplatňování je nezbytné při navrhování a implementaci efektivních softwarových aplikací.
Absolvováním předmětu jsou získány informace o pokročilých datových strukturách, jejich aplikacích a efektivních implementacích, což podporuje navrhování a tvorbu kvalitních softwarových produktů.
|
|
Předpoklady
|
Předpokládají se znalosti základních abstraktních datových struktur, jejich aplikací a efektivních implementací.
|
|
Hodnoticí metody a kritéria
|
Ústní zkouška, Písemná zkouška, Posouzení zadané práce
Podmínkou k udělení zápočtu je úspěšné zpracování semestrálních prací (implementace vybraných datových struktur). Student získává za zpracování každé semetrální práce příslušný bodový zisk. Minimální počet bodů k získání zápočtu je 9. Maximální bodové ohodnocení jednotlivých semestrálních prací a termíny jejich nejpozdějšího možného odevzdání v semestru je uvedeno v materiálech k 1. přednášce. Zkouška z předmětu má dvě části. V písemné části student písemně odpovídá na 4 teoretické otázky, v rámci ústní části student odpovídá na doplňující otázky souvisejícími s písemně zpracovanými otázkami. Pro úspěšné složení zkoušky je potřebné dobře zodpovědět minimálně 2/3 všech otázek.
|
|
Doporučená literatura
|
-
Cenek, P., Klima, V., Janáček, J. Optimalizace dopravních a spojových procesů. Žilina, 1994.
-
Cormen, Thomas H. Introduction to algorithms. Cambridge, Mass.: Massachusetts Institute of Technology, 2001. ISBN 0-262-53196-8.
-
Lewis, H. R., Denenberg, L. Data structures and their algorithms. Berkley: Adison-Wesley, 1997. ISBN 978-0673397362.
-
Wirth, N. Algoritmy a štruktúry údajov. ALFA Bratislava, 1987.
-
Wróblewski, Piotr. Algoritmy : datové struktury a programovací techniky. Brno: Computer Press, 2004. ISBN 80-251-0343-9.
|