Diskrétní matematika - přednáška ZS 2024/2025

Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky.

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

Pokud chcete mít dopředu představu, jaká témata se budou přibližně probírat, můžete se podívat na předchozí běh přednášky v mém podání. (Nicméně nějaké drobné odchylky nejspíš nastanou, mj. proto, že tehdejší běh byl ovlivněný online výukou.)

Doporučená literatura

J. Matoušek, J. Nešetřil, Kapitoly z Diskrétní Matematiky

Odkazy na cvičení (této paralelky)

Pondělí 12:20 a 14:00 v N7 s Klárou Grinerovou

Pondělí 14:00 v N4 s Mikulášem Zindulkou

Pondělí 14:00 v N6 s Petrem Martinkem

Středa 14:00 v N5 s Josefem Tkadlecem

Čtvrtek 14:00 v N4 se mnou

Průběh přednášek

Přednáška 1 Motivace: kombinatorika, pravděpodobnost a teorie grafů. (Příklady: Problém šatnářky, barvení map.) Základní pojmy a značení: množiny, zmínka potíží při příliš volném pojetí množiny, operace s množinami, další značení (sumy, součiny, celá část). Výroková logika: výrok (intuitivně), logické spojky, kvantifikátory. Příklady důkazů: jednoduchý důkaz přímo, důkaz sporem že odmocnina ze 2 je iracionální.

Přednáška 2 Důkaz matematickou indukcí. Relace: intuitivní motivace, definice kartézského součinu a relace, znázorňování relací. Vlastnosti relací: reflexivita, symetrie a tranzitivita. Relace ekvivalence a třídy ekvivalence. Věta o rozkladu na třídy ekvivalence.

Přednáška 3 Částečná uspořádání: (slabá antisymetrie) a definice částečného uspořádání, částečně uspořádaná množina. Porovnatelé prvky, řetězec a antiřetězec, bezprostřední následník. Hasseův diagram (neformálně). Největší versus maximální prvek (podobně nejmenší a minimální). Věta o dlouhém a širokém. Funkce: definice, obvyklé značení, pár poznámek o funkcích, f(A) a f -1(B). Prostá funkce, funkce na a bijekce. Skládání funkcí a poznámka o skládání relací.

Přednáška 4 Kombinatorické počítání: tvrzení o počtu funkcí, tvrzení o počtu podmnožin, tvrzení o počtu sudých a lichých pdomnožin a tvrzení o počtu prostých funkcí. Permutace, poznámky o jejich zápisu a znázroňování, a ekvivalentní definice. Kombinační čísla, tvrzení o počtu k-prvkových podmnožin, základní vzorečky, binomická věta (důkaz jen náznakem).

Přednáška 5 Byl záskok, Jiří Fiala s Vámi probral (metodou inverzní výuky) princip inkluze a exkluze a problém šatnářky podle materiálů zde. Konkrétně se jedná o: motivační příklad na princip inkluze a exkluze; princip inkluze a exkluze (jako věta); počet permutací bez pevného bodu (motivováno jako substituční šifry bez pevného bodu, známé též jako problém šatnářky).

Přednáška 6 Základy pravděpodobnosti: motivační povídání a příklady. Konečný pravděpodobnostní prostor, jev a elementární jev. Uniformní prostor (všechny elementární jevy mají stejnou pravděpodobnost). Příklad s kartami, podmíněná pravděpodobnost. Příklad: spolehlivost testu a následně Bayesova věta. Nezávislost jevů. Součin pravděpodobnostních prostorů (za pár minut; v plánu zopakovat).

Přednáška 7 Pokračování se součinem pravděpodobnostních prostorů a nezávislost jevů závisejících na různých souřadnicích součinového prostoru (vysvětleno pořádně, ale neplánuju to zkoušet; můžete však použít v příkladech, pokud Vám to bude užitečné). Náhodná veličina, střední hodnota (poznámka o mediánu). Linearita střední hodnoty. Indikátor jevu a počítání s indikátory. Teorie grafů: motivace, definice grafu, standardní kreslení grafů. Důležité třídy grafů: úplné grafy Kn, nezávislé množiny In, kružnice Cn, cesty Pn (délky n), úplné bipartitní grafy Km,n, bipartitní graf obecně.