| |
Datové struktury a algoritmy (Y36DSA)
předmět denního studia, v tomto semestru se nevyučuje
Rozsah (přednášky + cvičení): 2+2
Zakončení: Zápočet, zkouška
Anotace:
| |
Analýza algoritmů z hlediska operační a paměťové složitosti. Algoritmy řazení. Abstraktní datové typy, jejich specifikace a implementace. Tabulky a rozptylování. Stromy, binární haldy, Fibonnaciho haldy. Rekurze a rekurzivní programování, implementace, složitost rekurzivních algoritmů, metody řešení rekurentních rovnic. Dynamické programování. Vyhledávání, vyhledávací stromy, vyvažováné vyhledávací stromy.
|
Osnova:
| |
- Paměťová a operační složitost algoritmů
- Klasifikace algoritmů řazení (třídění). Algoritmy řazení s kvadratickou operační složitostí
- Algoritmy řazení se složitostí n.logn, speciální algoritmy řazení
- Vyhledávací problém, jednorozměrné adresní vyhledávání
- Jednorozměrné asociativní vyhledávání, vyhledávací stromy, vyhledávání vzoru v textu
- Vícerozměrné vyhledávání, vícerozměrné vyhledávací stromy
- Geometrické vyhledávání a geometrické algoritmy
- Datové typy a jejich specifikace
- Implementace datových typů řetěz, zásobník, fronta, pole, tabulka, seznam, graf
- Soubory dat, logická a fyzická skladba, řazení souborů
- Rekurze a rekurzivní programování, implementace a složitost rekurzivních algoritmů
- Algoritmy prohledávání s návratem
- Dynamické programování
- Techniky a zásady návrhu algoritmů
|
Osnova cvičení:
| |
- Určování minimální, maximální a průměrné operační složitosti algoritmů
- Algoritmy řazení výběrem a zaměňováním a jejich analýza z hlediska paměťové a operační složitosti
- Algoritmy řazení vkládáním a jejich analýza z hlediska paměťové a operační složitosti
- Algoritmy řazení Quick-sort, Heap-sort, Merge-sort, Radix-sort
- Adresní vyhledávání, rozptylování s otevřenou adresací
- Vyhledávání půlením, binární vyhledávací stromy a jejich vyvažování
- Vyhledávací stromy pro vícerozměrné vyhledávání, vyhledávání nejbližšího souseda
- Konstrukce konvexní obálky množiny bodů, test příslušnosti bodu polygonální oblasti
- Specifikace datového typu
- Implementace datového typu
- Aktualizace a řazení sekvenčních souborů
- Algoritmy prohledávání s návratem
- Výpočet složitosti rekurzivních algoritmů
- Zápočet
|
Literatura:
| |
- Hudec, B.: Programovací techniky. Praha , ČVUT 2001.
- Cormen,T.H., et al.: Introduction to ALGORITHMS, New York, McGraw-Hill 1990.
- Manoocher, A.:Abstract Data Types and Algorithms, London, MacMillan Education Ltd. 1990.
|
Požadavky:
| |
Znalost zakladních pojmů a postupů z algoritmizace.
|
Vyučující:
|
 
|
