Diskrétní matematika - přednáška ZS 2020/2021

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. (Nicméně nějaké drobné odchylky nejspíš nastanou.)

Informace ke zkouškám

• Už proběhly všechny termíny plánované na zkouškové období. Pokud se stále potřebujete nechat vyzkoušet, kontaktujte mne emailem, a snad se nějak domluvíme.
• Níže najdete informace ohladně organizace zkoušek a potřebných znalostí. Pokud tyto informace na cokoliv neodpovídají, tak se mi ozvěte, a budu se snažit odpovědět, popř. tyto informace doplnit.
• Informace uvedené níže počítají s prezenční formou zkoušky. Pokud potřebujete distanční formu zkoušky, tak se mi ozvěte emailem. Budeme se domlouvat individuálně.

Průběh a organizace zkoušek

• Zkouška bude začínat písemkou z příkladů na 60 minut. Po této písemce bude obvykle následovat hned ústní zkoušení (ale mohou nastat výjimky).
• V SISu najdete vypsané termíny. Očekávám, že to není finální výčet možností, ale další termíny dodám až časem podle toho, jak se budou zaplňovat ty vypsané v SISu. (Zatím jsou termíny vypsané do 5. 2. Určitě očekávám, že ještě vypíšu nějaký termín nebo termíny po 5.2. Pokud se nějaký týden vyčerpá kapacita termínů, budu se snažit vypsat další termín někdy blízko, ale neslibuju.)
• Typicky u jednoho dne najdete více možných časů. Ranní termín je vždy otevřený a pozdější časy se otevírají, pokud dojde kapacita časů dřívějších. Je možné, že si nevšimnu okamžitě, že došla kapacita, ale můžete počítat s tím, že to budu čas od času kontrolovat. Kdyžtak se zařaďte do fronty, a já Vás na termín rovnou nahlásím, až ho otevřu. (Případně mne můžete i upozornit emailem, pokud se Vám zdá, že některý termín není otevřený příliš dlouho, a už by otevřený být měl. Ale speciálně v období 28. 12. - 3. 1. nebudu reagovat moc.)
• V tento moment se zdá, že bude možné prezenční zkoušení do 10 osob. Počítejte tedy s touto variantou. Pokud se v budoucnu navýší počet možných osob v místnosti při zkoušení, tak je možné, že termíny nějak přeuspořádám. Pokud se tedy nahlásíte na pozdější termín, tak počítejte s variantou, že po Vás můžu chtít, abyste dorazili už dříve. Speciálně se vždy přednostně hlašte na co nejdřívější termín.
• Zkoušky se vesměs budou konat v budově na Malé Straně (Malostranské náměstí 25). U vstupu do budovy jsou dveře na čip. Já doufám, že máte možnost alespoň dostat studentskou kartičku, která by tyto dveře měla otevřít. Pokud ne, tak se nahlašte na vrátnici, že jdete na zkoušku. Potom podle ukazatelů najděte vhodnou učebnu.
• Pokud budete mít příznaky respiračního onemocnění, pak byste do budovy univerzity vůbec neměli vstupovat. Pokud se předtím nestihnete odhlásit včas ze zkoušky, tak mi napište email dříve než se bude zkouška konat. V takovém případě bude neúčast na zkoušce považovaná samozřejmě za omluvenou.

Potřebné znalosti ke zkoušce

• Zkoušeni můžete být ze všech témat, která jsme probírali (s výjimkou těch, kde jsem výslovně uvedl, že se nezkouší). Zkouší se definice, znění tvrzení/vět i důkazy. Neovládat definice a tvrzení/věty je problém. U důkazů jde hlavně o to, o jakou známku budete bojovat. Nicméně nějaký jednodušší důkaz něčeho, co plyne hned z definic by měl zvládat každý. (Speciálně je velmi žádoucí mít jasno v tom, v jakém směru vede implikace, a také v důkazu matematickou indukcí.)
• Při učení se Vám mohou být nápomocné slajdy (i kvůli tomu jsem je vyráběl). Nicméně pozor, na slajdech nemůže být vše. Velmi důležité je i to, co jsem k slajdům navíc říkal na přednášce jako vysvětlení. Když si nebudete v některých bodech jistí, můžete si například stále napsat o záznamy přednašek (s dostatečným předstihem).
• Příklady v písemce by měly být ze stejných témat, jako se brala na cvičeních. Celkově je ale potřeba počítat s tím, že k vyřešení nějakého příkladu může být potřebné aktivně ovládat nějakou znalost z přednášky.
• V písemce budou dva příklady na 15 bodů. Zisk 4 bodů nebo méně nebude stačit k získání zkoušky ani při skvělém výkonu na ústní části. Zisk 5-7 bodů bude vyžadovat skvělý výkon u ústní části. Dále bude u ústní části samozřejmě přihlíženo k bodům získaným z písemky. Můžete se podívat na vzorovou písemku.

Důležité informace k online výuce

• Zde jsou údaje pro přihlašení se na přednášku přes Zoom: "Meeting id" je 995 5081 2938, pro účast na přednášce je potřeba se registrovat přes tento odkaz, stačí jednou za semestr. Zároveň by přihlášeným účastníkům mělo dorazit heslo. Pokud Vám heslo nedorazilo do středy 30. září 16:00, napište mi email. Také se přednášky může zúčastnit i někdo, kdo ji nemá zapsanou v SISu. Opět mi napište email a heslo Vám pošlu, jen chci mít přehled. Můj email nalzenete na mé domovské stránce.
• Přednáška je rozdělena na dvě paralelky. Paralelku X učí Martin Mareš, tady je odkaz na jeho stránky k přednášce. Já učím paralelku Y. Obě přednášky jsou v pondělí od 9:00. Domluvili jsme se, že je smysluplné mít obě přednášky, byť jsou zároveň. Planujeme se snažit synchronizovat témata, ale každý chceme přednášku pojmout online přednášku mírně jinak. V principu si tedy můžete vybrat jaký styl přednášky Vám více vyhovuje s drobným varováním: Nemůžete očekávat, že úplně všechny detaily řekneme úplně stejně. Proto, až bude zkouškové období, tak si určitě zkontrolujte, co přesně přednášel ten přednášející, který Vás má zkoušet.
• Moje přednáška bude probíhat přes zoom s pomocí slajdů. Slajdy k přednášce budu průběžně zveřejňovat.
• Ptejte se, ptejte se, ptejte se: Při online výuce schází přímá interakce mezi vyučujícím a studenty, a hůře se odhaduje, jak kdo tématu rozumí. O to je důležitější, abyste se během přednášky ptali na cokoliv, co Vám není jasné. (Času na dotazy bude určitě dost!)
• Samozřejmě se také neváhejte na cokoliv zeptat emailem, když se to během přednášky nebude hodit. Email také použijte, pokud si chcete domluvit konzultaci.
• Přednášky mám v plánu nahrávat přes zoom kvůli tomu, že se může stát, že někteří nebudou moci přednášky sledovat v daný čas. Tím budou nahrané i Vaše dotazy. Kdyby to komukoliv vadilo, tak prosím pokládejte dotazy přes chat.

Doporučená literatura

Záznamy přednášek

Průběh přednášek a slajdy

Přednáška 1, 5. 10. (slajdy): 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, 12. 10. (slajdy (po drobných opravách)): Ještě jeden příklad na indukci. Funkce: definice, prostá funkce, funkce na, bijekce, inverzní funkce a skládání funkcí. Inverznní relace a skládání relací. Částečná uspořádání, bezprostřední následník, Hasseův diagram (neformálně), porovnatelné prvky, řetězce, antiřetězce.

Přednáška 3, 19. 10. (slajdy (po drobných opravách)) Maximální, největší, minimální a nejmenší prvek. Věta o dlouhém a širokém. 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. Binomická věta.

Přednáška 4, 26. 10. (slajdy (po drobných opravách)) Princip inkluze a exkluze, motivační příklad, znění a důkaz. Problém šatnářky a počet permutací bez pevného bodu. Snadné odhady faktoriálu a kombinačních čísel a zlepšení (stále snadné) prostřední kombinační číslo.

Přednáška 5, 2. 11. (slajdy) Graf, definice, příklady, kreslení grafů. Důležité grafy: úplný graf, nezávislá množina, kružnice, cesta, úplný bipartitní graf. Bipartitní grafy. 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.

Přednáška 6, 9. 11. (slajdy (po drobné opravě)) Matice sousednosti. Věta o počtu sledů. Grafová metrika. Stupeň vrcholu a skóre grafu. Princip sudosti a počet vrcholů lichého stupně. Věta o skóre. Konkrétní příklady na poznávání skóre grafu.

Přednáška 7, 16. 11. (slajdy) Eulerovské grafy. Charakterizace eulerovských grafů pomocí souvislosti a sudosti stupňů vrcholů. 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.

Přednáška 8, 23. 11. (slajdy (po několika drobných opravách; přidaná definice lesa)) Stromy, definice stromu, listu a lesa. Lemma o existenci listů a tvrzení o trhání listů. Věta o ekvivalentních charakterizacích stromů. Kostra grafu. Graf má kostru, právě když je souvislý.

Přednáška 9, 30. 11. (slajdy (po několika drobných opravách)) Motivace pojmu rovinné grafy. Spojitá funkce z intervalu [0,1] do roviny (nebude se zkoušet přesná definice). Oblouk. Nakreslení grafu, rovinné nakreslení, rovinný graf. Oblouková souvislost a stěna nakreslení. Eulerův vzorec pro rovinné grafy. Tvrzení o maximálním počtu hran rovinného grafu. Důsledek, každý rovinný graf obsahuje vrchol stupně nejvýše 5. Hlavně pro počítání příkladů: stupeň stěny; součet stupňǔ stěn je dvakrát počet hran; duální (multi)graf (pouze obrázkem); souvislý rovinný graf bez trojúhelníků s n vrcholy má nejvýše 2n-4 hran. Grafové operace zachovávjící rovinnost: odebírání vrcholu a hrany, kontrakce a podrozdělení. Něco navíc (nezkouší se): dělení grafu a minor, Kuratowského a Wagnerova věta.

Přednáška 10, 7. 12. (slajdy (po drobných opravách)) Barvení grafu: motivace - barvení map. 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 11, 14. 12. (slajdy (po drobných opravách)) Základy diskrétní pravděpodobnosti: diskrétní pravděpodobnostní prostor, pravděpodobnostní prostor (neúplná definice), elementární jev, jev, příklady pravděpodobnostních prostorů. Podmíněná pravděpodobnost (motivace, příklad s kartami), 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ý graf G(n,p).

Přednáška 12, 21. 12. (slajdy (po drobných opravách)) Náhodná veličina, střední hodnota, druhý způsob, jak ji spočítat. Medián (okrajově). Indikátor jevu. Příklad: střední hodnota počtu 1 v náhodné posloupnosti 0 a 1 délky n, z definice pro n=3 a přes indikátory obecně. Další příklad: střední hodnota počtu pevných bodů v náhodné permutaci. Nezávislé náhodné veličiny. Distribuční funkce, rovnoměrné a binomické rozdělení. Pravděpodobnostní důkaz: existence bipartního podgrafu s alespoň polovinou hran.

Přednáška 13, 4. 1. (slajdy (po drobné úpravě)) Erdős-Szekeresova věta. Platónská tělesa (nezkouší se).