M5501 Diskrétní matematika I

Přírodovědecká fakulta
podzim 1999
Rozsah
2/1/0. 3 kr. Ukončení: z.
Vyučující
doc. RNDr. Eduard Fuchs, CSc. (přednášející)
RNDr. Pavel Šišma, Dr. (cvičící)
Garance
doc. RNDr. Eduard Fuchs, CSc.
Ústav matematiky a statistiky – Ústavy – Přírodovědecká fakulta
Kontaktní osoba: doc. RNDr. Eduard Fuchs, CSc.
Předpoklady
M3510 Algebra III
Omezení zápisu do předmětu
Předmět je nabízen i studentům mimo mateřské obory.
Mateřské obory/plány
Osnova
  • Základní kombinatorické funkce. Variace, permutace, kombinace. Rozklady konečných množin; rozklady přirozených čísel. Princip inkluze a exkluze. Rekurentní formule a jejich řešení. Posloupnosti. Základní pojmy teorie grafů. Souvislé grafy, stromy. Eulerovské a hamiltonovské grafy a jejich aplikace (se zaměřením na školskou matematiku). Rovinné grafy, barvení grafů. Elementární grafové algoritmy: hledání nejkratší cesty, minimální kostra, kritická cesta. Charakterizace NP-úplných problémů; problém obchodního cestujícího.
Literatura
  • FUCHS, Eduard. Kombinatorika a teorie grafů. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1986, 138 s. info
  • SEDLÁČEK, Jiří. Úvod do teorie grafů. Vyd. 3. Praha: Academia, 1981, 271 s. URL info
  • VILENKIN, Naum Jakovlevič. Kombinatorika. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1977, 298 s. URL info
  • NEŠETŘIL, Jaroslav. Kombinatorika. Vyd. 1. Praha: Státní pedagogické nakladatelství, 1975, 160 s. URL info
  • NEŠETŘIL, Jaroslav. Teorie grafů. Vyd. 1. Praha: SNTL - Nakladatelství technické literatury, 1979, 316 s. URL info
  • ŠIŠMA, Pavel. Teorie grafů 1736-1963. 1. vyd. Praha: Prometheus, 1997, 171 s. Dějiny matematiky, sv. 8. ISBN 80-7196-065-9. info
Další komentáře
Předmět je vyučován každoročně.
Výuka probíhá každý týden.
Předmět je zařazen také v obdobích podzim 2000, podzim 2001.