Efektivní algoritmy
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
BI-EFA | Z,ZK | 5 | 2P+2C | česky |
- 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ů: