Diskrétní matematika pro matematiky (NDMA005)

vyučující Robert Šámal

Aktuálně

Termíny zkoušky jsou vypsány v SISu. Přihlásit/odhlásit se je možné do půlnoci před zkouškou. Pokud možno však tuto krajní hranici nevyužívejte, pro umožnění lepšího plánování opravovatelů i kolegů, kterým byste třeba termín blokovali.
Zkouška bude písemná. Očekávat můžete --
příklady na znalost: věty z přednášky, důležité definice;
příklady na počítání: podobného charakteru jako byly na cvičení;
a příklady na dokazování: buď přímo věty z přednášky, nebo jejich modifikace.
Pro účely přípravy ke zkoušce, tady je seznam probrané látky. (Plán do konce semestru, některá témata ještě nebyla.) Většina témat je popsaná v knize Kapitoly z disk. matematiky. 1. kapitola byla probraná již v úvodním týdnu, v přednášce DM jsme se dále zabývali kapitolou 1.6. Dále pokračovaly kapitoly (občas v jiném pořadí): 2.1, 2.2, 2.3, 2.4, 3.1, 3.2, 3.3 (část), 3.6, 3.7, 4.1, 4.2, 4.4 (bez věty o skóre), 4.5, 4.8, 5.1, 5.3, 7.4, 7.2, 8.1+8.6, 13.4. Dále jsme mluvili o Axiomu výběru, Zornovu lemmatu a principu dobrého uspořádání.
Předtermín je plánován na poslední pátek před Vánoci: 21.12.2012 od 10 v M2 -- viz SIS. Přijít na předtermín bude možné i bez zápočtu, ale budu s cvičícími konzultovat, takže jestli někdo je na tom se zápočtem bledě, tak radši přijďte až na řádný termín.

SIS

v SISu lze najít oficiální info o předmětu, jakož i rozvrh přednášky a všech cvičení.

Literatura

Přednáška poměrně přesně sleduje knihu J. Matoušek, J. Nešetřil: Kapitoly z Diskrétní matematiky (ale nestihneme ji probrat celou). V knihovně i v prodejně skript najdete i další pěkné knihy k tématu. v SISu
Příklady na počítání najdete v doporučené učebnici, a samozřejmě na cvičeních. Pokud byste toužili po dalších příkladech na procvičení, můžete použít třeba tuto sbírku. Zájemcům o drsné příklady (mnohem těžší, než jsou potřeba pro absolvování této přednášky, zato často krásné) doporučuji knihu L. Lovász: Combinatorial Problems and Exercises.

Cvičení

Zisk zápočtu ze cvičení je nutnou podmínkou pro účast na zkoušce. Navíc, aktivní účast na cvičení vám výrazně usnadní skládání zkoušky. Podmínky k získání zápočtu vám sdělí příslušný cvičící.

Konzultační hodiny

Pokud jste něco na přednášce nechytili, a přemýšlení nad poznámkami, knihou, ani dotazy na cvičení nepomáhají, nebojte se domluvit si konzultaci. Např. ve čtvrtek 19-19:30 (před seminářem IPS), nebo v pátek od 12:20. V mé pracovně (nebo poblíž) - místnost 323 na Malé Straně. Každopádně prosím, domluvte se předem, že chcete přijít (a s čím máte obtíže). Když s sebou přivedete víc lidí najednou, tím lépe!

Co se dělo na přednáškách

1. přednáška 11.10.2012: Problém šatnářky (zatím bez řešení). Prosté zobrazení na konečné množině je na. Dirichletův princip. Počet usp. dvojic, zobrazení, prostých zobrazení.
2. přednáška 18.10.2012: Počet permutací, všech podmnožin, podmnožin dané velikosti, všech relací. Základní vlastnosti kombinačních čísel (symetrie, sčítací vzorec). Jak je velké sjednocení? Vysloven princip inkluze a exkluze. Hádanka: jaká je otázka, když odpověď je 2^{2 ⁿ} ?
Řešení: pokud X je n-prvková množina, tak uvedené číslo je velikost množiny P(P(X)) -- čili počet všech podmnožin množiny všech podmnožin X. Ještě jinak: množinový systém říkejme libovolné množině podmnožin X. Počítáme zde, kolik je všech množinových systémů.
3. přednáška 25.10.2012: Řešení šatnářky. Důkaz principu inkluze a exkluze.
4. přednáška 1.11.2012: Jiný důkaz principu inkluze a exkluze. Podrobnější pohled na relace ekvivalence. Hádanka: Kolik je latinských obdélníku nx1? Kolik nx2?
Řešení: těch nx1 je n!, pro nx2 je to n!.š(n).
Hádanka: Kolik je všech rozkladů množiny {1,2,3}? (A co {1,2,3,4}?)
Řešení: Pět, konkrétně jsou to { {1,2,3} }, { {1}, {2}, {3} }, { {1}, {2,3} }, { {2}, {3,1} }, { {3}, {1,2} }.
Pro čtyřprvkovou množinu dostaneme už 15 rozkladů, pro pětiprvkovou 52, pro šestiprvkovou 203. To není potřeba počítat vypsáním všech možností, dá se sestavit rekurentní vzoreček.
5. přednáška 8.11.2012: Důkaz věty o ekvivalenčních třídách. Uspořádání: příklady, znázorňování. Lineární rozšíření, min., max., nejv. a nejm. prvky.
Hádanka: jak vypadá uspořádání, které nemá minimální ani maximální prvek? Řešení: třeba celá čísla s běžným uspořádáním.
6. přednáška 15.11.2012: Existence minima a maxima. Existence lineárního rozšíření. Hypotéza 1/3-2/3. Vnoření částečných uspořádání do vícerozměrných krychlí. Řetězce a antiřetězce. Hádanka: Jaký je největší řetězec a antiřetězec v n-rozměrné hyperkrychli? (Pro antiřetězec nemusíte dokazovat, že je opravdu maximální, to není úplně lehké -- ale zkuste nalézt co nejlepší!)
7. a 8. přednáška 29.11.2012: Věta o dlouhém a širokém. Rozklady na řetězce a antiřetězce. Aplikace na monotónní posloupnosti. Zornovo lemma, axiom výběru a aplikace. Obrázky ordinálů. Spernerova věta -- znění, motivace.
9. přednáška 6.12.2012: Spernerova věta -- důkaz. Počítání dvěma způsoby. Grafy -- úvod. Co a proč to je, příklady důležitých grafů. Rovnost vs. izomorfismus grafů. Hádanka: Kolik je grafů s n vrcholy? Kolik jich může být navzájem neizomorfních?
10. přednáška 13.12.2012: Počet všech grafů s n vrcholy, odhad počtu neisomorfních. Stupeň v grafu. Princip sudosti. Incidenční matice. Součet stupňů v grafu je dvakrát počet hran. Důsledek: graf se sudými stupni nemá most. Podgraf, indukovaný podgraf. Cesta, kružnice, sled v grafu. Komponenty souvislosti. Kreslení jedním tahem -- důkaz zatím jen jednodušší části.
11. přednáška 20.12.2012 -- PLAN: Vzdálenost v grafu. Matice sousednosti a sledy v grafu. Stromy -- kap. 5.1 v knize.
12. přednáška 3.1.2013 -- PLAN: Problém minimální kostry v grafu -- kap. 5.3.
13. přednáška 10.1.2013 -- PLAN: Prostor kružnic -- kapitola 13.4 v knize. (Jen znění hlavní věty.)