Efektivní algoritmy

Garant předmětu:

Přednášející:

Cvičící:

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Studenti získají přehled efektivních algoritmů a datových struktur pro řešení standardních úloh, především vyhledávání a řazení, nad dynamicky se měnícími daty. Umějí navrhovat a implementovat takové algoritmy, ovládají metody používané pro analýzu operační a paměťové složitosti algoritmů. Rozumějí algoritmům pro řazení o složitosti O(n.log n), pro speciální řazení s lineární složitostí, algoritmům asociativního a adresního vyhledávání. Umějí používat příslušné dynamické datové struktury, jako např. rozptylovací tabulky, vyhledávací stromy, vyvažované vyhledávací stromy, haldy, či B-stromy. Dokážou pracovat s rekurzivními algoritmy a dynamickým programováním.

Požadavky:

Předpokládá se schopnost aktivního algoritmického řešení základních typů úloh, znalost nějakého vyššího programovacího jazyka (Java, C++) a znalost základních pojmů z matematické analýzy a kombinatoriky.

Osnova přednášek:

1. Datové struktury 1: Základní ADT.

2. Datové struktury 2: Rozptylovací tabulky.

3. Algoritmy řazení 1.^

4. Datové struktury 3: Stromy, haldy.

5. Algoritmy řazení 2.

6. Datové struktury 4: Pokročilé haldy.

7. Vyhledávání a vyhledávací stromy.

8. Rekurzivní algoritmy.

9. B-stromy a jejich varianty.

10. Vyvažované vyhledávací stromy.

11. Dynamické programování.

12. Algoritmy výpočetní geometrie.

Osnova cvičení:

1. Algoritmy nad poli, vícerozměrná pole a mapovací funkce. ADT Seznam, Fronta, Zásobník.^2. ADT Tabulka, Množina. Rozptylovací tabulky.^3.Základní algoritmy řazení. Stromy a binární haldy.^4. Algoritmy řazení. Binomiální a Fibonnaciho haldy.^5. Vyhledávání a vyhledávací stromy. Rekurzivní algoritmy.^6. B-stromy a jejich varianty. Vyvažované vyhledávací stromy.^7.Dynamické programování.

Cíle studia:

Cílem předmětu je naučit studenty standardní soubor algoritmů pro zpracování dynamicky se měnících dat a naučit jej rozpoznávat vhodné příležitosti pro použití jejich různých variant. Současně s návrhem či přizpůsobováním algoritmů se studenti mají naučit i základní metody analýzy složitosti algoritmů jakožto hlavního kritéria jejich efektivnosti. Cílem je rozvíjet u studentů schopnost samostatného návrhu a analýzy algoritmů.

Studijní materiály:

Cormen, T. H., Leiserson, C. E., Rivest, R. L. Introduction to Algorithms. The MIT Press, 2001. ISBN 0262032937.

Poznámka:

Dvojici předmětů EFA + GRA lze uznat, jestliže student úspěšně absolvuje dvojici předmětů AG1 + AG2.

Student, kterému chybí EFA si zapíše AG1 a dělá rozdílovou zkoušku.

Znovu přijatému studentu, kterému bude uznaný předmět EFA z minulého studia si zapíše předmět AG1 a může požádat o uznání zápočtu.

Další informace:

Pro tento předmět se rozvrh nepřipravuje

Předmět je součástí následujících studijních plánů: