Přednášky:
Část I -- Úvod do diskrétní matematiky
Zaměření a cíle diskrétní matematiky.
Množiny, prvky a podmnožiny, úvodní kombinatorické pojmy.
Kombinace a permutace, vzorce na jejich počet.
Přirozená čísla a matematická indukce. Pojem matematického důkazu.
Počty podmnožin, důkazy vzorců pro kombinace a permutace.
Konečná pravděpodobnost: hody mincí a kostkou, náhodné výběry, míchání karet.
Pojem pravděpodobnosti, prostoru a jevu.
Náhodná čísla v počítači.
Formální základy diskrétní matematiky: pojmy relace, zobrazení, eqivalence,
uspořádání, částečné uspořádání.
(Princip inkluze a exkluze.)
Algoritmické aspekty: praktická implementace množin, zobrazení a relací.
Algoritmy generování podmnožin a permutací.
(Odhady růstu funkcí faktoriál a kombinační číslo.)
Část II -- Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi.
Podgrafy, izomorfismus, stupně vrcholů, (indukované podgrafy).
Realizace grafu, orientovaný graf.
Souvislost grafu, algoritmy procházení do hloubky a do šířky.
Vícenásobná souvislost, hranová souvislost. (Mengerova věta.)
Eulerovské grafy -- kreslení jedním tahem.
Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty.
Metrika grafu a její výpočet. (Tranzitivní uzávěr.)
Stromy a jejich charakterizace, izomorfismus stromů.
Kořenové stromy.
Kostra grafu, (počet koster), problém minimální kostry.
Definice matroidu přes nezávislé množiny.
Vektorový a grafový matroid, hladový algoritmus.
Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky.
Rovinné kreslení grafu, Eulerův vztah.
Barvení grafů, bipartitní grafy a jejich rozeznávání.
(Průsečíkové číslo.)
Praktická realizace grafů v počítači, různé způsoby realizace a jejich výhody.
Ohodnocení vrcholů a hran.
Realizace kořenových stromů a planárních grafů.
(Vizualizace grafů včetně nerovinných.)
Aktuální průběh přednášek a promítané přednášky.
Cvičení:
Procvičení věcí z přednášky.
Projekty:
Vypracování samostatých písemných referátů, viz zadaná témata s termíny úkolů v KatISu.
(Na témata se přihlašujte před odevzdáním, už to funguje.)
Část I -- Úvod do diskrétní matematiky
Zaměření a cíle diskrétní matematiky.
Množiny, prvky a podmnožiny, úvodní kombinatorické pojmy.
Kombinace a permutace, vzorce na jejich počet.
Přirozená čísla a matematická indukce. Pojem matematického důkazu.
Počty podmnožin, důkazy vzorců pro kombinace a permutace.
Konečná pravděpodobnost: hody mincí a kostkou, náhodné výběry, míchání karet.
Pojem pravděpodobnosti, prostoru a jevu.
Náhodná čísla v počítači.
Formální základy diskrétní matematiky: pojmy relace, zobrazení, eqivalence,
uspořádání, částečné uspořádání.
(Princip inkluze a exkluze.)
Algoritmické aspekty: praktická implementace množin, zobrazení a relací.
Algoritmy generování podmnožin a permutací.
(Odhady růstu funkcí faktoriál a kombinační číslo.)
Část II -- Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi.
Podgrafy, izomorfismus, stupně vrcholů, (indukované podgrafy).
Realizace grafu, orientovaný graf.
Souvislost grafu, algoritmy procházení do hloubky a do šířky.
Vícenásobná souvislost, hranová souvislost. (Mengerova věta.)
Eulerovské grafy -- kreslení jedním tahem.
Vzdálenost v grafu, Dijkstrův algoritmus pro hledání nejkratší cesty.
Metrika grafu a její výpočet. (Tranzitivní uzávěr.)
Stromy a jejich charakterizace, izomorfismus stromů.
Kořenové stromy.
Kostra grafu, (počet koster), problém minimální kostry.
Definice matroidu přes nezávislé množiny.
Vektorový a grafový matroid, hladový algoritmus.
Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky.
Rovinné kreslení grafu, Eulerův vztah.
Barvení grafů, bipartitní grafy a jejich rozeznávání.
(Průsečíkové číslo.)
Praktická realizace grafů v počítači, různé způsoby realizace a jejich výhody.
Ohodnocení vrcholů a hran.
Realizace kořenových stromů a planárních grafů.
(Vizualizace grafů včetně nerovinných.)
Aktuální průběh přednášek a promítané přednášky.
Cvičení:
Procvičení věcí z přednášky.
Projekty:
Vypracování samostatých písemných referátů, viz zadaná témata s termíny úkolů v KatISu.
(Na témata se přihlašujte před odevzdáním, už to funguje.)