Detail předmětu
Algoritmy
FEKT-BPC-ALGAk. rok: 2021/2022
Přehled základních datových struktur a jejich použití.
Principy dynamického přidělování paměti.
Specifikace abtraktních datových typů (ADT).
Specifikace a implementace ADT: seznamy, zásobník, fronta, množina, pole, vyhledávací tabulka, graf, binární strom. Algoritmy nad binárním stromem.
Vyhledávání: sekvenční, v neseřazeném a seřazeném poli, vyhledávání se zarážkou, binární vyhledávání, binární vyhledávácí strom, vyvážený strom (AVL). Vyhledávání v tabulkách s rozptýlenými položkami.
Řazení, principy, řazení bez přesunu položek, řazení podle více klíčů. Nejznámější metody řazení: Select-sort, Bubble-sort, Heap-sort, Insert-sort a jeho varianty, Shell-sort, Quick sort v rekurzívní a nerekurzívní notaci, Merge-sort, List-merge-sort, Radix-sort. Sekvenční metody řazení. Rekurze a algoritmy s návratem. Vyhledávání podřetězců v textu. Dokazování programů, tvorba dokázaných programů.
Jazyk výuky
Počet kreditů
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Prerekvizity
Plánované vzdělávací činnosti a výukové metody
Způsob a kritéria hodnocení
Osnovy výuky
2. Specifikace, implementace a použití ADT seznam.
3. Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
4. ADT pole, množina, graf, binární strom.
5. Algoritmy nad binárním stromem.
6. Vyhledávání, sekvenční, v poli, binární vyhledávání.
7. Binární vyhledávácí stromy, AVL strom.
8. Vyhledávání v tabulkách s rozptýlenými položkami.
9. Řazení, principy, bez přesunu, s vícenásobným klíčem.
10. Známé metody řazení polí I
11. Známé metody řazení polí II, řazení souborů.
12. Rekurze, algoritmy s návratem.
Dokazování správnosti programů, tvorba dokázaných programů.
Učební cíle
Seznámit se základními principy složitosti algoritmů.
Seznámit se základními abstraktními datovýni typy a strukturami, naučit se je implementovat a používat. Seznámit se s principy dynamického přidělování paměti. Naučit se rekurzívní a nerekurzívní zápisy základních algoritmů. Naučit se vytvářet a analyzovat algoritmy vyhledávání a řazení.
Vymezení kontrolované výuky a způsob jejího provádění a formy nahrazování zameškané výuky
Základní literatura
Amsbury, W: Data Structures: From Arrays to Priority Queues.
Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
Cormen, T.H. ,Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
Honzík, J.,Hruška, T.,Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
Horovitz, Sahni: Fundamentals of Data Structures.
Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
Kruse, R.L.>Data Structures and Program Design. Prentice- Hall,Inc. 1984
Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
Zařazení předmětu ve studijních plánech
- Program BPC-AMT bakalářský 0 ročník, zimní semestr, volitelný
- Program BPC-AUD bakalářský
specializace AUDB-TECH , 0 ročník, zimní semestr, volitelný
specializace AUDB-ZVUK , 0 ročník, zimní semestr, volitelný - Program BPC-EKT bakalářský 0 ročník, zimní semestr, volitelný
- Program BPC-IBE bakalářský 0 ročník, zimní semestr, volitelný
- Program BPC-MET bakalářský 0 ročník, zimní semestr, volitelný
- Program BPC-SEE bakalářský 0 ročník, zimní semestr, volitelný
- Program BPC-TLI bakalářský 0 ročník, zimní semestr, volitelný
Typ (způsob) výuky
Přednáška
Vyučující / Lektor
Osnova
Specifikace, implementace a použití ADT seznam.
Specifikace, implementace a použití ADT zásobník, fronta. Vyčíslení výrazů s použitím zásobníku.
ADT pole, množina, graf, binární strom.
Algoritmy nad binárním stromem.
Vyhledávání, sekvenční, v poli, binární vyhledávání.
Binární vyhledávácí stromy, AVL strom.
Vyhledávání v tabulkách s rozptýlenými položkami.
Řazení, principy, bez přesunu, s vícenásobnám klíčem.
Známé metody řazení polí
Známé motody řazení polí, řazení souborů.
Rekurze, algoritmy s návratem.
Dokazování správnosti programů, tvorba dokázaných programů.
Projekt
Vyučující / Lektor
Osnova
Projekt s miniobhajobou čtveřice studentů.