|
Diskrétní matematika ZS 2014/2015Toto 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í (asi) den, dva před přednáškou (ve formátu PDF). K dispozici jsou i příklady na procvičení: dim_cviceni.pdf
První přednáška, Po 15.9.2014Soubory: 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.
Druhá přednáška, Po 22.9.2014Soubory: 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, Po 29.9.2014Soubory: 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, Po 6.10.2014Soubory: 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, Po 13.10.2014Soubory: dim_kapitola05_en.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, Po 20.10.2014Soubory: dim_kapitola06_en.pdf, dim_kapitola07.pdf, dim_kapitola07_en.pdf. 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.
Sedmá přednáška, Po 27.10.2014Přednáška odpadla.
Osmá přednáška, Po 3.11.2014Soubory: dim_kapitola08_en.pdf. Dokončili jsme téma implementace algoritmických struktur. Dále jsme se na sedmé přednášce věnovali základním pojmům teorie grafů.
Devátá přednáška, Po 10.11.2014Soubory: dim_kapitola09_en.pdf. 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ů. 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.
Desátá přednáška, Po 17.11.2014Přednáška nebude.
Jedenáctá přednáška, Po 24.11.2014Soubory: dim_kapitola10_en.pdf, dim_kapitola11_en.pdf.
První část přednášky bude věnována 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.
Dvanáctá přednáška, Po 1.12.2014Soubory: dim_kapitola12_en.pdf. Dále zavedeme třídu grafů zvaných stromy a dokážeme několik základních vět pro stromy. Potom zavedeme pojem kořenového stromu a pěstěného stromu. Ukážeme si, jak sestavit kód pěstovaného stromu. Ukážeme si algoritmus pro určení isomorfismu dvou stromů. Převedeme jsme každý strom na kořenový pěstěný strom a najdeme jeho minimální kód.
Třináctá přednáška, Po 8.12.2014Soubory: dim_kapitola13_en.pdf. Začneme probírat téma minimální kostry grafu. Dále zavedeme (dobré) barvení grafu a nadefinujeme rovinný graf. Na závěr si ukážeme co je to duální graf rovinného grafu. Ukážeme si Eulerův vzorec a budeme se věnovat některým jeho důsledkům.
Čtrnáctá přednáška, Po 15.12.2014Soubory: 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 si 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 si, jak algoritmus použít při hledání největšího párování i při důkazu Hallovy věty.
PoznámkaPokud najdete chybu v textu přednášek, dejte mi, prosím, vědět. Pokusím se chyby co nejdříve opravit. Toto není stránka aktuálního akademického roku.Zpět na stránku předmětu Diskrétní matematika.
|