|
Vyučující
|
-
Novotný Lukáš, doc. Ing. Ph.D.
|
|
Obsah předmětu
|
1. Permutace. Rychlé násobení matic. Permanenty. 2. Grupy a tělesa. Kvadratická rezidua. Testování prvočíselnosti. 3. Grafové algoritmy. Generování grafů. 4. Izomorfismus grafů. Stromy. Rozklady grafu. 5. Souvislost grafu. Cyklická souvislost. 6. Rovinnost grafu. Párování. Třídy grafů. 7. Matroidy, průniky matroidů. Submodulární funkce. 8. Nezávislost grafů. Barvení grafů. Hamiltonovské kružnice. 9. Hypergrafy. Bloková schémata. 10. Splnitelnost. 11. Kombinatorická geometrie. 12. Pravděpodobnostní algoritmy. Online algoritmy. 13. Paralelní algoritmy. Analýza algoritmů.
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Přednáška, Cvičení
- Příprava na souhrnný test [6-30]
- 20 hodin za semestr
- Kontaktní výuka
- 39 hodin za semestr
- Příprava na zkoušku [10-60]
- 45 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| předpokládá se aktivní znalost obsahu předmětu KMA/DMA (KMA/DMA-A). Je doporučen souběžně předmět KMA/TGD1 |
| Výsledky učení |
|---|
| úspěšný absolvent bude schopen především: - algoritmicky řešit standardní kombinatorické úlohy, - analyzovat složitost algoritmů, - aplikovat vhodné aproximační algoritmy |
| Vyučovací metody |
|---|
| Přednáška založená na výkladu, |
| Přednáška s aktivizací studentů, |
| Cvičení (praktické činnosti), |
| Hodnotící metody |
|---|
| Ústní zkouška, |
| Test, |
|
Doporučená literatura
|
-
Schrijver, A. Combinatorial optimization. Berlin, 2003. ISBN 3-540-44389-4.
-
Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest and Clifford Stein:. Introduction to Algorithms, 3rd Edition.
-
Van Lint, J. H.; Wilson, R. M. A course in combinatorics. Cambridge : Harvard University Press, 2001. ISBN 0-521-00601-5.
|