Podrobné informace o předmětu Diskrétní matematika:

• v KatISu
• předběžný průběh přednášek
• hodnocení písemek a referátů
• doporučená literatura

Následuje přehled látky probrané v jednotlivých týdnech včetně přednášek ke stažení (ve formátu postscript).

První přednáška

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 na množině (bez opakování). Ukázali jsme si, jak odvodit vztahy pro počet zmíněných výběrů.

Druhá přednáška

Na druhé přednášce jsme dokončili Kapitolu 1, permutace, kombinace a variace bez opakování, včetně příkladů.
Dále jsme probrali většinu Kapitoly 2: motivační příklady, pojem pravděpodobnostní prostor, funkce pravděpodobnosti i uniformní pravděpodobnost, dále nezávislé jevy, včetně příkladů.

Třetí přednáška

Nejprve jsme dokončili téma diskrétní pravděpodobnosti. Na příkladech byly probrány pojmy náhodná veličina a střední hodnota náhodné veličiny.
Hlavní téma přednášky byly důkazové techniky, zejména užití matematické indukce. V druhé části přednášky jsme užitím indukce a metodou dvojího počítání dokázali vztahy pro počty kombinatorických výběrů a některé vztahy pro kombinační čísla.

Čtvrtá přednáška

Čtvrtá přednáška byla věnována důkazům metodou počítání a relacím. Nejprve jsme odvodili některé kombinatorické identity a příkladech ukázali užití Dirichletovu principu.
V druhé části přednášky jsme se zaměřili na 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. Na závěr jsme zavedli pojem zobrazení a popsali důležité speciální typy zobrazení.

Pátá přednáška

Na páté přednášce byla probrána skládání zobrazení jak v maticovém zápisu, tak v zápisu pomocí permutací.
Dále jsme se věnovali a 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í.

Šestá přednáška

První část šesté přednášky byla věnována 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
V druhé části přednášky 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. Také jsme zavedli pojem podgrafu a věnovali jsme se isomorfismům grafů.

Sedmá přednáška

Sedmá přednáška byla věnována implementaci grafů v počítači a různým stupňům souvislosti grafů.
Nadefinovali jsme sled, tah a cestu v grafu a zavedli jsme pojem komponenty souvislosti. Velká část přednášky byla věnována prohledávání grafů postupem do šířky i do hloubky. Také jsme zavedli Eulerovské grafy a uvedli nutné a dostatečné podmínky pro to, aby bylo možné graf nakreslit jedním otevřeným či uzavřeným tahem.

Osmá přednáška

Po 14.11.2005, semestrální písemka

Devátá přednáška

Devátá přednáška byla věnována ohodnoceným grafům a hledání nejkratší cesty užitím Dijkstrova algoritmu.
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). Potom jsme zavedli vážené ohodnocení grafu a probrali Dijkstrův algoritmus pro hledání nejkratších cest v grafu z daného vrcholu.

Desátá přednáška

Nejprve 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ěstěného stromu.

Jedenáctá přednáška

Jedenáctá přednáška byla věnována kostrám, barvení a kreslení stromů.
Ukázali jsme si algoritmus pro určení isomorfismu dvou stromů. Převedli jsme každý strom na kořenový pěstěný strom a našůi jeho minimální kód.
V druhé části přednášky 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.

Dvanáctá přednáška

Dvanáctá přednáška bude věnována barvení grafů.
V závěru začneme poslední kapitolu: toky v sítích.

Třináctá přednáška

Třináctá přednáška byla věnována algortimu hledání maximálního toku v síti a aplikacím sítí. Ukázali jsme si nejen správnost algoritmu, ale také jak se algoritmus hledání maximálního toku v síti dá použít při hledání největšího párování nebo pro důkaz Hallovy věty.

Čtrnáctá přednáška

Po 9.1.2006, není

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.
Pokud navíc znáte nějaký unixový program, který upraví pěkně slajdy v souborech *.ps pro tisk tak, aby na jedné straně bylo více slajdů, napište mi (v ideálním případě příkaz pro příkazovou řádku ;o)