Diskrétní matematika

V zimním semestru 2012/2013 přednáším Diskrétní matematiku [NDMI002]. Přednáška se koná každé úterý od 9:00 v S5, v druhé paralelce pak ve čtvrtek od 14:00 v S3.

datum co se přednášelo [zdroj]
2. 10. Co je diskrétní matematika. Dva příklady úvodem: od skákání po schodišti přes Fibonacciho čísla až k čárovým kódům; tři domečky a tři studny. Jak se buduje matematika (definice, věty, důkazy, malá exkurze do logiky). Ukázky důkazů pár jednoduchých tvrzení. Notace. [K 1.1–1.3]
9. 10. Množiny a základní operace s nimi: průnik, sjednocení, vydělení podmnožiny, rozdíl, symetrická diference. Důkaz neexistence množiny všech množin. Kódování dvojic a kartézské součiny. Relace a způsoby jejich znázorňování (maticí sousednosti, různými grafy). Zobrazení neboli funkce a jejich vlastnosti. [K 1.1, 1.4, 1.5]
16. 10. Skládání relací a funkcí a mírný zmatek v jejich značení. Další druhy relací. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy. Uspořádání: definice, Hasseovy diagramy, nejmenší a minimální prvky. [K 1.6, 2.1, 2.2]
23. 10. Kombinatorické počítání: počet funkcí, prostých funkcí, permutací; počet všech podmnožin, sudých a lichých podmnožin, k-prvkových podmnožin. Kombinační čísla a jejich základní vlastnosti; binomická věta. [K 3.1–3.3]
30. 10. Princip inkluze a exkluze, problém šatnářky. [K 3.6, 3.7]
6. 11. Úvod do diskrétní pravděpodobnosti: pravděpodobnostní prostory, elementární a složené jevy, Bertrandův paradox (barevné kartičky). podmíněná pravděpodobnost, věta o úplné pravděpodobnosti, Bayesova věta, nezávislé jevy. [K 10.2, 10.3; P 1–22]
13. 11. Pravděpodobnost: Součinové prostory, střední hodnota a její linearita. [K 10.2, 10.3; P 23–30] Úvod do teorie grafů: definice a základní značení. [K 4.1]
20. 11. Teorie grafů: zoo grafů, isomorfismus grafů, odhad počtu neisomorfních grafů na n vrcholech, stupeň a skóre, princip sudosti, podgrafy a indukované podgrafy, cesty a kružnice v grafech, souvislost a komponenty souvislosti. [K 4.1, 4.2, 4.4 bez Věty o skóre]
27. 11. Vzdálenosti v grafu (metrika). Operace s grafy: přidání a odebrání vrcholu/hrany, dělení hrany, kontrakce hrany. Stromy: definice, lemma o koncovém vrcholu, princip stromové indukce, věta o charakterizaci stromů. Kostra grafu: definice, existence, význam. Na cvičení: Reprezentace grafů pomocí matice sousednosti a incidence. [K 4.2, 5.1]
4. 12. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Kreslení grafů do roviny. Trocha topologie roviny (oblouky, topologické kružnice, Jordanova věta o kružnici [bez důkazu]). K5 není rovinný. Stěny nakreslení a jejich hranice (u souvislých grafů to jsou uzavřené sledy). Kreslení na sféru, stereografická projekce a možnost zvolit si vnější stěnu. [K 4.5, 6.1, 6.2]
11. 12. Barvení map a Problém 4 barev. Převod pomocí duality na barvení rovinných grafů. Eulerova formule, triangulování grafů, horní odhad na počet hran rovinného grafu, existence vrcholu nízkého stupně. Věta o 5 barvách. Barevnost a degenerovanost grafu a souvislost mezi nimi. Kuratowského věta [bez důkazu]. [K 6.3, 6.4]
18. 12. Částečně uspořádané množiny: Linearizace částečného uspořádání, vnořování do inkluze, věta o Dlouhém a Širokém. Orientované grafy: úvod, silná a slabá souvislost, acyklické grafy a orientované stromy, topologické uspořádání grafu coby jiný pohled na linearizaci uspořádání. [K 2.2–2.4, 4.6] (Pozor, topologické uspořádání v Kapitolách není.)
8. 1. Aplikace diskrétní matematiky aneb sbíráme ovoce okolo cesty, po níž jsme prošli: Erdősova-Szekeresova věta o monotónní podposloupnosti. De Bruijnovy posloupnosti a jejich konstrukce pomocí orientovaných eulerovských tahů. Platónská tělesa a souvislost s rovinnými grafy. [K 2.4, 4.6, 6.3]

Cvičení

Přednáším v obou paralelkách a přednášky jsou téměř synchronní, takže si můžete vybrat kterékoliv cvičení ke kterékoliv přednášce.

Cvičení vedou Jiří Fink, Ida Kantor, Dušan Knop a Pavel Rytíř.

Zkoušky

Už je to tak, k přednášce patří i zkouška :) Na termíny se prosím zapisujte v SISu.

Ke zkoušce je potřeba:

Všechny definice i tvrzení byste měli umět přesně formulovat (se všemi předpoklady, a to i na známku dobře) a dokázat (s výjimkou vět, jejichž důkaz jsem nepřednášel).

Přeji hodně štěstí a čistou mysl.

Literatura

Stránku spravuje Martin Mareš