XD36DSA | Datové struktury a algoritmy | Rozsah výuky: | 14+6 | ||
---|---|---|---|---|---|
Přednášející (garant): | Hudec B. | Typ předmětu: | Z | Zakončení: | Z,ZK |
Zodpovědná katedra: | 336 | Kreditů: | 5 | Semestr: | Z |
Anotace:
Analýza algoritmů z hlediska operační a paměťové složitosti. Algoritmy řazení. Jednorozměrné a vícerozměrné vyhledávání. Geometrické vyhledávání a geometrické algoritmy. Datové typy, jejich specifikace a implementace. Soubory dat, logická a fyzická skladba souborů, implementace souborů, řazení souborů. Rekurze a rekurzivní programování, složitost rekurzivních algoritmů, implementace rekurze. Strategie návrhu algoritmů.
Osnovy přednášek:
1. | Paměťová a operační složitost algoritmů | |
2. | Klasifikace algoritmů řazení (třídění). Algoritmy řazení s kvadratickou operační složitostí | |
3. | Algoritmy řazení se složitostí n.logn, speciální algoritmy řazení | |
4. | Vyhledávací problém, jednorozměrné adresní vyhledávání | |
5. | Jednorozměrné asociativní vyhledávání, vyhledávací stromy, vyhledávání vzoru v textu | |
6. | Vícerozměrné vyhledávání, vícerozměrné vyhledávací stromy | |
7. | Geometrické vyhledávání a geometrické algoritmy | |
8. | Datové typy a jejich specifikace | |
9. | Implementace datových typů řetěz, zásobník, fronta, pole, tabulka, seznam, graf | |
10. | Soubory dat, logická a fyzická skladba, řazení souborů | |
11. | Rekurze a rekurzivní programování, implementace a složitost rekurzivních algoritmů | |
12. | Algoritmy prohledávání s návratem | |
13. | Dynamické programování | |
14. | Techniky a zásady návrhu algoritmů |
Osnovy cvičení:
1. | Určování minimální, maximální a průměrné operační složitosti algoritmů | |
2. | Algoritmy řazení výběrem a zaměňováním a jejich analýza z hlediska paměťové a operační složitosti | |
3. | Algoritmy řazení vkládáním a jejich analýza z hlediska paměťové a operační složitosti | |
4. | Algoritmy řazení Quick-sort, Heap-sort, Merge-sort, Radix-sort | |
5. | Adresní vyhledávání, rozptylování s otevřenou adresací | |
6. | Vyhledávání půlením, binární vyhledávací stromy a jejich vyvažování | |
7. | Vyhledávací stromy pro vícerozměrné vyhledávání, vyhledávání nejbližšího souseda | |
8. | Konstrukce konvexní obálky množiny bodů, test příslušnosti bodu polygonální oblasti | |
9. | Specifikace datového typu | |
10. | Implementace datového typu | |
11. | Aktualizace a řazení sekvenčních souborů | |
12. | Algoritmy prohledávání s návratem | |
13. | Výpočet složitosti rekurzivních algoritmů | |
14. | Zápočet |
Literatura Č:
1. | Hudec, B.: Programovací techniky. Praha , ČVUT 2001. | |
2. | Cormen,T.H., et al.: Introduction to ALGORITHMS, New York, McGraw-Hill 1990. | |
3. | Manoocher, A.:Abstract Data Types and Algorithms, London, Macmillan Education Ltd. |
Literatura A:
1. | Cormen,T.H., et al.: Introduction to ALGORITHMS, New York, McGraw-Hill 1990. | |
2. | Manoocher, A.:Abstract Data Types and Algorithms, London, Macmillan Education Ltd. |
Požadavky:
Absolvování průběžných testů. Dále každý student vypracuje individuální úlohu spočívající ve specifikaci a implementaci datového typu.
Předmět je zahrnut do těchto studijních plánů:
|
Stránka vytvořena 25. 2. 2002, semestry: Z/2001-2, Z/2002-3, L/2001-2, L/2002-3, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: I. Halaška (K336), J. Novák (K336) |