|
Vyučující
|
-
Volejníček Vladimír, Mgr. Ph.D.
|
|
Obsah předmětu
|
1. Úvod, postup při návrhu řešení problému, zápis algoritmů, časová a prostorová složitost 2. Metoda hrubé síly, backtracking 3. Rozděl a panuj 4. Dynamické programování I 5. Dynamické programování II 6. Hladové algoritmy a optimalita řešení 7. Principy návrhu grafových algoritmů I (Dijkstra, Bellman-Ford, Floyd-Warshall, Kruskal) 8. Principy návrhu grafových algoritmů II 9. Stromové struktury - reprezentace intervalů, prefixových součtů a disjunktních množin 10. Algoritmy zpracování textů - vyhledávání podřetězců 11. NP-úplné problémy, splnitelnost logického obvodu, dokazování NP-úplnosti 12. Možnosti řešení NP-úplných úloh 13. Řešení problémů vyžadujících kombinaci více principů
|
|
Studijní aktivity a metody výuky
|
- Nácvik dovedností [3/10]
- 17 hodin za semestr
- Kontaktní výuka
- 65 hodin za semestr
- Příprava na dílčí test [2-10]
- 12 hodin za semestr
- Příprava na souhrnný test [6-30]
- 20 hodin za semestr
- Příprava na zkoušku [10-60]
- 42 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| asymptotická složitost |
| princip fungování základních datových struktur (pole, halda, zásobník, fronta, spojový seznam, strom) a složitost souvisejících operací |
| reprezentace grafů a základní algoritmy jejich prohledávání |
| Odborné dovednosti |
|---|
| základní znalosti programování |
| rekurzivní volání funkcí |
| rutinní používání základních datových struktur |
| Obecné způsobilosti |
|---|
| bc. studium: své učení a pracovní činnost si sám plánuje a organizuje, |
| bc. studium: rozpozná problém, objasní jeho podstatu, rozčlení ho na části, |
| bc. studium: uplatňuje při řešení problémů vhodné metody a dříve získané vědomosti a dovednosti, kromě analytického a kritického myšlení využívá i myšlení tvořivé s použitím představivosti a intuice, |
| bc. studium: je otevřený k využití různých postupů při řešení problémů, nahlíží problém z různých stran, |
| bc. studium: zvažuje možné klady a zápory jednotlivých variant řešení, včetně posouzení jejich rizik a důsledků, |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| obecné metody návrhu algoritmů |
| principy algoritmů a datových struktur probíraných na přednášce |
| třídy složitosti P a NP, pojem NP-úplný problém, převoditelnost, možnosti řešení |
| Odborné dovednosti |
|---|
| používat obecné metody pro návrhu algoritmů |
| analýza složitosti algoritmů |
| schopnost naprogramovat daný algoritmus |
| zařadit daný algoritmus do kategorie obecných metod návrhu |
| rozpoznat NP-úplné problémy |
| Obecné způsobilosti |
|---|
| bc. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
| bc. studium: srozumitelně a přesvědčivě sdělují odborníkům i laikům informace o povaze odborných problémů a vlastním názoru na jejich řešení, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška s demonstrací, |
| E-learning, |
| Řešení problémů, |
| Demonstrace dovedností, |
| Samostudium, |
| Individuální konzultace, |
| Diskuse, |
| Přednáška založená na výkladu, |
| Odborné dovednosti |
|---|
| Přednáška založená na výkladu, |
| Přednáška s diskusí, |
| Přednáška s aktivizací studentů, |
| Řešení problémů, |
| Demonstrace dovedností, |
| Individuální konzultace, |
| Diskuse, |
| Obecné způsobilosti |
|---|
| Přednáška založená na výkladu, |
| Přednáška s diskusí, |
| Přednáška s aktivizací studentů, |
| Řešení problémů, |
| Demonstrace dovedností, |
| Individuální konzultace, |
| Diskuse, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Odborné dovednosti |
|---|
| Písemná zkouška, |
| Test, |
| Průběžné hodnocení, |
| Obecné způsobilosti |
|---|
| Ústní zkouška, |
| Písemná zkouška, |
| Test, |
| Průběžné hodnocení, |
|
Doporučená literatura
|
-
Halim, Steven; Halim, Felix. Competitive programming 3 : the new lower bound of programming contests : handbook for ACM ICPC and IOI contestants. [3.ed.]. [S.l.] : Lulu, 2013.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
|