|
Diskrétní matematika ZS 2022/2023Toto není stránka aktuálního akademického roku.
Tady je přehled látky probrané v jednotlivých týdnech.
Přednášky jsou v elektronické formě ke stažení, obvykle jsou den, dva před přednáškou aktualizovány (ve formátu PDF). K dispozici je přehled příkladů počítaných na cvičení: zadání příkladů (zadání příkladů online), řešené příklady (zadání a řešení příkladů online).
První přednáška, Po 19.9.2022Soubory: dim_kapitola00.pdf, dim_kapitola00_en.pdf. dim_kapitola01.pdf, dim_kapitola01_en.pdf.
Na první přednášce jsme prošli hodnocení písemek a projektů, podmínky získání zápočtu a zkoušky i doporučenou literaturu.
Druhá přednáška, Po 26.9.2022Soubory: 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ů. Na příkladech jsme ukázali použití kombinatorických pravidel součtu a součinu. Byly nadefinovány pojmy permutace množiny, kombinace a variace (s opakováním) na množině. Ukázali jsme, jak odvodit vztahy pro počet zmíněných výběrů.
Třetí přednáška, Po 3.10.2022Soubory: dim_kapitola03.pdf, dim_kapitola03_en.pdf. Probrali jsme diskrétní pravděpodobnost: motivační příklady, pojem pravděpodobnostní prostor, funkce pravděpodobnosti, uniformní pravděpodobnost i dále nezávislé jevy, včetně příkladů. 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, Po 10.10.2022Soubory: dim_kapitola04.pdf, dim_kapitola04_en.pdf. Přednáška byla věnována dalším početním postupům, zejména užití principu inkluze a exkluze. Na příkladech jsme odvodili některé kombinatorické identity a ukázali jsme použití metody počítání možností (Dirichletova principu).
Pátá přednáška, Po 17.10.2022Soubory: dim_kapitola05.pdf, dim_kapitola05_en.pdf. Přednáška byla věnována rekuretním vztahům, zejména lineárním, a metodám jejich řešení. Věnovali jsme se lineárním homogenním i nehomogenním rekurentním rovnicím s konstantními koeficienty. Ukázali jsme praktické úlohy, které lze popsat a řešit pomocí rekurencí.
Šestá přednáška, Po 24.10.2022Soubory: dim_kapitola06.pdf, dim_kapitola06_en.pdf, dim_kapitola07.pdf.
Probrali jsme implementace 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.
Sedmá přednáška, Po 31.10.2022Soubory: dim_kapitola08.pdf, dim_kapitola08_en.pdf. Dokončili jsme kongruence a ukázali jsme, jak jednoduché kongruence řešit.
Osmá přednáška, Po 7.11.2022Soubory: dim_kapitola09.pdf, dim_kapitola09_en.pdf, dim_kapitola10.pdf, dim_kapitola10_en.pdf. Na přednášce budeme věnovat základním pojmům teorie grafů. Zavedeme pojem grafu, stupeň vrcholu a některé základní typy grafů jako kompletní graf, kompletní bipartitní graf, cykly a cesty. Také zavedeme pojem stupňové posloupnosti a probereme větu Havla-Hakimiho. Další část přednášky bude věnována pojmu isomorfismu grafů a implementaci grafů v počítači. Nadefinujeme pojmy sled, tah a cesta v grafu a zavedeme pojem souvislosti grafu a komponent grafu.
Devátá přednáška, Po 14.11.2022Soubory: dim_kapitola10.pdf, dim_kapitola10_en.pdf. dim_kapitola11.pdf, dim_kapitola11_en.pdf. Budeme se věnovat prohledávání grafů postupem do šířky i do hloubky, probereme i různé stupně souvislosti grafů. Nadefinujeme také eulerovské grafy a uvedeme nutné a dostatečné podmínky, aby bylo možné graf nakreslit jedním otevřeným či uzavřeným tahem. Zavedeme pojem hamiltonovského grafu a uvedeme několik dostatečných podmínek pro to, aby v grafu existoval hamiltonovský cyklus. Dále se budeme věnovat ohodnoceným grafům a hledání nejkratší cesty užitím Dijkstrova algoritmu. Zavedeme pojem vzdálenosti v grafu a metriku grafu. Ukážeme algoritmus pro sestavení metriky grafu (čtvercové matice udávající vzdálenost mezi každými dvěma vrcholy grafu).
Desátá přednáška, Po 21.11.2022Soubory: dim_kapitola12.pdf, dim_kapitola12_en.pdf.
Zavedeme vážené ohodnocení grafu a probereme Dijkstrův algoritmus pro hledání nejkratších cest v grafu z daného vrcholu.
Jedenáctá přednáška, Po 28.11.2022Soubory: dim_kapitola13.pdf, dim_kapitola13_en.pdf. Ukážeme horní a dolní odhady barevnosti grafu. Vyřešíme několik příkladů pro určení barevnosti grafu. Toto téma nebudeme letos probírat na cvičení. Dále nadefinujeme rovinný graf. Ukážeme Eulerův vzorec a budeme se věnovat některým jeho důsledkům, probereme kriteria rozpoznání rovinného grafu. Ukážeme, co je to duální graf rovinného grafu.
Dvanáctá přednáška, Po 5.12.2022Soubory: dim_kapitola14.pdf, dim_kapitola14_en.pdf. Na přednášce začneme poslední kapitolu: toky v sítích. Budeme se věnovat algortimu hledání maximálního toku v síti a aplikacím sítí. Ukážeme také správnost algoritmu a jeho další aplikace (hledání největšího párování, důkaz Hallovy věty). Probereme další aplikace Ford-Fulkersonova algoritmu. Ukážeme, 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 bude věnována řešeným příkladům.
PoznámkaPokud 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. Toto není stránka aktuálního akademického roku.
|