Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Diskrétní matematika ZS 2017/2018

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 jsou i příklady na procvičení: dim_cviceni.pdf

 

První přednáška, Po 18.9.2017

Soubory: dim_kapitola01.pdf, dim_kapitola01_en.pdf.

Na první přednášce projdeme hodnocení písemek a referátů, podmínky získání zápočtu a zkoušky i doporučenou literaturu.
Probereme čá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. Nadefinujeme pojmy permutace množiny, kombinace a variace (bez opakování) na množině.

 

Druhá přednáška, Po 25.9.2017

Soubory: dim_kapitola02.pdf ,dim_kapitola02_en.pdf.

Na druhé přednášce probereme permutace, kombinace a variace bez opakování, včetně příkladů. Nadefinujeme pojmy permutace množiny, kombinace a variace (s opakováním) na množině. Ukážeme si, jak odvodit vztahy pro počet zmíněných výběrů. Začneme 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 2.10.2017

Soubory: dim_kapitola03.pdf, dim_kapitola03_en.pdf.

Dokončíme Kapitolu 2: pravděpodobnostní prostor, funkce pravděpodobnosti a nezávislé jevy. Na příkladech ukážeme pojmy náhodná veličina a střední hodnota náhodné veličiny, zmíníme podmíněnou pravděpodobnost.

 

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

Soubory: dim_kapitola04.pdf, dim_kapitola04_en.pdf.

Přednáška bude 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 16.10.2017

Soubory: dim_kapitola05.pdf, dim_kapitola06.pdf

Odvodíme některé kombinatorické identity a na příkladech ukážeme užití Dirichletovu principu. Dále zavedeme pojem relace. Popíšeme důležité vlastnosti relací a zaměřéme jsme se na pojem uspořádání a ekvivalence. Ukážeme souvislost mezi ekvivalencemi na množině a rozklady množiny.

 

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

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

Zavedeme pojem zobrazení a popsali důležité speciální typy zobrazení. Bude probrána skládání zobrazení jak v maticovém zápisu, tak v zápisu pomocí permutací. Další část přednášky věnujeme implementaci diskrétních struktur (posloupnost, relace, množina) a také souvisejícím algoritmům. Jedná 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 se budeme věnovat 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číme téma implementace algoritmických struktur.

 

Sedmá přednáška, Po 30.10.2017

Soubory: dim_kapitola08.pdf, dim_kapitola08_en.pdf.

Dále se 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. Budeme se věnovat i isomorfismům grafů.

 

Osmá přednáška, Po 6.11.2017

Soubory: dim_kapitola09.pdf, dim_kapitola09_en.pdf.

Budeme se věnovat implementaci grafů v počítači. Dále bude přednáška věnována souvislosti grafu. Nadefinujeme pojmy sled, tah a cesta v grafu a zavedeme pojem komponenty souvislosti. Další čá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ů.

 

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

Soubory: dim_kapitola10.pdf, dim_kapitola10_en.pdf.

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.

 

Desátá přednáška, Po 20.11.2017

Soubory: dim_kapitola11.pdf, dim_kapitola11_en.pdf.

Nejprve zavedeme pojem vzdálenosti v grafu a metriku grafu. Ukážeme si algoritmus pro sestavení metriky grafu (čtvercové matice udávající vzdálenost mezi každými dvěma vrcholy grafu). 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 27.11.2017

Soubory: dim_kapitola12.pdf, 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ů.

 

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

Soubory: dim_kapitola12.pdf, dim_kapitola12_en.pdf.

Převedeme jsme každý strom na kořenový pěstěný strom a najdeme jeho minimální kód. Probereme téma minimální kostry grafu. Dále zavedeme (dobré) barvení grafu a nadefinujeme rovinný graf. 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.

 

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

Soubory: dim_kapitola13.pdf, dim_kapitola13_en.pdf.

Ukážeme si Eulerův vzorec a budeme se věnovat některým jeho důsledkům. 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í.

 

Čtrnáctá přednáška, Po 18.12.2017

Soubory: dim_kapitola14.pdf, dim_kapitola14_en.pdf.

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í 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á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.


email
kancelář EA536, tel. 597 325 972
Upraveno: 04.09.2017