Diskrétní matematika - přednáška

Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky. (Typicky se nové informace budou objevovat večer po přednášce nebo druhý den.)

Můžete se také pro zajímavost podívat na předchozí běh této přednášky, ale vůbec neslibuju, že vše bude stejně.

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

Doporučená literatura: J. Matoušek, J. Nešetřil, Kapitoly z Diskrétní Matematiky

Odkazy na jednotlivá cvičení

Zde najdete odkazy na jednotlivá cvičení:

Cvičení út 13:10 vedené mnou.

Cvičení st 9:00 a 10:40 vedené Michaelou Seifrtovou.

Cvičení čt 10:40 a 12:20 vedené Annou Mlezivovou.

Cvičení čt 10:40 vedené Janou Maxovou.

Cvičení čt 12:20, které vede Tung Anh Vu.

Cvičení čt 15:40 vedené Tomášem Honsem.

Nové! Dodatečný termín zkoušky

Termíny zkoušky během zimního zkouškového období už uplnuly. Mám v plánu vypsat jeden termín buď v průběhu letního semestru nebo v letním zkouškovém. Pokud stojíte o to ovlivnit, kdy tento termín bude, udělejte následující: Napište mi email s předmětem "DM termin zkousky" (ať se mi to snadno hledá) a svými preferencemi, kdy by pro Vás tento termín byl přijatelný. (Například to může být tvaru "březen a duben, nebo letní zkouškové".) Až shromáždím preference, tak se podle toho pokusím termín vypsat. Určitě není reálné, aby tento termín byl do 23. února, a nejspíš také ne, aby to byl týden na přelomu února a března.

Informace ke zkoušce

K tomu, abyste mohli skládat zkoušku, je potřeba mít zápočet; v případě předtermínu stačí doporučení od cvičícího. (Zápočet nebudu vyžadovat u přihlašování se na zkoušku, ať můžete trochu plánovat, ale je Vaší starostí si zápočet do termínu zkoušky obstarat.)

Těžištěm zkoušky bude písemka na 2 hodiny. Z písemky lze získat známky 1, 2, 3, 3- nebo 4. V případě zisku 1 nebo 4, dostanete známku hned do SISu. V případě zisku 2 nebo 3 se můžete známku pokusit o jeden stupeň vylepšit na následném ústním zkoušení. V případě zisku 3- je ústní zkoušení povinné (pokud nechcete rovnou 4), dá se vylepšit jedině na 3. Pokud dostanete po ústním zkoušení 2 nebo 3, tak se také můžete rozhodnout, že známku nechcete a přijdete na další termín.

Další upozornění:

Na zkoušky je potřeba se přihlásit přes SIS.
Zkontrolujte si, zda opravdu máte zápočet nebo doporučení cvičícího, jinak písemku psát nemůžete.
Rezervujte si na zkoušku i odpoledne, abyste se případně mohli zúčastnit i ústního zkoušení. (Pokud zkouška začíná až odpoledne, kvůli dostupnosti učeben, počítejte s tím, že se to může protáhnout do večera.)
Změna: Toto zkouškové se budu snažit být tolerantnější, pokud se nebudete moci dostavit na termín zkoušky, na který budete přihlášení. Přesto Vás prosím o ohleduplnost k ostatním i ke zkoušejícímu: Pokud víte dostatečně včas, že na zkoušku nechcete jít, tak se odhlaste přes SIS (ať kdyžtak uvolníte místo ostatním). Pokud se nestihnete odhlásit přes SIS, prosím, ať mi napíšete email, že nedorazíte.
Zkoušky jsou zatím vypsané vesměs v budově na Malé Straně. Nicméně je tam jedna výjimka, jedna zkouška je v budově impakt. Dejte si tedy pozor, abyste dorazili do správné budovy.

Vzorovou písemku naleznete zde. Bodování pro tuto konkrétní písemku by bylo 1: 23-30b; 2: 20-22b; 3: 16-19b; 3-: 10-15b; 4: 0-9b. (Pro jiné písemky může být bodování mírně upraveno podle obtížnosti písemky.)

Termíny zkoušek. Vypsané termíny zkoušek naleznete v SISu. Jedná se o termíny: 5. 1. (předtermín), 15. 1., 19. 1., 30. 1., 5. 2. a 9. 2. (Speciálně upozorňuji, že v týdnech 22. - 26. 1. a 12. - 16. 2. k dispozici nejsem.)

Informace navíc pro předtermín

5. 1. bude zkouškový předtermín (vypsaný v SISu). Jelikož se předtermín bude konat před poslední přednáškou, očekávám, že zájemci o předtermín se samostatně doučí látku odpovídající poslední přednášce. Tato látka je následující: Jednak se budou probírat odhady faktoriálu a kombinačních čísel, které naleznete v poznámkách zde (je možné vynechat využívající integrál). Dále ještě doděláme nějaká tvrzení o částečně uspořádaných množinách, podívejte se na věty 2 a 3 zde. (Při čtení ať už prvních nebo druhých ručně psaných poznámek je potřeba trošičku přemýšlet, u pár kroků je potřeba se zamyslet nad detaily. Ale očekávám, že studenti hlásicí se na předtermín by to měli zvládnout.)

K dotazům ohldeně videí

Přednášku nebude možné nahrávat. Existují však videa z dřívějšího běhu přednášky, kdy ji učil V. Jelínek. Ty lze najít na univerzitním streamu pokud zadáte do vyhledávání "DM" (je zároveň potřeba se přihlásit přes SIS).

Varování: Nepočítejte s tím, že vše budu říkat vše úplně stejně jako na videích. Videa Vám mohou být napomocná, ale i tak je potřeba sledovat, co se na přednášce probralo. Zkouška bude odpovídat tomu, co se probere letos.

Průběh přednášek

Přednáška 1 Motivace: kominatorika a teorie grafů. Základní pojmy a značení. Množiny - paradoxy při intuitivním vnímání množin. Poznámka o axiomatické definici. Základní množinové operace. Důkaz matematickou indukcí (jednoduchý příklad).

Přednáška 2 Kartézský součin a relace. Znázorňování relací. Funkce; prostá funkce, funkce na (surjektivní), bijekce. Skládání funkcí a relací. Mohutnost množin, spočetné množiny, Cantor-Bernsteinova věta (zatím bez důkazu). Reflexivita, symetrie, tranzitivita; relace ekvivalence a definice třídy ekvivalence. Tvrzení o třídách ekvivalence. (Důkaz nedokončený.)

Přednáška 3 Dokončení důkazu z minule. Částečně uspořádaná množina. (Ne)porovnatelné prvky, řetězec a antiřetězec. Bezprostřední následník a Hasseův diagram (jen neformálně). Největší, maximální, nejmenší a minimální prvek v částečném uspořádání. Věta o dlouhém a širokém. Axiom výběru. (Pouze úvodní motivace.)

Přednáška 4 Ekvivalentní reformulace axiomu výběru: Přes kartézský součin (zjevná reformulace), princip dobrého uspořádání (bez dk.), princip maximality - Zornovo lemma (bez dk.). Kombinatorické počítání: počet funkcí mezi dvěma konečnými množinami, počet podmnožin konečné množiny a počet podmnožin sudé velikosti, počet prostých funkcí, permutace, kombinační čísla, tvrzení o počtu k-prvkových podmnožin, binomická věta.

Přednáška 5 Princip inkluze a exkluze: Nejprve motivační příklad na dělitelnost, potom znění a důkaz. Permutace bez pevných bodů (problém šatnářky). Grafy: motivace, definice, základní třídy (úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf).

Přednáška 6 Izomorfismus grafů, incidence (sousednost), podgraf a indukovaný podgraf. Sled, tah a cesta. Souvislost grafu, existence cesty mezi dvěma vrcholy je ekvivalence, komponenty souvislosti. Matice sousednosti, věta o počtu sledů. Stupeň vrcholu, skóre grafu. Princip sudosti, důsledek o počtu vrcholů lichého stupně (neplatí pro nekonečné grafy).

Přednáška 7 Příklad, že důsledek z předchozí přednášky neplatí pro nekonečné grafy. Věta o skóre. (Znění vyžaduje drobnou korekci, je potřeba přidat předpoklad d_n ≤ n - 1. Budu se k tomu snažit vrátit na příští přednášce.) Uzavřený eulerovský tah a eulerovské grafy. Věta o eulerovských grafech. Poznámka o hamiltonovských kružnicích. Orientované grafy. Vstupní a výstupní stupeň v orientovaném grafu. Orientovaný sled (podobně se dá zavést orientovaný/á cesta, tah). Slabá a silná souvislost.

Přednáška 8 Drobná oprava u věty o skóre (viz výše). Věta o orientovaném eulerovském tahu (důkaz na cvičeních). Příklad aplikace - cyklické posloupnosti 0 a 1, ve kterých je každá možná k-tice právě jednou. Stromy. Lemma o listech (existence listů) a tvrzení o trhání listů. Ekvivalentní charakterizace stromů.

Přednáška 9 (záskok V. Jelínek) Počet koster v úplném grafu (důkaz přes povykosy). Jarníkův algoritmus pro hledání minimální kostry.

Přednáška 10 Prostor cyklů grafu: eulerovské množiny hran v grafu. Každou eulerovskou množinu hran lze rozložit na kružnice. Věta o prostoru cyklů: Charakteristické vektory nad Z_2 pro eulerovské množiny hran tvoří vektorový prostor nad Z_2, u kterého umíme určit dimenzi a (nějakou) bázi.

Přednáška 11 (záskok I. Kantor) Rovinné grafy: oblouk, rovinné nakreslení grafu. Topologická kružnice a zmínka o Jordanově větě o kružnici (bez důkazu). Oblouková souvislost a stěna rovinného nakreslení. Kuratowského věta (bez důkazu, pouze ukázána nerovinnost K₅). Eulerova formule pro rovinné grafy.

Přednáška 12 Tvrzení o maximálním možném počtu hran v rovinném grafu. Důsledek: Každý rovinný graf má vrchol stupně nejvýše 5. Trochu neformálně: Stupeň stěny a analogie pricipu sudosti vzhledem ke stupňům stěn. Počet hran rovinných grafů bez trojúhelníků. Barvení grafů - obarvení k barvami a chromatické číslo. Věta o čtyřech barvách bez důkazu. Tvrzení o barevnosti k-degenerovaných grafů a věta o šesti barvách přes k-degenerované grafy. Věta o pěti barvách (s důkazem).

Přednáška 13 Odhady faktoriálu a kombinačních čísel (podle poznámek zde). Dodatečná tvrzení k částečně uspořádaným množinám: Každou Č. U. M. lze rožířit na lineární. Každou konečnou Č. U. M. lze vnořit do množiny podmnožin uspořádané inkluzí.