Efektivní algoritmy
| Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
|---|---|---|---|---|
| BI-EFA | Z,ZK | 5 | 2+2 | česky |
- Přednášející:
- Pavel Tvrdík (gar.)
- Cvičící:
- Jiří Chludil, Petr Matyáš
- 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:
-
Rozsah=prednasky+cviceni:2p+2c
- Rozvrh na zimní semestr 2011/2012:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - Rozvrh na letní semestr 2011/2012:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů:
-
- Teoretická informatika - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět oboru)
- Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2009 a 2010 (povinný předmět oboru)
- Informační systémy a management - verze pro ty, kteří se zapsali v roce 2009 a 2010 (VO)
- Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2009 a 2010 (VO)
- Informatika, plán pro fázi studia bez oboru - verze pro ty, kteří se zapsali v roce 2011 a 2012 (VO)
- Informační systémy a management - verze pro ty, kteří se zapsali v roce 2011 a 2012 (VO)
- Softwarové inženýrství - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět oboru)
- Teoretická informatika - verze pro ty, kteří se zapsali v roce 2011 a 2012 (povinný předmět oboru)