Diskrétní matematika

V zimním semestru 2010/2011 přednáším Diskrétní matematiku [NDMI002]. Přednáška se koná každou středu od 14:00 v S3.

datum co se přednášelo [zdroj]
29. 9. 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]
6. 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. Skládání relací a funkcí a mírný zmatek v jejich značení. [K 1.1, 1.4, 1.5]
13. 10. Přednáška se nekoná, jestiž imatrikulace. Gaudeamus igitur!
20. 10. Ekvivalence: definice, popis pomocí rozkladu na ekvivalenční třídy. Uspořádání: definice, Hasseovy diagramy, nejmenší a minimální prvky. Kombinatorické počítání: počty funkcí a podmnožin. Binomická věta. [K 1.6, 2.1, 2.2, 3.1–3.3]
27. 10. Kombinatorika: důkaz Binomické věty, počet sudých a lichých podmnožin, počet řešení rovnice x1+…+xn=m v přirozených číslech. Úvod do diskrétní pravděpodobnosti: pravděpodobnostní prostory, elementární a složené jevy, Bertrandův paradox (barevné kartičky). [K 3.3, 10.2; P 1–15]
3. 11. Pravděpodobnost: podmíněná pravděpodobnost, věta o úplné pravděpodobnosti, Bayesova věta, nezávislé jevy, součinové prostory, střední hodnota a její linearita. [K 10.2, 10.3; P 16–30]
10. 11. Pravděpodobnost: rozptyl, Markovova a Čebyševova nerovnost, běžná rozdělení (alternativní, rovnoměrné, binomické, Poissonovo). Úvod do teorie grafů: definice, zoo grafů. [P 31–42; K 4.1]
17. 11. Přednáška se opět nekoná, anžto je stá(t|d)ní svátek.
24. 11. Teorie 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]
1. 12. Pozor! V prosinci dojde k permutaci některých přednášek:
  • 1. 12. se místo Matematické analýzy kolegy Šámala koná ještě jedna Diskrétka.
  • 8. 12. je naopak místo Diskrétky Analýza.
  • 9. 12. se místo Lineární algebry kolegy Sgalla koná Diskrétka (S3 15:40).
  • 15. 12. je místo Diskrétky Lineární algebra.
Reprezentace grafů pomocí matice sousednosti a incidence. Vzdálenosti v grafu (metrika). Operace s grafy: přidání a odebrání vrcholu/hrany, rozdě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. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. [K 4.2, 4.5, 5.1]
9. 12. 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. Kuratowského věta [bez důkazu]. [K 6.1, 6.2]
22. 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 (v próze i zpěvem). [K 6.3, 6.4]
5. 1. Čá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í.)
12. 1. Aplikace diskrétní matematiky aneb sbíráme ovoce okolo cesty, po níž jsme prošli: Erdősova-Szekeresova věta. Platónská tělesa a souvislost s rovinnými grafy. De Bruijnovy posloupnosti a jejich konstrukce pomocí orientovaných eulerovských tahů. [K 2.4, 6.3, 4.6]

Cvičení

Další dvě paralelky vedou Petr Kolman a Ondřej Pangrác, přednášky jsou téměř synchronní, takže si můžete vybrat kterékoliv cvičení ke kterékoliv přednášce.

Stránky mého cvičení.

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š