|
Diskrétní matematika ZS 2008/2009Toto 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.2008Soubory: 'dim_prednaska01.pdf' se připravuje!, 'dim_prednaska01_en.pdf' se připravuje!.
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.2008Soubory: 'dim_prednaska02.pdf' se připravuje!, 'dim_prednaska02_en.pdf' se připravuje!. Na druhé přednášce jsme dokončili Kapitolu 1, permutace, kombinace a variace bez opakování, včetně příkladů. Byly nadefinovány pojmy permutace množiny, kombinace a variace (bez opakování) na množině. Ukázali jsme si, jak odvodit vztahy pro počet zmíněných výběrů.
Třetí přednáška, Po 29.9.2008odpadla Čtvrtá přednáška, Po 6.10.2008Soubory: 'dim_prednaska02.pdf' se připravuje!, 'dim_prednaska02_en.pdf' se připravuje!. Probrali jsme Kapitolu 2: 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. Na závěr přednášky jsme se věnovali důkazovým technikám, zejména užití matematické indukce.
Pátá přednáška, Po 13.10.2008Soubory: 'dim_prednaska03.pdf' se připravuje!, 'dim_prednaska03_en.pdf' se připravuje!. 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 na příkladech ukázali užití Dirichletovu principu.
Šestá přednáška, Po 20.10.2008Soubory: 'dim_prednaska04.pdf' se připravuje!, 'dim_prednaska04_en.pdf' se připravuje!. Přednáška byla věnována pojmu 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. 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í.
Sedmá přednáška, Po 27.10.2008Soubory: 'dim_prednaska05.pdf' se připravuje!, 'dim_prednaska05_en.pdf' se připravuje!. První čá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.
Osmá přednáška, Po 3.11.2008Soubory: 'dim_prednaska06.pdf' se připravuje!, 'dim_prednaska06_en.pdf' se připravuje!.
Na sedmé 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.
Také jsme zavedli pojem stupňové posloupnosti a probrali větu Havla-Hakimiho.
Věnovali jsme se pojmu isomorfismus grafů, implementaci grafů v počítači a různým stupňům souvislosti grafů.
Devátá přednáška, Po 10.11.2008Soubory: 'dim_prednaska07.pdf' se připravuje!, 'dim_prednaska07_en.pdf' se připravuje!. 'dim_prednaska08.pdf' se připravuje!, 'dim_prednaska08_en.pdf' se připravuje!.
Osmá přednáška byla věnována ohodnoceným grafům a hledání nejkratší cesty užitím Dijkstrova algoritmu.
Desátá přednáška, Po 17.11.2008Odpadla.
Jedenáctá přednáška, Po 24.11.2008Soubory: 'dim_prednaska09.pdf' se připravuje!, 'dim_prednaska09_en.pdf' se připravuje!.
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.
Dvanáctá přednáška, Po 1.12.2008Soubory: 'dim_prednaska10.pdf' se připravuje!, 'dim_prednaska10_en.pdf' se připravuje!.
Na přednášce jsme zavedli (dobré) barvení grafu a nadefinovali rovinný graf.
Věnovali jsme se Eulerovu vzorci a některým jeho důsledkům.
Na závěr jsme ukázali co je to duální graf rovinného grafu.
Třináctá přednáška, Po 8.12.2008Soubory: 'dim_prednaska11.pdf' se připravuje!, 'dim_prednaska11_en.pdf' se připravuje!. 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).
Čtrnáctá přednáška, Po 15.12.2008Soubory: 'dim_prednaska11.pdf' se připravuje!, 'dim_prednaska11_en.pdf' se připravuje!. 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.
|