Detail předmětu
Algoritmy
FEKT-BPC-ALGAk. rok: 2019/2020
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ů.
Garant předmětu
Zajišťuje ústav
Výsledky učení předmětu
Student se naučí analyzovat a navrhovat jednoduché algoritmy pro počítače. Seznámí se se základní koncepcí programovacích jazyků. Naučí se vytvářet programy ve vyšších programovacích jazycích. Porozumí EBNF pro popis syntaxe programovacího jazyka. Osvojí si odborné pojmy z oblasti programování, syntax a sémantiku programovacího jazyka.
Prerekvizity
Jsou požadovány znalosti na úrovni středoškolského studia.
Doporučená nebo povinná literatura
Honzík, J.,Hruška, T.,Máčel, M.: Vybrané kapitoly z programovacích technik, Ed.stř.VUT Brno,1991.
Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
Horovitz, Sahni: Fundamentals of Data Structures.
Amsbury, W: Data Structures: From Arrays to Priority Queues.
Cormen, T.H. ,Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms.
Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms.
Kruse, R.L.>Data Structures and Program Design. Prentice- Hall,Inc. 1984
Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
Plánované vzdělávací činnosti a výukové metody
Metody vyučování závisejí na způsobu výuky a jsou popsány článkem 7 Studijního a zkušebního řádu VUT.
Způsob a kritéria hodnocení
Podmínky pro úspěšné ukončení předmětu stanoví každoročně aktualizovaná vyhláška garanta předmětu.
Jazyk výuky
čeština
Osnovy výuky
1. Základy algoritmického jazyka. Přehled datových struktur. Abstraktní datový typ a jeho specifikace.
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ů.
Cíl
Seznámit se s metodami dokazování správnosti programů a s tvorbou dokázaných programů.
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
Vymezení kontrolované výuky a způsob jejího provádění stanoví každoročně aktualizovaná vyhláška garanta předmětu.
Zařazení předmětu ve studijních plánech
- Program BPC-AUD bakalářský
specializace AUDB-TECH , libovolný ročník, zimní semestr, 5 kreditů, volitelný
- Program BPC-AMT bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
- Program BPC-EKT bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
- Program BPC-IBE bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
- Program BPC-MET bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
- Program BPC-SEE bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný
- Program BPC-TLI bakalářský, libovolný ročník, zimní semestr, 5 kreditů, volitelný