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.
Výběry prvků s opakováním.
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.
Přirozená čísla a matematická indukce. Pojem matematického důkazu.
Počty podmnožin, důkazy vzorců pro kombinace a permutace.
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í.
Část II -- Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi.
Podgrafy, isomorfizmus, 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.
Stromy a jejich charakterizace, isomorfizmus stromů.
Kořenové stromy.
Kostra grafu, (počet koster), problém minimální kostry.
Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky.
Rovinné kreslení grafu, Eulerův vztah a jeho aplikace.
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.
Aplikace na párování a různé reprezentanty.
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 a jiné dokumenty.
Cvičení:
Procvičení učiva z přednášek v dané chronologii.
Projekty:
Vypracování jednoho samostatného písemného referátu, který se skládá z části kombinatorické a části, týkající se teorie grafů. Každá ze dvou částí bude hodnocena buď 0, 5 nebo 10 bodů, tedy stylem NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ. Projekty naleznete na stránkách Petra Kováře. Někteří z vás NENAPSALI na odevzdaný projekt své JMÉNO. Tedy NENÍ v Katisu uveden jeho VÝSLEDEK. Proto se musí zmínění hříšníci dostavit osobně za opravujícím!
Čá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.
Výběry prvků s opakováním.
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.
Přirozená čísla a matematická indukce. Pojem matematického důkazu.
Počty podmnožin, důkazy vzorců pro kombinace a permutace.
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í.
Část II -- Úvod do teorie grafů
Pojem grafu, jeho souvislost s relacemi.
Podgrafy, isomorfizmus, 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.
Stromy a jejich charakterizace, isomorfizmus stromů.
Kořenové stromy.
Kostra grafu, (počet koster), problém minimální kostry.
Aplikace na hledání minimální kostry, algoritmy Jarníka a Borůvky.
Rovinné kreslení grafu, Eulerův vztah a jeho aplikace.
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.
Aplikace na párování a různé reprezentanty.
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 a jiné dokumenty.
Cvičení:
Procvičení učiva z přednášek v dané chronologii.
Projekty:
Vypracování jednoho samostatného písemného referátu, který se skládá z části kombinatorické a části, týkající se teorie grafů. Každá ze dvou částí bude hodnocena buď 0, 5 nebo 10 bodů, tedy stylem NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ. Projekty naleznete na stránkách Petra Kováře. Někteří z vás NENAPSALI na odevzdaný projekt své JMÉNO. Tedy NENÍ v Katisu uveden jeho VÝSLEDEK. Proto se musí zmínění hříšníci dostavit osobně za opravujícím!