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 pár desítek minut až pár jednotek hodin po přednášce, občas možná až po víkendu.)

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

Pokud chcete mít představu, jak asi bude přednáška probíhat, můžete se podívat na její předchozí běh.

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

Zkoušení po zimním zkouškovém

Řádné termíny v zimním zkouškovém už uběhly. Nějaký dodatečný termín může být po zimním zkouškovém na vyžádání (ale rozhodně takových možností nebude hodně). Pokud máte zájem, napište mi email, ideálně do 4. března. Budeme se snažit domluvit na termínu (po 4. březnu ztratíte vliv na to, jestli nějaký termín bude a kdy). Případný další termín určitě nebude dříve než 12. března.

Požadavky na předtermín 3. 1. 2018

Vzhledem k tomu, že do předtermínu 3. 1. nebudou ještě probrána všechna témata, zde najdete další témata, která se mohou na předtermínu objevit. Odkazy jsou na knihu Kapitoly z diskrétní matematiky.

Erdős-Szekerésovo lemma/věta, Lemma 2.4.6, podle vydání 2009 (cvičení 10 v 6.2 ve vydání z roku 2000; velmi doporučuju čerpat z novější verze kapitol, budete-li mít možnost).

Definice náhodného grafu, Definice 10.2.6 podle vydání 2009 (Definice 9.2.6. ve vydání 2000). Pochopení může také výrazně pomoci se podívat na úlohu 10.2.7 (9.2.7 ve vydání 2000), ale nemá význam se učit řešení úlohy nazpaměť.

Existence velkých bipartitních podgrafů, Věta 10.4.1 podle vydání 2009 (9.4.1 ve vydání 2000).

Informace ke zkoušce

Termíny zkoušek najdete v SISu. Pro přihlášení na termín je potřeba mít buď zápočet nebo alespoň doporučení od cvičícího (to se hlavně týká předtermínu). 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 a do indexu. 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í:

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-: 8-15b; 4: 0-7b. (Pro jiné písemky může být bodování mírně upraveno podle obtížnosti písemky.)

Průběh přednášek

Přednáška 1 (6. 10.) Motivace. Základní pojmy a značení, množiny. Důkaz matematickou indukcí. Kartézský součin. Relace: reflexivita, symetrie, tranzitivita; relace ekvivalence a třídy ekvivalence. Tvrzení o rozkladu na třídy ekvivalence.

Přednáška 2 (13. 10.) Funkce: definice, prostá funkce, funkce na, bijekce, inverzní funkce a skládání funkcí. (Poznámky o inverzní relaci a skládání relací). Částečná uspořádání, porovnatelné prvky, řetězce, antiřetězce, Hasseův diagram. Maximální, největší, minimální a nejmenší prvek. Věta o dlouhém a širokém.

Přednáška 3 (20. 10.) Kombinatorické počítání: tvrzení o počtu funkcí, počtu podmnožin, počtu sudých a lichých podmnožin, počtu prostých zobrazení. Permutace, počet permutací (faktoriál), rozklad permutací na cykly. Kombinační čísla, množina N nad k, tvrzení o počtu k-prvkových podmnožin. Motivační příklad na princip inkluze a exkluze.

Přednáška 4 (27. 10.) Princip inkluze a exkluze, znění a důkaz. Problém šatnářky a počet permutací bez pevného bodu. Základy diskrétní pravděpodobnosti: pravděpodobnostní prostor (neúplná definice), diskrétní pravděpodobnostní prostor, elementární jev, jev, příklady pravděpodobnostních prostorů.

Přednáška 5 (3. 11.) Podmíněná pravděpodobnost, spolehlivost testu jako příklad na podmíněnou pravděpodobnost, Bayesova věta. Nezávislé jevy. Součin pravděpodobnostních prostorů. Náhodná veličina, střední hodnota. Indikátor jevu. Příklad: střední hodnota počtu 1 v náhodné posloupnosti 0 a 1 délky n, z definice a přes indikátory.

Přednáška 6 (10. 11.) Nezávislost náhodných veličin. Graf. Důležité grafy: úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf. Izomorfismus grafů. Sousednost (incidence), podgraf a indukovaný podgraf. Sled, tah a cesta v grafu. Relace ~ vyjadřující existenci cesty mezi dvěma vrcholy je ekvivalence. Souvislost grafu a komponenty souvislosti. Matice sousednosti.

Přednáška 7 (24. 11.) Věta o počtu sledů. Stupeň vrcholu a skóre grafu. Princip sudosti a počet vrcholů lichého stupně. Věta o skóre. Eulerovské grafy. Charakterizace eulerovských grafů pomocí souvislosti a sudosti stupňů vrcholů.

Přednáška 8 (1. 12.) Definice orientovaného grafu. Tah v orientovaném grafu, eulerovské orientované grafy. Vstupní a výstupní stupeň vrcholu v orientovaném grafu, silná a slabá souvislost. Charakterizace orientovaných eulerovských grafů (důkaz se předpokládá na cvičeních). Aplikace eulerovských grafů na existenci cycklických posloupností nul a jedniček obsahujících, pro dané k všechny možné k-tice po sobě jdoucích nul a jedniček právě jednou. Stromy, definice stromu a listu. Lemma o existenci listů a lemma o trhání listů (důkaz zatím pouze jedné implikace).

Přednáška 9 (8. 12.) Druhá implikace lemma o trhání listů. Věta o ekvivalentních charakterizacích stromů. Kostra grafu. Graf má kostru, právě když je souvislý. Definice oblouku v rovině.

Přednáška 10 (15. 12.) Drobná oprava definice oblouku; oblouková souvislost. Nakreslení grafu, rovinné nakreslení, rovinný graf. Eulerův vzorec pro rovinné grafy. Tvrzení o doplnění rovinného grafu na triangulaci. Důsledek o maximálním počtu hran rovinného grafu. Důsledek důsledku, každý rovinný graf obsahuje vrchol stupně nejvýše 5.

Přednáška 11 (22. 12.) Hlavně pro počítání příkladů: stupeň stěny; součet stupňǔ stěn je dvakrát počet hran; rovinný graf bez trojúhelníků s n vrcholy má nejvýše 2n-4 hran; duální graf (pouze obrázkem). Barvení grafu: obarvení k barvami, chromatické číslo. k-degnerovaný graf. Tvrzení o chrom. čísle k-degnerovaného grafu. Věta o 4 barvách (bez dk.); věta o 6 barvách jako důsledek tvrzení. Věta o 5 barvách (s důkazem).

Přednáška 12 (5. 1.) Erdős-Szekerésova věta (dva důkazy). Pravděpodobnostní důkazy: hledání velkého bipartitního podgrafu; náhodný graf G(n,p) a konkrétní příklad využití pro existenci grafu s 2^50 vrcholy bez nezávisle množiny velikosti 100 či úplného podgrafu velikosti 100. (Motivováno Ramseyovou větou.)