Následuje přehled látky probrané v jednotlivých týdnech včetně přednášek ke stažení (ve formátu postscript).
Přednášky zde najdete v elektronické formě ke stažení (asi) jeden den před přednáškou. Oproti loňskému roku budou soubory upravené.

První přednáška, Čt 5.10.2006

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ě. Ukázali jsme si, jak odvodit vztahy pro počet zmíněných výběrů.

Druhá přednáška, Čt 12.10.2006

Na druhé přednášce jsme dokončili Kapitolu 1, permutace, kombinace a variace bez opakování, včetně příkladů.
Dále jsme probrali většinu Kapitoly 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.

Třetí přednáška, Čt 19.10.2006

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 26.10.2006

Č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.
V druhé části přednášky jsme se zaměřili na 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. Na závěr jsme zavedli pojem zobrazení a popsali důležité speciální typy zobrazení.

Pátá přednáška, Čt 2.11.2006

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í.
Dále jsme se věnovali a 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í.

Šestá přednáška, Čt 9.11.2006

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
V druhé části přednášky 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.

Sedmá přednáška, Čt 16.11.2006

odpadla

Osmá přednáška, Čt 23.11.2006

semestrální písemka

Devátá přednáška, Čt 30.11.2006

Na deváté 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ů.
Nadefinovali jsme sled, tah a cestu v grafu a zavedli jsme pojem komponenty souvislosti. Velká část přednášky byla věnována prohledávání grafů postupem do šířky i do hloubky. Také jsme zavedli 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.

Desátá přednáška, Čt 7.12.2006

Desátá přednáška byla věnována 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). Potom jsme zavedli vážené ohodnocení grafu a probrali Dijkstrův algoritmus pro hledání nejkratších cest v grafu z daného vrcholu.

Začali jsme další kapitolu věnovanou stromům.

Jedenáctá přednáška, Čt 14.12.2006

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.
Ukázali jsme si algoritmus pro určení isomorfismu dvou stromů. Převedli jsme každý strom na kořenový pěstěný strom a našli jeho minimální kód.

Dvanáctá přednáška, Čt 21.12.2006

Na dvanácté 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. Zmínili jsme se také o hamiltonovských grafech.

Třináctá přednáška, Čt 11.1.2007

Na třinácté 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).

Čtrnáctá přednáška, Čt 18.1.2007

Přednáška Prof. Frončka o losování sportovních turnajů s využitám teorie grafů.

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.
Vzhledem k nekompatibilitě PDF prohlížečů jsem převedl přednášky do PDF a multi soubory dále nepoužívám. Každý si je může snadno vytvořit pomocí volně dostupných programů pro příslušný operační systém.