Diskrétní matematika

V zimním semestru 2016/2017 přednáším Diskrétní matematiku pro matematiky [NMIN105]. Přednáška se koná každý pátek od 9:00 v M1.

datum co se přednášelo [zdroj]
7. 10. Značení: sumy, produkty, množiny a operace s nimi. Množina všech množin neexistuje. Kartézské součiny a relace. Funkce a jejich vlastnosti. [K 1.2, 1.4, 1.5]
14. 10. Operace s relacemi. Ekvivalence a uspořádání. Popis ekvivalence pomocí rozkladu na třídy. Kombinatorické počítání: funkce, prosté funkce, permutace, podmnožiny (pomocí charakteristických funkcí), k-prvkové podmnožiny. Kombinační čísla. [K 1.6, 3.1–3.3]
21. 10. Kombinační čísla: základní vlastnosti, binomická věta a její důsledky (součet a alternující součet kombinačních čísel), Pascalův trojúhelník, počet řešení rovnice x1 + … + xk = n. Princip inkluze a exkluze (zatím bez důkazu) a jeho použití pro problém šatnářky (počet permutací bez pevného bodu). Odhad růstu faktoriálu. [K 3.3, 3.4, 3.6, 3.7]
28. 10. Přednáška se nekoná. Václave, Václave, vévodo náš, buď pozdraven ty, kdož v péči nás máš…
4. 11. A-G nerovnost. Důkaz principu inkluze a exkluze. Částečně uspořádané množiny: minimální, maximální, nejmenší a největší prvky. Příklady různých uspořádání a jejich znázornění Hasseovými diagramy. [K 3.6, 2.1]
11. 11. Částečně uspořádané množiny: součin uspořádání, isomorfismus, inkluze je isomorfní s mocninou 2-prvkového lineárního uspořádání. Lexikografické uspořádání. Existence minimálního prvku a věta o lineárním rozšíření pro konečné množiny. Reprezentace částečných uspořádání pomocí inkluze. Řetězce, antiřetězce a věta o dlouhém a širokém. [K 2.2–2.4, 7.2]
18. 11. Věta o monotónní posloupnosti (Erdős, Szekeres). Úvod do teorie grafů: definice a základní značení, zoo grafů, bipartitnost, stupeň vrcholu, regulární graf, isomorfismus grafů, odhad počtu neisomorfních grafů na n vrcholech. [K 2.4, 4.1, 4.4 bez Věty o skóre]
25. 11. Grafy: Princip sudosti. Podgrafy a indukované podgrafy, grafové operace (přidání a odebrání vrcholu/hrany, dělení hrany), cesty a kružnice v grafech, souvislost a komponenty souvislosti, metrika v grafu. Stromy: definice, lemma o listu, princip indukce odtrháváním listů. [K 4.2, 5.1]
2. 12. Charakterizační věta pro stromy (5 ekvivalentních vlastností). Zakořeněné a pěstované stromy a jejich isomorfismy. [K 5.1, 5.2]
9. 12. Isomorfismus stromů: kódování pěstovaných stromů závorkami, kódování pro zakořeněné stromy, převod obecných stromů na zakořeněné pomocí centra. Kostra grafu, problém minimální kostry a Jarníkův algoritmus. [K 5.2–5.4] (bez Kruskalova algoritmu)
16. 12. Kreslení grafů jedním tahem: věta o existenci uzavřeného eulerovského tahu. Cykly (eulerovské podgrafy) a jejich popis pomocí vektorových prostorů. [K 4.5, 13.4]
6. 1. Ramseyova věta pro grafy, vícebarevná Ramseyova věta, dolní odhad Ramseyových čísel pravděpodobnostní metodou. [K 11.1–11.3]
13. 1. Cayleyho formule pro počet koster úplného grafu, důkaz pomocí obratlovců. Zmínka o počítáni koster obecných grafů (rekurence s mazáním a kontrakcí hran). Mohutnosti množin, Cantorova-Bernsteinova věta a její grafový důkaz. Které věty z Diskrétky platí pro nekonečné množiny/grafy? Zmínka o axiomu výběru, principu dobrého uspořádání a Zornovu lemmatu (vše bez důkazu). [D; K 8.1, 8.3]

Cvičení

K přednášce patří cvičení. Vedou je tito kolegové:

Druhé paralelce přednáší Martin Tancer, cvičení vedou Jana Novotná a Jana Syrovátková. Pozor na to, že paralelky se mohou lišit obsahem a pořadím výuky.

Zkoušky

Ke zkoušce je potřeba zápočet, znalost odpřednesené látky (definice, věty, důkazy, …) a schopnost ji aplikovat (řešit příklady, dokazovat tvrzení podobná těm z přednášky). Doporučena je dobrá nálada a čistá mysl :)

Zkouška je ústní s písemnou přípravou: zadám několik příkladů, ty si v klidu vyřešíte na papíře, o řešení pak spolu diskutujeme a pokud není ideální, dostanete šanci jej opravit, případně malou nápovědu.

Na zkoušky se prosím přihlašujte v SISu. Přihlásit se můžete i předtím, než získáte zápočet, ale na samotnou zkoušku už je potřeba.

Literatura

Další odkazy

Stránku spravuje Martin Mareš