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).
Oproti minulým letům 2005/06, 2006/07, 2007/08, 2008/09, 2009/10 , 2009/10 jsou soubory upravené a některé podmínky se liší.

K dispozici jsou i příklady na procvičení: dim_cviceni.pdf

První přednáška, Po 12.9.2011

Soubory: '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.
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 (bez opakování) na množině.

Druhá přednáška, Po 19.9.2011

Soubory: '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 (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 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ů.

Třetí přednáška, Po 26.9.2011

Soubory: 'dim_prednaska03.pdf' se připravuje!, 'dim_prednaska03_en.pdf' se připravuje!.

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. Na závěr přednášky jsme se věnovali důkazovým technikám, zejména užití matematické indukce.

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

Soubory: 'dim_prednaska04.pdf' se připravuje!, 'dim_prednaska04_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. 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.

Pátá přednáška, Po 10.10.2011

Soubory: 'dim_prednaska04.pdf' se připravuje!, 'dim_prednaska04_en.pdf' se připravuje!.

Přednáška byla věnována pojmu relace. 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í.

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

Soubory: '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.

Sedmá přednáška, Po 24.10.2011

Soubory: '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ů.

Osmá přednáška, Po 31.10.2011

Soubory: '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!.

Přednáška byla věnována vzdálenostem v grafu. Nadefinovali jsme sled, tah a cesta v grafu a zavedli jsme pojem komponenty souvislosti. Další část přednášky byla věnována prohledávání grafů postupem do šířky i do hloubky. Nadefinovali jsme Eulerovské grafy a uvedli nutné a dostatečné podmínky, aby bylo možné graf nakreslit jedním otevřeným či uzavřeným tahem.
Dále jsme se věnovali 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).

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

Soubory: 'dim_prednaska09.pdf' se připravuje!, 'dim_prednaska09_en.pdf' se připravuje!.

Zavedli vážené ohodnocení grafu a probrali Dijkstrův algoritmus pro hledání nejkratších cest v grafu z daného vrcholu. Dále 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.
Ukázali jsme si algoritmus pro určení isomorfismu dvou stromů.

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

Soubory: 'dim_prednaska10.pdf' se připravuje!, 'dim_prednaska10_en.pdf' se připravuje!.

Převedli jsme každý strom na kořenový pěstěný strom a našli jeho minimální kód. Začali jsme probírat téma minimální kostry grafu.

Jedenáctá přednáška, Po 21.11.2011

Soubory: 'dim_prednaska11.pdf' se připravuje!, 'dim_prednaska11_en.pdf' se připravuje!.

Na přednášce 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. Ukázali jsme Eulerův vzorec.

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

Soubory: 'dim_prednaska11.pdf' se připravuje!, 'dim_prednaska11_en.pdf' se připravuje!.

Věnovali jsme se Eulerovu vzorci a některým jeho důsledkům. Zmínili jsme se o hamiltonovských grafech. Na  přednášce jsme začali poslední kapitolu: toky v sítích.

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

Soubory: 'dim_prednaska11.pdf' se připravuje!, 'dim_prednaska11_en.pdf' se připravuje!.

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). Probrali jsme další aplikace Ford-Fulkersonova algoritmu. Ukázali jsme si, jak algoritmus použít při hledání největšího párování i při důkazu Hallovy věty.

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.