Diskrétní matematika ZS 2026/2027

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).
Oproti minulým letům jsou soubory upravené a některé podmínky se výrazně liší.

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 15.9.2026

Soubory: dim_kapitola00.pdf, dim_kapitola00_en.pdf, dim_kapitola01.pdf, dim_kapitola01_en.pdf.

Na první přednášce jsme uvedli hodnocení písemek a projektů, podmínky získání zápočtu a zkoušky i doporučenou literaturu.
Stručně jsme připomněli (látku předmětu Úvod do logického myšlení) množiny, jejich značení a množinové operace, dále relaci ekvivalence a relaci částečného uspořádání a jejímu znázornění.
Pracovali jsme s konečnými posloupnostmi i nekonečnými posloupnostmi, připomněli různá vyjádření aritmetické a geometrické posloupnosti a součty a také součiny těchto posloupností.

Druhá přednáška, Po 22.9.2026

Soubory: dim_kapitola02.pdf ,dim_kapitola02_en.pdf, dim_kapitola03.pdf, dim_kapitola03_en.pdf.

Probrali jsme 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ů.
Probrali jsme diskrétní pravděpodobnost: motivační příklady, pojem pravděpodobnostní prostor.

Třetí přednáška, Po 29.9.2026

Soubory: dim_kapitola03.pdf, dim_kapitola03_en.pdf, dim_kapitola04.pdf, dim_kapitola04_en.pdf.

Na přednášce jsme zavedli funkci 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. Přednáška byla věnována dalším početním postupům, zejména užití principu inkluze a exkluze.

Čtvrtá přednáška, Po 6.10.2026

Soubory: dim_kapitola04.pdf, dim_kapitola04_en.pdf, dim_kapitola07.pdf.

Na příkladech jsme odvodili některé kombinatorické identity a ukázali jsme použití metody počítání možností (Dirichletova principu).
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.

Pátá přednáška, Po 13.10.2026

Soubory: dim_kapitola05.pdf, dim_kapitola05_en.pdf, dim_kapitola07.pdf.

Dokončili jsme kapitolu 7, uvedli jsme 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.
Dále jsme se na přednášce věnovali rekuretním vztahům, zejména lineárním, a metodám jejich řešení.
Probrali jsme se lineární homogenní i nehomogenní rekurentní rovnice s konstantními koeficienty. Ukázali jsme praktické úlohy, které lze popsat a řešit pomocí rekurencí.

Šestá přednáška, Po 20.10.2026

Soubory: dim_kapitola05.pdf, dim_kapitola05_en.pdf, dim_kapitola06.pdf, dim_kapitola06_en.pdf.

Na přednášce jsme dokončili popis řešení nehomogenních rekurentních rovnic. Další část přednášky byla věnována základům modulární aritmetiky, počítání s konečnými množinami.
Zavedli jsme lineární kongruence a ukázali jsme, jak jednoduché kongruence řešit.

Sedmá přednáška, Po 27.10.2026

Soubory: dim_kapitola06.pdf, dim_kapitola06_en.pdf,

Dokončili jsme téma lineárních kongruencí a ukázali jsme, jak řešit soustavy kongruencí.

Osmá přednáška, Po 3.11.2026

Soubory: dim_kapitola08.pdf, dim_kapitola08_en.pdf. dim_kapitola09.pdf, dim_kapitola09_en.pdf.

Na přednášce jsme se 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. Zavedli jsme pojem stupňové posloupnosti a probrali větu Havla-Hakimiho.
Také jsme se věnovali jsme se pojmu isomorfismus grafů a implementaci grafů v počítači. Nadefinovali jsme sled, tah a cesta v grafu a zavedli jsme pojem souvislosti grafu a komponenty grafu.

Devátá přednáška, Po 10.11.2026

Soubory: dim_kapitola09.pdf, dim_kapitola09_en.pdf. dim_kapitola10.pdf, dim_kapitola10_en.pdf.

Věnovali jsme se prohledávání grafů postupem do šířky i do hloubky, probrali jsme i různé stupně souvislosti grafů. 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.
Byla zavedena vzdálenost v grafu a metrika grafu. Ukázali jsme algoritmus pro sestavení metriky grafu (čtvercové matice udávající vzdálenost mezi každými dvěma vrcholy grafu). 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, Po 17.11.2026

Soubory: dim_kapitola10.pdf, dim_kapitola10_en.pdf. dim_kapitola11.pdf, dim_kapitola11_en.pdf.

Státní svátek, přednáška odpadla.

Jedenáctá přednáška, Po 24.11.2026

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. Zavedli jsme pojem kořenového stromu a pěstěného stromu. Ukázali jsme, jak sestavit kód pěstovaného stromu. Ukázali jsme algoritmus pro určení isomorfismu dvou stromů. 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.

Dvanáctá přednáška, Po 1.12.2026

Soubory: dim_kapitola13.pdf, dim_kapitola13_en.pdf.

Dále jsme nadefinovali rovinný graf. Ukázali jsme Eulerův vzorec a některé jeho důsledky, probrali kriteria rozpoznání rovinného grafu. Ukázali jsme, co je to duální graf rovinného grafu.

Třináctá přednáška, Po 8.12.2026

Soubory: dim_kapitola14.pdf, dim_kapitola14_en.pdf.

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í. Ukázali jsme 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, 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. 596 995 972

Upraveno: 20.06.2026