1-INF-160 Úvod do kombinatoriky a teórie grafov
Odporúčaný ročník: | 1. |
Semester: | letný |
Rozsah: | P2,C2 |
Hodnotenie: | 30/70 |
Počet kreditov: | 6 |
Vyučujúci: | prednáša prof. RNDr. Martin Škoviera PhD. cvičí Mgr. Lucia Haviarová cvičí Mgr. Barbora Candráková |
www stránka: |
Cieľ:
Zoznámenie so základnými pojmami, výsledkami, metódami a algoritmami z kombinatoriky a teórie grafov.
Sylabus:
- Kombinatorika: základné typy kombinatorických úloh a základné pojmy. Permutácie, variácie, kombinácie. Pascalova formula, binomická a plynomická veta, Newtonova polynomická veta. Kombinatorické identity, odhady kombinatorických čísel. Princíp zapojenia - vypojenia. Rekurentné vzťahy, generujúce funkcie, metódy sumácie, konečný kalkulus.
- Teória grafov: Motivačné úlohy. Definície rôznych typov grafov. Základné pojmy. Stromy. Prehľadávanie grafov. Eulerovské ťahy, Hamiltonovské kružnice. Farbenia grafov. Planárne grafy. Enumerácia stromov. Algoritmy na nájdenie najkratšej cesty, najlacnejšej kostry, najpočetnejšieho párenia.
Literatúra:
- Martin Škoviera: Úvod do diskrétnej matematiky
- Kosmák L.: Kombinatorická teória pravdepodobnosti
- Nešetřil, Jaroslav - Matoušek, Jiří: Kapitoly z diskrétní matematiky