Logo ČVUT
Loading...
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2011/2012

Diskrétní matematika

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
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ů:
Platnost dat k 9. 7. 2012
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet24616605.html