|
Diskrétní matematika ZS 2007/2008
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 postscript). K dispozici jsou také příklady na procvičení: dim_cviceni.ps, dim_cviceni.pdf
První přednáška, Út 2.10.2007Soubory: dim_prednaska01.ps, 'dim_prednaska01.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, Út 9.10.2007Soubory: dim_prednaska02.ps, 'dim_prednaska02.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ů.
Třetí přednáška, Út 16.10.2007Soubory: dim_prednaska03.ps, 'dim_prednaska03.pdf' se připravuje!. Hlavním tématem 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, Út 23.10.2007Soubory: dim_prednaska04.ps, 'dim_prednaska04.pdf' se připravuje!.
Č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 na příkladech ukázali užití Dirichletovu principu.
Pátá přednáška, Út 30.11.2007Soubory: dim_prednaska05.ps, 'dim_prednaska05.pdf' se připravuje!.
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í.
Šestá přednáška, Čt 6.11.2007Soubory: dim_prednaska06.ps, 'dim_prednaska06.pdf' se připravuje!.
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
Sedmá přednáška, Út 13.11.2007Soubory: dim_prednaska07.ps, 'dim_prednaska07.pdf' se připravuje!.
Na sedmé přednášce jsme zavedli pojem podgrafu.
Věnovali jsme se pojmu isomorfismus grafů, implementaci grafů v počítači a různým stupňům souvislosti grafů.
Osmá přednáška, Út 20.11.2007Soubory: dim_prednaska08.ps, 'dim_prednaska08.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. Začali jsme další kapitolu věnovanou stromům.
Devátá přednáška, Út 27.11.2007Soubory: dim_prednaska09.ps, 'dim_prednaska09.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.
Desátá přednáška, Út 3.12.2007Soubory: dim_prednaska10.ps, 'dim_prednaska10.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.
Jedenáctá přednáška, Út 10.12.2007Soubory: dim_prednaska11.ps, 'dim_prednaska11.pdf' se připravuje!. 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 si také správnost algoritmu a jeho další aplikace (hledání největšího párování, důkaz Hallovy věty).
Dvanáctá přednáška, Út 17.12.2007Soubory: dim_prednaska11.ps, 'dim_prednaska11.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.
Třináctá přednáška, Út 8.1.2007Pozvaná přednáška.
PoznámkaPokud 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.
|