Diskrétní matematika ZS 2016/2017

Tady je přehled látky probrané v jednotlivých týdnech. Přednášky jsou v elektronické formě ke stažení (asi) den, dva před přednáškou (ve formátu PDF).
Oproti minulým letům jsou soubory upravené a některé podmínky se výrazně liší.

K dispozici jsou i příklady na procvičení: dim_cviceni.pdf

První přednáška, Út 13.9.2016

Soubory: dim_kapitola01.pdf, dim_kapitola01_en.pdf.

Na první přednášce jsme prošli hodnocení písemek a referátů, podmínky získání zápočtu a zkoušky i doporučenou literaturu.
Probrali jsme část první kapitoly: posloupnosti a jejich součty a součiny, množiny a množinové operace, včetně kartézského součinu, potenční množiny a množinové systémy. Byly nadefinovány pojmy permutace množiny, kombinace a variace (bez opakování) na množině.

Druhá přednáška, Út 20.9.2016

Soubory: dim_kapitola02.pdf ,dim_kapitola02_en.pdf.

Na druhé přednášce jsme probrali permutace, kombinace a variace bez opakování, včetně příkladů. Byly nadefinovány pojmy permutace množiny, kombinace a variace (s opakováním) na množině. Ukázali jsme si, jak odvodit vztahy pro počet zmíněných výběrů. Začali jsme další kapitolu: motivační příklady, pojem pravděpodobnostní prostor, funkce pravděpodobnosti, uniformní pravděpodobnost i dále nezávislé jevy, včetně příkladů.

Třetí přednáška, Út 27.9.2016

Soubory: dim_kapitola03.pdf, dim_kapitola03_en.pdf.

Dokončili jsme Kapitolu 2: pravděpodobnostní prostor, funkce pravděpodobnosti a nezávislé jevy. Na příkladech byly probrány pojmy náhodná veličina a střední hodnota náhodné veličiny, zmínili jsme podmíněnou pravděpodobnost.

Čtvrtá přednáška, Út 4.10.2016

Soubory: dim_kapitola04.pdf, dim_kapitola04_en.pdf.

Přednáška byla věnována důkazovým technikám, zejména užití matematické indukce a důkazům metodou počítání.

Pátá přednáška, Út 11.10.2016

Soubory: dim_kapitola05.pdf, dim_kapitola06.pdf

Nejprve jsme odvodili některé kombinatorické identity a na příkladech ukázali užití Dirichletovu principu. Dále jsme zavedli pojem relace. Popsali jsme důležité vlastnosti relací a zaměřili jsme se na pojem uspořádání a ekvivalence. Ukázali jsme souvislost mezi ekvivalencemi na množině a rozklady množiny.

Šestá přednáška, Út 18.10.2016

Soubory: dim_kapitola06.pdf, dim_kapitola07.pdf, Algoritmizace diskrétních struktur

Zavedli jsme pojem zobrazení a popsali důležité speciální typy zobrazení. Byla probrána skládání zobrazení jak v maticovém zápisu, tak v zápisu pomocí permutací. Další část přednášky byla věnována implementaci diskrétních struktur (posloupnost, relace, množina) a také souvisejícím algoritmům. Jednalo se především o probrání všech uspořádaných i neuspořádaných dvojic, ověření, zda daná relace je symetrická či tranzitivní a implementaci množin. Dále jsme se věnovali implementaci některých algoritmů pro diskrétní struktury, zejména vygenerování všech variací a kombinací k prvků z n-prvkové množiny. Dokončili jsme téma implementace algoritmických struktur.

Sedmá přednáška, Út 25.10.2016

Soubory: dim_kapitola08.pdf, dim_kapitola08_en.pdf.

Dále jsme se na sedmé přednášce věnovali základním pojmům teorie grafů. Zavedli jsme pojem grafu, stupeň vrcholu a některé základní typy grafů jako kompletní graf, kompletní bipartitní graf, cykly a cesty. Také jsme zavedli pojem stupňové posloupnosti a probrali větu Havla-Hakimiho. Věnovali jsme se pojmu isomorfismus grafů.

Osmá přednáška, Út 1.11.2016

Soubory: dim_kapitola09.pdf, dim_kapitola09_en.pdf.

Na přednášce jsme se věnovali implementaci grafů v počítači a různým stupňům souvislosti grafů. Dále byla přednáška byla věnována souvislosti grafu. Nadefinovali jsme sled, tah a cesta v grafu a zavedli jsme pojem komponenty souvislosti. Další část přednášky byla věnována prohledávání grafů postupem do šířky i do hloubky, probrali jsme i různé stupně souvislosti grafů.

Devátá přednáška, Út 8.11.2016

Soubory: dim_kapitola10.pdf, dim_kapitola10_en.pdf.

Nadefinovali jsme eulerovské grafy a uvedli nutné a dostatečné podmínky, aby bylo možné graf nakreslit jedním otevřeným či uzavřeným tahem.
Zavedli jsme pojem hamiltonovského grafu a uvedli několik dostatečných podmínek pro to, aby v grafu existoval hamiltonovský cyklus. Dále jsme se věnovali ohodnoceným grafům a hledání nejkratší cesty užitím Dijkstrova algoritmu.

Desátá přednáška, Út 15.11.2016

Soubory: dim_kapitola11.pdf, dim_kapitola11_en.pdf.

Nejprve byla zavedena vzdálenost v grafu a metrika grafu. Ukázali jsme si algoritmus pro sestavení metriky grafu (čtvercové matice udávající vzdálenost mezi každými dvěma vrcholy grafu). Zavedli vážené ohodnocení grafu a probrali Dijkstrův algoritmus pro hledání nejkratších cest v grafu z daného vrcholu.

Jedenáctá přednáška, Út 22.11.2016

Soubory: dim_kapitola12.pdf, dim_kapitola12_en.pdf.

Dále byla zavedena třída grafů zvaných stromy a dokázali jsme několik základních vět pro stromy. Potom jsme zavedeli pojem kořenového stromu a pěstěného stromu. Ukázali jsme si, jak sestavit kód pěstovaného stromu. Ukázali jsme algoritmus pro určení isomorfismu dvou stromů.

Dvanáctá přednáška, Út 29.11.2016

Soubory: dim_kapitola12.pdf, dim_kapitola12_en.pdf.

Dále jsme zavedli (dobré) barvení grafu a nadefinovali rovinný graf. Na závěr jsme ukázali co je to duální graf rovinného grafu. Převedli jsme každý strom na kořenový pěstěný strom a našli jeho minimální kód. Probrali jsme téma minimální kostry grafu.

Třináctá přednáška, Út 6.12.2016

Soubory: dim_kapitola13.pdf, dim_kapitola13_en.pdf.

Ukázali jsme Eulerův vzorec a některé jeho důsledky. Zmínili jsme se o hamiltonovských grafech. Na  přednášce jsme začali poslední kapitolu: toky v sítích. Věnovali jsme se algortimu hledání maximálního toku v síti a aplikacím sítí.

Čtrnáctá přednáška, Út 13.12.2016

Soubory: dim_kapitola14.pdf, dim_kapitola14_en.pdf.

Ukázali jsme si také správnost algoritmu a jeho další aplikace (hledání největšího párování, důkaz Hallovy věty). Probrali jsme další aplikace Ford-Fulkersonova algoritmu. Ukázali jsme si, jak algoritmus použít při hledání systému reprezentantů i při důkazu Mengerových vět. Poslední část přednášky byla věnována řešeným příkladům.

Poznámka

Pokud najdete chybu v textu přednášek, dejte mi, prosím, vědět. Pokusím se chyby co nejdříve opravit.

Zpět na stránku předmětu Diskrétní matematika.

Petr<tečka>Kovar<zavináč>vsb<tečka>cz kancelář EA536, tel. 597 325 972

Upraveno: 10.01.2017