Předmět: 470-2301/01, 470-2301/03*, 470-2301/05: Diskrétní matematika (DIM)
Garant: Doc. Mgr. Petr Kovář, Ph.D.
Rozsah: 6 kreditů (2/2/2), *5 kreditů (2/2/1)
Akademický rok: ZS 2022/2023

Anotace

Předmět seznamuje studenty se základními pojmy diskrétní matematiky, se kterými se nejčastěji pracuje v různých oblastech teoretické a aplikované informatiky. Cílem je naučit se používat tyto pojmy při exaktní formulaci a řešení praktických úloh.

Slovo "diskrétní" v názvu je míněno jako opak "spojitého"; tj. předmět se zabývá těmi oblastmi matematiky, kde uvažujeme celá čísla a jednotlivé konečné objekty. Diskrétní objekty jsou prezentovány převážně pomocí konečných množin a grafů.

Průběh přednášek

K dispozici bude přehled látky probrané v jednotlivých týdnech včetně elektronické prezentace.

Část I - Úvod do diskrétní matematiky

• Sumy a produkty, vybrané početní postupy. Aritmetická a geometrická posloupnost.
• Kombinace a permutace. Výběry prvků bez opakování, 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. Střední hodnota Náhodná čísla v počítači.
• Princip inkluze a exkluze. Dirichletův princip. Kombinatorické identity. Binomická věta.
• Rekurentní vztahy a jejich řešení.
• Základy modulární aritmetiky.
• 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 v počítači, 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 a praktické aplikace. Hamiltonovské grafy a jejich využití.
• 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. 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. Využití pro řešení přiřazovací úlohy a hledání systému různých reprezentantů.
• 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.)

Hodnocení

Zápočtové písemky (20 bodů)

Téměř každý týden v semestru (s výjimkou prvních dvou týdnů) budou prezenční studenti na cvičení psát krátkou dvoubodovou nebo tříbodovou zápočtovou písemku (celkem 10 písemek). K vyřešení bude zhruba 2-10 minut, podle obtížnosti příkladu. Alespoň týden před každou písemkou budou k dispozici zadání typových příkladů.
Během písemek není možno používat literaturu, ani zápisky. Za každou písemku můžete získat 0/1/2 body - rozuměj NE/TÉMĚŘ SPRÁVNĚ/ZCELA SPRÁVNĚ. Každá druhá písemka bude navíc obsahovat nějakou teoretickou otázku z látky probrané na přednáškách za 1 bod. Při  absenci se písemka hodnotí 0 body. Opravné písemky se nepíší. Při případné neúčasti máte možnost sami na webu zjistit, co bylo probráno a na jaké téma se bude další písemka psát.

Celkový počet bodů za zápočtové písemky vypočítáme na konci semestru tak, že každému sečteme body jeho čtyř nejlepších dvoubodových písemek a čtyř nejlepších tříbodových písemek. To bude celkový počet bodů za semestrální písemky.

Témata písemek a typové příklady písemek najdete v tabulce. Příklady na písemku budou vybrány ze stejných typů jako jsou v domácí úloze. Alespoň týden před písemkou budou k dispozici zadání příkladů.

Kombinovaní studenti píší jedinou zápočtovou písemku v jednom z tutoriálů. Tato písemka obsahuje pět příkladů a každý je hodnocen až 4 body. Příklady mohou být jak početní tak teoretické a jsou výhradně z kombinatoriky, tzn. nebude mezi nimi žádný z teorie grafů, která se probírá až na pozdějších tutoriálech.

Samostatný projekt (10 bodů)

V druhé polovině semestru budou zveřejněna témata samostatných projektů. Každý student vypracuje jedno zadání podle čísla, které mu bude přiděleno.
Projektům je věnována samostatná stránka.

Zkouška (70 bodů)

Ke zkoušce můžete jít, jestliže máte nárok na zápočet (máte alespoň 10 bodů a váš projekt je přijat)! Hlavní součástí zkoušky je písemná práce zhruba na 75 minut. Na písemné zkoušce můžete získat až 70 bodů.
Během zkoušky můžete používat vedle vlastní hlavy pouze jednu stranu A4 rukou psaných poznámek.
Na tomto "zlegalizovaném taháku" mohou být definice, věty a vztahy, ale "tahák" nesmí obsahovat řešené příklady .

Data a místnosti zkušebních termínů budou stanoveny koncem semestru v  systému Edison.

Můžete se podívat na vzorovou zkouškovou písemku ve formátu pdf:

• pro písemnou verzi zkoušky dim_vzorova_pisemka_zk.pdf,
• pro LMS Moodle verzi zkoušky dim_cvicna_zkouskova_pisemka_moodle.pdf.

Náhrada cvičení, která odpadla
Místnost C3	13.12.2022   od 12:15

Literatura

• M. Kubesa. Základy diskrétní matematiky, výukový text I (skripta online), FEI VŠB-TUO, 2012.
• P. Kovář. Úvod do teorie grafů, výukový text II (skripta online), FEI VŠB-TUO, 2012.
• P. Kovář. Algoritmizace diskrétních struktur, doplňkový výukový text (skripta online), FEI VŠB-TUO, 2016.
• P. Kovář. ZDM a ÚTG řešené příklady k procvičení, zadání příkladů (zadání příkladů online), řešené příklady (zadání a řešení příkladů online), 2018.

Multimediální řešené příklady

Připravili jsme sbírku řešených příkladů. Příklady jsou ve formě tzv. "pencastů", což jsou PDF soubory, které obsahují postup výpočtu s namluveným slovním komentářem. Pro jejichž přehrávání je nutno nainstalovat přehrávač livescribe software, který lze zdarma stáhnout.

Slides and books available for English speaking students

• P. Kovář: Lecture slides. (slides online), FEI VŠB-TUO, 2022.
• P. Kovář, T. Kovářová: Solved exercises. (sample problems online), FEI VŠB-TUO, 2021.
• Meyer. Lecture notes and readings for an open course (weeks 1-5, 8-10, 12-13), MIT, 2005.
• Diestel. Graph theory on-line preview (chapetrs 1-6), Springer, 2010.   (for free when downoloaded from university domain!)

Doplňková literatura

• J. Matoušek, J. Nešetřil. Kapitoly z diskrétní matematiky, Karolinum Praha 2000.
  (Kapitoly 1, 2 a kousek z 9 pro Část I přednášky. Kapitoly 3, 4, 5 pro Část II přednášky.)

10 výtisků knihy "Kapitoly z diskrétní matematiky" je v knihovně VŠB, prodejna skript ji neprodává. Knihu je možné koupit případně objednat v knihkupectvích. Vhodné zejména pro studenty s hlubším zájmem o předmět.

Literatura je doporučená, není povinná. Na přednáškách a cvičeních se dozvíte vše co je potřeba znát ke zkoušce.
Rozhodně není potřeba učit se nazpaměť pasáže z knih, látce je třeba rozumět!
Je možné používat i jiné úvodní knihy a skripta pro daný předmět, ovšem pozor: některé detaily na přednášce se mohou lišit od literatury (odchylky v definicích pojmů, které nejsou ustálené) a u zkoušky pak platí to, co bylo na přednášce.

Animace

Pro lepší pochopení vybraných pojmů můžete při studiu využít následující animace.

• ukázka Dijkstrova algoritmu
• k důkaz Eulerovy věty
• hledání isomorfismu grafů
• ukázka algoritmů pro hledání minimální kostry grafů
• ukázky uložení struktury grafu v počítači
• ukázky sledu, tahu a cesty v grafu