Přednášky:
Část I - Úvod do diskrétní matematiky
Zaměření a cíle diskrétní matematiky. Množiny, prvky a podmnožiny, základní kombinatorické pojmy. Kombinatorické výběry a jejich počet.
Konečná pravděpodobnost: Pojem pravděpodobnosti, pravděpodobnostního prostoru a náhodného jevu. Náhodná čísla v počítači.
Přirozená čísla a matematická indukce. Pojem matematického důkazu. Počty podmnožin, odvození vzorců pro kombinace a permutace. Aplikace.
Formální základy diskrétní matematiky: pojmy relace, zobrazení, ekvivalence,
uspořádání, částečné uspořádání. Princip inkluze a exkluze.
Algoritmické aspekty: praktická implementace množin, zobrazení a relací. Algoritmy generování a procházení všech základních kombinatorických výběrů.
Část II - Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů. Metody zadání grafu, orientované grafy.
Pojem souvislosti grafu, algoritmy procházení do hloubky a do šířky. Vyšší stupně souvislosti (Mengerovy věty).
Eulerovské grafy - kreslení jedním tahem, využití, hamiltonovské grafy a jejich využití .
Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její určení.
Stromy a jejich charakterizace, kořenové stromy, isomorfizmus stromů.
Kostra grafu, (počet koster), problém minimální kostry. Aplikace problému minimální kostry, klasické algoritmy.
Rovinné kreslení grafu, Eulerův vztah a jeho důsledky. Barvení grafů, bipartitní grafy a jejich rozeznávání.
Toky v sítích: definice a modelované problémy. Ford-Fulkersonův algoritmus pro nalezení maximálního toku. Další využití algoritmu (párování a systém reprezentantů).
Cvičení:
Procvičení učiva z přednášek v dané chronologii.
Projekty:
Vypracování jednoho samostatného písemného projektu, který se skládá z části kombinatorické a části, týkající se teorie grafů.
Část I - Úvod do diskrétní matematiky
Zaměření a cíle diskrétní matematiky. Množiny, prvky a podmnožiny, základní kombinatorické pojmy. Kombinatorické výběry a jejich počet.
Konečná pravděpodobnost: Pojem pravděpodobnosti, pravděpodobnostního prostoru a náhodného jevu. Náhodná čísla v počítači.
Přirozená čísla a matematická indukce. Pojem matematického důkazu. Počty podmnožin, odvození vzorců pro kombinace a permutace. Aplikace.
Formální základy diskrétní matematiky: pojmy relace, zobrazení, ekvivalence,
uspořádání, částečné uspořádání. Princip inkluze a exkluze.
Algoritmické aspekty: praktická implementace množin, zobrazení a relací. Algoritmy generování a procházení všech základních kombinatorických výběrů.
Část II - Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi. Podgrafy, isomorfizmus, stupně vrcholů. Metody zadání grafu, orientované grafy.
Pojem souvislosti grafu, algoritmy procházení do hloubky a do šířky. Vyšší stupně souvislosti (Mengerovy věty).
Eulerovské grafy - kreslení jedním tahem, využití, hamiltonovské grafy a jejich využití .
Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty. Metrika grafu a její určení.
Stromy a jejich charakterizace, kořenové stromy, isomorfizmus stromů.
Kostra grafu, (počet koster), problém minimální kostry. Aplikace problému minimální kostry, klasické algoritmy.
Rovinné kreslení grafu, Eulerův vztah a jeho důsledky. Barvení grafů, bipartitní grafy a jejich rozeznávání.
Toky v sítích: definice a modelované problémy. Ford-Fulkersonův algoritmus pro nalezení maximálního toku. Další využití algoritmu (párování a systém reprezentantů).
Cvičení:
Procvičení učiva z přednášek v dané chronologii.
Projekty:
Vypracování jednoho samostatného písemného projektu, který se skládá z části kombinatorické a části, týkající se teorie grafů.