Detail předmětu
Algoritmy (v angličtině)
IALe Ak. rok 2024/2025 letní semestr 5 kreditů
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, vyhledávací tabulka. 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.
Garant předmětu
Jazyk výuky
Zakončení
Rozsah
- 39 hod. přednášky
- 13 hod. projekty
Bodové hodnocení
- 51 bodů závěrečná zkouška (písemná část)
- 14 bodů půlsemestrální test (písemná část)
- 35 bodů projekty
Zajišťuje ústav
Přednášející
Cvičící
Cíle předmětu
Seznámit se s principy metod dokazování správnosti programů a s tvorby dokázaných programů. Seznámit se základními principy složitosti algoritmů. Seznámit se s principy dynamického přidělování paměti. Seznámit se základními abstraktními datovými typy a strukturami, naučit se je implementovat a používat. 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í.
- Student porozumí významu metod dokazování správnosti programů a s tvorby dokázaných programů.
- Porozumí základním principům a významu složitosti algoritmů.
- Seznámí se se základními abstraktními datovými typy a strukturami, naučí se je implementovat a používat.
- Seznámí se s principy dynamického přidělování paměti.
- Naučí se rekurzívní a nerekurzívní zápisy základních algoritmů.
- Naučí se vytvářet a analyzovat algoritmy vyhledávání a řazení.
- Student se nučí odborné terminologii v českém i anglickém jazyce
- Student se naučí vytvářet malé projekty v malém týmu
- Student se naučí prezentaci a obhajobě výsledků v malém projektu
Doporučené prerekvizity
- Základy programování (IZP)
Požadované prerekvizitní znalosti a dovednosti
- Znalost základů programování v procedurálně orientovaném programovacím jazyce (pro řešení domácích úloh je nezbytná znalost programovacího jazyka C).
- Středoškolské znalosti z matematiky.
Literatura studijní
- Cormen, T.H., Leiserson, Ch.E., Rivest, R.L.: Introduction to Algorithms, Cambridge: MIT Press, 2009
- Knuth, D.: The Art of Computer programming, Vol.1,2,3. Addison Wesley, 1968
- Wirth, N.: Alorithms+Data Structures=Programs, Prentice Hall, 1976
- Horowitz, Sahni: Fundamentals of Data Structures in C, University Press, 2010
- Aho A.V., Hoppcroft J.E., Ullman J.D.: Data Structures and Algorithms, Addison Wesley, 1983.
- Kruse, R.L.: Data Structures and Program Design. Prentice- Hall,Inc. 1984
- Baase, S.: Computer Algorithms - Introduction to Design and Analysis. Addison Wesley, 1998
Osnova přednášek
- Přehled datových struktur, úvod do způsobů hodnocení časové složitosti algoritmů.
- Abstraktní datový typ a jeho specifikace.
- 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 vyhledávací tabulka.
- 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í I
- Známé metody řazení polí II.
Osnova ostatní - projekty, práce
- Dvě domácí úlohy
Průběžná kontrola studia
- Dvě opravované domácí úlohy - 25 bodů
- Půlsemestrální písemná zkouška - 14 bodů
- Vypracování krátkých příkladů během přednášek - max 10 bodů
- Závěrečná písemná zkouška - 51 bodů
Rozvrh