Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
X36DSA Datové struktury a algoritmy Rozsah výuky:2+2
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.

Rozsah výuky v kombinované formě studia: 14+6
Typ cvičení: s, p
Předmět je nabízen také v anglické verzi.

Předmět je zahrnut do těchto studijních plánů:
Plán Obor Role Dop. semestr
BVT Výpočetní technika Z 3


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)