Přednášky a cvičení:
Část I - Úvod do diskrétní matematiky
Zaměření a cíle diskrétní matematiky.
Výpočetní metody: Kombinatorické výběry, jejich aplikace. Dirichletův princip.
Geometrická a aritmetická posloupnost. Princip inkluze a exkluze, binomická věta a jejich využití.
Konečná pravděpodobnost: Pojem pravděpodobnosti, pravděpodobnostního prostoru a náhodného jevu. Náhodná čísla v počítači.
Rekurentní rovnice, jejich aplikace a příklady řešení.
Modulární aritmetika.
Algoritmické aspekty: implementace diskrétních struktur. 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í struktury grafu do hloubky a do šířky. Vyšší stupně souvislosti.
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í největšího toku. Další využití algoritmu (párování a systém reprezentantů).
Část I - Úvod do diskrétní matematiky
Zaměření a cíle diskrétní matematiky.
Výpočetní metody: Kombinatorické výběry, jejich aplikace. Dirichletův princip.
Geometrická a aritmetická posloupnost. Princip inkluze a exkluze, binomická věta a jejich využití.
Konečná pravděpodobnost: Pojem pravděpodobnosti, pravděpodobnostního prostoru a náhodného jevu. Náhodná čísla v počítači.
Rekurentní rovnice, jejich aplikace a příklady řešení.
Modulární aritmetika.
Algoritmické aspekty: implementace diskrétních struktur. 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í struktury grafu do hloubky a do šířky. Vyšší stupně souvislosti.
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í největšího toku. Další využití algoritmu (párování a systém reprezentantů).