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 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.
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í.
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 pdomnož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).
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).
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).
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ě.
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.
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ů.
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.
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.