Zde se průběžně budou objevovat informace k přednášce z diskrétní matematiky.
Pokud hledáte kontakt na mě, tak se podívejte na moji domovskou stránku.
Pokud chcete mít dopředu představu, jaká témata se budou přibližně probírat, můžete se podívat na předchozí běh přednášky v mém podání. (Nicméně nějaké drobné odchylky nejspíš nastanou, mj. proto, že tehdejší běh byl ovlivněný online výukou.)
Pondělí 14:00 v N4 s Mikulášem Zindulkou
Pondělí 14:00 v N6 s Petrem Martinkem
Středa 14:00 v N5 s Josefem Tkadlecem
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í:
| Přednáška | Probraná témata | Slajdy |
|---|---|---|
| Přednáška 1 | Motivace: kombinatorika, pravděpodobnost a teorie grafů. (Příklady: Problém šatnářky, barvení map.) Základní pojmy a značení: množiny, zmínka potíží při příliš volném pojetí množiny, operace s množinami, další značení (sumy, součiny, celá část). Výroková logika: výrok (intuitivně), logické spojky, kvantifikátory. Příklady důkazů: jednoduchý důkaz přímo, důkaz sporem že odmocnina ze 2 je iracionální. | Velkou část ale ne vše naleznete v těchto slajdech. |
| Přednáška 2 | Důkaz matematickou indukcí. Relace: intuitivní motivace, definice kartézského součinu a relace, znázorňování relací. Vlastnosti relací: reflexivita, symetrie a tranzitivita. Relace ekvivalence a třídy ekvivalence. Věta o rozkladu na třídy ekvivalence. | Téměř vše naleznete v těchto slajdech (druhá půlka). |
| Přednáška 3 | Částečná uspořádání: (slabá antisymetrie) a definice částečného uspořádání, částečně uspořádaná množina. Porovnatelé prvky, řetězec a antiřetězec, bezprostřední následník. Hasseův diagram (neformálně). Největší versus maximální prvek (podobně nejmenší a minimální). Věta o dlouhém a širokém. Funkce: definice, obvyklé značení, pár poznámek o funkcích, f(A) a f -1(B). Prostá funkce, funkce na a bijekce. Skládání funkcí a poznámka o skládání relací. | Téměř vše naleznete v těchto a těchto slajdech (ale v jiném pořadí). |
| Přednáška 4 | Kombinatorické počítání: tvrzení o počtu funkcí, tvrzení o počtu podmnožin, tvrzení o počtu sudých a lichých podmnožin a tvrzení o počtu prostých funkcí. Permutace, poznámky o jejich zápisu a znázroňování, a ekvivalentní definice. Kombinační čísla, tvrzení o počtu k-prvkových podmnožin, základní vzorečky, binomická věta (důkaz jen náznakem). | Téměř vše naleznete v těchto slajdech (druhá půlka). |
| Přednáška 5 | Byl záskok, Jiří Fiala s Vámi probral (metodou inverzní výuky) princip inkluze a exkluze a problém šatnářky podle materiálů zde. Konkrétně se jedná o: motivační příklad na princip inkluze a exkluze; princip inkluze a exkluze (jako věta); počet permutací bez pevného bodu (motivováno jako substituční šifry bez pevného bodu, známé též jako problém šatnářky). | Téma naleznete v těchto slajdech, nicméně je pojaté jinak, než to bylo na přednášce. |
| Přednáška 6 | Základy pravděpodobnosti: motivační povídání a příklady. Konečný pravděpodobnostní prostor, jev a elementární jev. Uniformní prostor (všechny elementární jevy mají stejnou pravděpodobnost). Příklad s kartami, podmíněná pravděpodobnost. Příklad: spolehlivost testu a následně Bayesova věta. Nezávislost jevů. Součin pravděpodobnostních prostorů (za pár minut; v plánu zopakovat). | Téměř vše naleznete v těchto slajdech. |
| Přednáška 7 | Pokračování se součinem pravděpodobnostních prostorů a nezávislost jevů závisejících na různých souřadnicích součinového prostoru (vysvětleno pořádně, ale neplánuju to zkoušet; můžete však použít v příkladech, pokud Vám to bude užitečné). Náhodná veličina, střední hodnota (poznámka o mediánu). Linearita střední hodnoty. Indikátor jevu a počítání s indikátory. Teorie grafů: motivace, definice grafu, standardní kreslení grafů. Důležité třídy grafů: úplné grafy Kn, nezávislé množiny In, kružnice Cn, cesty Pn (délky n), úplné bipartitní grafy Km,n, bipartitní graf obecně. | Téměř vše naleznete v těchto a těchto slajdech. |
| Přednáška 8 | Definice základních grafových pojmů: izomorfismus, značení V(G) a E(G), doplněk, sousednost vrcholů a hran, podgraf a indukovaný podgraf; sled, tah a cesta. Tvrzení říkající, že existence cesty je ekvivalence. Komponenta souvislosti a souvislý graf. Matice sousednosti a věta o počtu sledů. Stupeň vrcholu a skóre grafu. Tvrzení: princip sudosti a důsledek, že počet vrcholů lichého stupně je v konečném grafu sudý (neplatí pro nekonečné grafy). Eulerovské grafy: zatím jen definice uzavřeného eulerovského tahu a eulerovského grafu. | Téměř vše naleznete v těchto, těchto a těchto slajdech. |
| Přednáška 9 | Věta: charakterizace eulerovských grafů pomocí souvislosti a sudých stupňů. Orientované grafy: definice orientovaného grafu, vstupní a výstupní stupeň, symetrizace, orientovaný tah (sled, cesta, kružnice), slabá a silná souvislost. Věta o orientovaných eulerovských grafech (důkaz ponechán na cvičení). Náznak aplikace: losovací zařízení neboli cyklické posloupnosti nul a jedniček, které obsahují všechny možné podposlounosti délky k právě jednou. Stromy: strom a list. Tvrzení/lemma o existenci listů. | Téměř vše naleznete v těchto a těchto slajdech. |
| Přednáška 10 | Tvrzení o trhání listů. Věta o ekvivalentních charakterizacích stromů. Kostra, tvrzení o existenci kostry. Rovinné grafy. Spojitá funkce z [0,1] do roviny (definice se nezkouší, a ještě k tomu jsem se v definici přepsal, upozorním na opravu příště). Oblouk. | Téměř vše naleznete v těchto a těchto slajdech. |
| Přednáška 11 | Koncové body oblouku. Narkeslení grafu a rovinné nakreslení. Rovinný graf. Obloukově souvislá množina a stěna (v rovinném nakreslení grafu). Eulerův vzorec pro rovinné grafy. Tvrzení o maximálním možném počtu hran v rovinném grafu. Důležité poznámky: stupně stěn a princip sudosti pro stěny; maximální možný počet hran v rovinných grafech bez trojúhelníků; a důsledek, že každý rovinný graf obshuje vrchol stupně nejvýše 5. | Téměř vše naleznete v těchto slajdech. |
| Přednáška 12 (plán) | Barevnost grafů--motivace. Obarvení grafu a chromatické číslo, k degenerovaný graf. Tvrzení: odhad chromatcikého čísla pro k-degenerované grafy. Důsledek: věta o šesti barvách. Věta o pěti barvách (s důkazem). Věta o čtyřech barvách (pouze znění). Snadné odhady faktoriálu, kombinačních čísel a zvlášť prostředního kombinačního čísla. | Téměř vše naleznete v těchto a těchto (konec) slajdech. (Pro zkoušku je dostačující se tato témata naučit ze slajdů, což se může hodit zejména u předtermínu.) |