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.)
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
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 týká předtermínu, pokud bude - domluvíme se na nejbližší přednášce).
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-: 10-15b; 4: 0-9b. (Pro jiné písemky může být bodování mírně upraveno podle obtížnosti písemky.) A ještě jedno upozornění pro studenty z mého kroužku: příklad 3 ve vzorové písemce je shodný s domácím úkolem. To ale neznamená, že mám v plánu do písemky zadávat domácí úkoly. Jedná se o vhodný příklad do vzorové písemky, abyste měli představu, jaké obtížnosti může být příklad v písemce. A zároveň se jednalo o vhodný domácí úkol.
Termíny zkoušek. Vypsané termíny zkoušek naleznete v SISu, konkrétně se jedná o předtermín pátek 13. 1., a dále středa 18. 1, středa 25. 1. a úterý 31. 1. Nové: Vypsal jsem už i slibovaný termín v únoru a to ve čtvrtek 16. 2. V případě zájmu o zkoušku po zkouškovém období mne, prosím, kontaktujte emailem (zkusíme se domluvit).
Přednáška 1 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). Kartézský součin a relace. Reflexivita, symetrie, tranzitivita; relace ekvivalence a definice třídy ekvivalence.
Přednáška 2 Tvrzení o třídách ekvivalence. 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). Částečně uspořádaná množina. Největší, maximální, nejmenší a minimální prvek v částečném uspořádání. Nesrovnatelné prvky, řetězec a antiřetězec. Bezprostřední následník a Hasseův diagram (jen neformálně).
Přednáška 3 Věta o dlouhém a širokém. Axiom výběru. 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.
Přednáška 4 (Záskok J. Kynčl) Permutace (dokončení). Kombinační čísla, počet k-prvkových podmnožin n-prvkové množiny, Pascalův trojúhelník, binomická věta, znění multinomické věty. Princip inkluze a exkluze. Permutace bez pevných bodů (problém šatnářky).
Přednáška 5 Permutace bez pevných bodů (dokončení). Teorie grafů. Graf, vrcholy a hrany. Základní třídy grafů (úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf). 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ů (zatím jen znění).
Přednáška 6 Věta o počtu sledů - důkaz. Stupeň vrcholu, skóre grafu. Princip sudosti, důsledek o počtu vrcholů lichého stupně (neplatí pro nekonečné grafy). Věta o skóre. Uzavřený eulerovský tah a eulerovské grafy. Věta o eulerovských grafech. (Poznámka o hamiltonovských kružnicích.)
Přednáška 7 Orientované grafy. Orientovaný sled (podobně se dá zavést orientovaný/á cesta, tah, kružnice). Vstupní a výstupní stupeň v orientovaném grafu. Slabá a silná souvislost. Věta o orientovaném eulerovském tahu (důkaz bude 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. Tvrzení o listech (existence listů) a tvrzení o trhání listů. Ekvivalentní charakterizace stromů (důkaz příště).
Přednáška 8 Důkaz tvrzení o ekvivalentní charakterizaci stromů. Poznámka o složitosti algoritmů. Zakořeněné a pěstované stromy a jejich izomorfismus. Kód pěstovaného stromu; různé pěstované stromy mají různý kód.
Přednáška 9 Izomorfismus pro zakořeněné stromy. Excentricita vrcholu a centrum grafu. Izomorfismus pro stromy. Kostra, existence kostry v souvislém grafu. Problém minimální kostry na grafu s váhovou funkcí (ohodnocením hran). Krushkalův "hladový" algoritmus. Pomocné lemma o přidávání hrany do množiny hran bez cyklů.
Přednáška 10 K důkazu korektnosti Krushkalova algoritmu jsme si zatím pořádně dokázali, že výstupem algoritmu je nějaká kostra, zbytek odložen. Rovinné grafy: oblouk, nakreslení grafu, rovinné nakreslení. Oblouková souvislost a stěny. Eulerův vzorec pro rovinné grafy. Tvrzení o maximálním možném počtu hran v rovinném grafu.
Přednáška 11 Dokončení/oprava důkazu Krushkalova algoritmu. Stupeň stěny a analogie pricipu sudosti vzhledem ke stupňům stěn. Počet hran rovinných grafů bez trojúhelníků. Každý rovinný graf má vrchol stupně nejvýše 5. Barvení grafů - obarvení k barvami a chromatické číslo. Věta o čtyřech barvách bez důkazu. Věta o šesti barvách přes k-degenerované grafy. Věta o pěti barvách s důkazem přes "dvoubarevné komponenty".
Přednáška 12 Dijkstrův algoritmus pro hledání nejkratších cest z jednoho zadaného vrcholu do všech ostatních vrcholů. Erdős-Szekeresova věta o monotónních posloupnostech (důkaz přes větu o dlouhém a širokém).
Přednáška 13 Prostor kružnic: eulerovské množiny hran v grafu. Každou eulerovskou množinu hran lze rozložit na kružnice. Věta o prostoru kružnic: 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.