Diskrétní matematika
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
818DIM | KZ | 2 | 0+2 | česky |
- Přednášející:
- Cvičící:
- Předmět zajišťuje:
- Katedra softwarového inženýrství
- Anotace:
-
Předmět diskrétní matematiky je demonstrován na základech teorie grafů. Jsou zde uvedeny definice, věty, důkazy, datové struktury a algoritmy.
- Požadavky:
-
Základní znalosti z lineární algebry.
- Osnova přednášek:
-
1. Předmět diskrétní matematiky.
2. Teorie grafů, neorientovaný graf.
3. Základní typy grafů, isomorfismus grafů.
4. Cesty, kružnice a kliky v grafu.
5. Charakteristiky grafu, charakteristiky vrcholu.
6. Souvislé grafy, vzdálenost vrcholů, metrický prostor vrcholů.
7. Maticová reprezentace neorientovaného grafu, Wilshawův a Floydův algoritmus.
8. Eulerovské a hamiltonovské grafy.
9. Planární grafy, chromatické číslo.
10. Strom, kořenový strom, algoritmy na stromech.
11. Heuristické a chamtivé algoritmy.
12. Minimální kostra grafu, Kruskalův nebo Primův algoritmus.
13. Optimální cesty v grafech.
- Osnova cvičení:
-
1. Předmět diskrétní matematiky.
2. Teorie grafů, neorientovaný graf.
3. Základní typy grafů, isomorfismus grafů.
4. Cesty, kružnice a kliky v grafu.
5. Charakteristiky grafu, charakteristiky vrcholu.
6. Souvislé grafy, vzdálenost vrcholů, metrický prostor vrcholů.
7. Maticová reprezentace neorientovaného grafu, Wilshawův a Floydův algoritmus.
8. Eulerovské a hamiltonovské grafy.
9. Planární grafy, chromatické číslo.
10. Strom, kořenový strom, algoritmy na stromech.
11. Heuristické a chamtivé algoritmy.
12. Minimální kostra grafu, Kruskalův nebo Primův algoritmus.
13. Optimální cesty v grafech.
14. Problém obchodního cestujícího.
- Cíle studia:
-
Znalosti:
Základy teorie grafů, oblasti využití teorie grafů, grafové algoritmy.
Schopnosti:
Řešení širokého spektra úloh z teorie grafů.
- Studijní materiály:
-
Povinná literatura:
[1] J. Matoušek, J. Nešetřil: Kapitoly z diskrétní matematiky, Karolinum, Praha, 2000.
[2] J. Nešetřil: Teorie grafů, SNTL, Praha, 1979.
Doporučená literatura:
[3] R. Diestel: Graph Theory, Springer Verlag, Berlin, 1996.
- Poznámka:
- Rozvrh na zimní semestr 2011/2012:
- Rozvrh není připraven
- Rozvrh na letní semestr 2011/2012:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů: