Diskrétní matematika - přednáška

Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky. (Typicky se nové informace budou objevovat pár desítek minut až pár jednotek hodin po přednášce, občas možná až po víkendu.)

Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.

Pokud chcete mít představu, jak asi bude přednáška probíhat, můžete se podívat na její předchozí běh.

Doporučená literatura: J. Matoušek, J. Nešetřil, Kapitoly z Diskrétní Matematiky

Průběh přednášek

Přednáška 1 (6. 10.) Motivace. Základní pojmy a značení, množiny. Důkaz matematickou indukcí. Kartézský součin. Relace: reflexivita, symetrie, tranzitivita; relace ekvivalence a třídy ekvivalence. Tvrzení o rozkladu na třídy ekvivalence.

Přednáška 2 (13. 10.) Funkce: definice, prostá funkce, funkce na, bijekce, inverzní funkce a skládání funkcí. (Poznámky o inverzní relaci a skládání relací). Částečná uspořádání, porovnatelné prvky, řetězce, antiřetězce, Hasseův diagram. Maximální, největší, minimální a nejmenší prvek. Věta o dlouhém a širokém.

Přednáška 3 (20. 10.) Kombinatorické počítání: tvrzení o počtu funkcí, počtu podmnožin, počtu sudých a lichých podmnožin, počtu prostých zobrazení. Permutace, počet permutací (faktoriál), rozklad permutací na cykly. Kombinační čísla, množina N nad k, tvrzení o počtu k-prvkových podmnožin. Motivační příklad na princip inkluze a exkluze.

Přednáška 4 (27. 10.) Princip inkluze a exkluze, znění a důkaz. Problém šatnářky a počet permutací bez pevného bodu. Základy diskrétní pravděpodobnosti: pravděpodobnostní prostor (neúplná definice), diskrétní pravděpodobnostní prostor, elementární jev, jev, příklady pravděpodobnostních prostorů.

Přednáška 5 (3. 11.) Podmíněná pravděpodobnost, spolehlivost testu jako příklad na podmíněnou pravděpodobnost, Bayesova věta. Nezávislé jevy. Součin pravděpodobnostních prostorů. Náhodná veličina, střední hodnota. Indikátor jevu. Příklad: střední hodnota počtu 1 v náhodné posloupnosti 0 a 1 délky n, z definice a přes indikátory.

Přednáška 6 (10. 11.) Nezávislost náhodných veličin. Graf. Důležité grafy: úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf. Izomorfismus grafů. Sousednost (incidence), podgraf a indukovaný podgraf. Sled, tah a cesta v grafu. Relace ~ vyjadřující existenci cesty mezi dvěma vrcholy je ekvivalence. Souvislost grafu a komponenty souvislosti. Matice sousednosti.