Diskrétní matematika (NDMI002), ZS 2016/2017

Na případných konzultacích se můžeme domluvit osobně nebo e-mailem (kyncl zavináč kam.mff.cuni.cz).

Doporučená literatura:

• Jiří Matoušek, Jaroslav Nešetřil; Kapitoly z diskrétní matematiky (kterékoliv vydání). K dispozici v informatickém oddělení knihovny MFF UK.
• Dodatky ke Kapitolám (poslední aktualizace 10. 2. 2017)
• Online sbírka příkladů z diskrétní matematiky

• Ručně psané poznámky doc. Jiřího Fialy. Doc. Fiala upozorňuje, že poznámky mohou obsahovat chyby; nejedná se o oficiální publikaci.
• Videozáznamy přednášek prof. Jaroslava Nešetřila z předmětu NDMA005 Diskrétní matematika, pro studenty matematického programu. Témata i jejich pořadí se mírně liší.
• Pravděpodobnost a matematická statistika - seriál Matematického korespondenčního semináře
• Archiv MKS - obsahuje mimo jiné i spoustu zajímavých příkladů z diskrétní matematiky

Odkazy na cvičení a paralelní přednášky:

Vzor zadání zkoušky

Vybavení ke zkoušce:

• povinné: studentská průkazka nebo jiný doklad totožnosti
• doporučené / povolené: psací potřeby, papíry, občerstvení, znalosti z diskrétní matematiky
• není nutný společenský oděv
• nejsou povolené externí poznámky, knihy, elektronická a komunikační zařízení (kromě ne příliš chytrých hodinek, případně zdravotních pomůcek)

Témata přednášek:

4.10.

• Opakování středoškolských pojmů a značení (číselné obory, operace, funkce, suma, součin, kvantifikátory, logické spojky, množinové operace)
• Důkazy: sporem, indukcí, pomocí nejmenšího protipříkladu
• Kartézský součin, binární relace, reprezentace relací (výčtem, orientovaným grafem, maticí)

11.10.

• Reprezentace relací bipartitním grafem (X vlevo, Y vpravo)
• Vlastnosti relací (reflexivní, symetrická, antisymetrická, tranzitivní), složení relací
  • Úloha: najděte relaci R na {1,2,3,4}, která je symetrická i antisymetrická, a relaci S na {1,2,3,4}, která není symetrická ani antisymetrická.
• Zobrazení a funkce, prosté, na, vzájemně jednoznačné (bijekce)
  • Úloha: dokažte, že funkce na konečné množině je prostá pravě tehdy, když je na. Platí to i pro nekonečnou množinu?
• Složené zobrazení
  • Úloha: jaké zobrazení vznikne složením dvou zobrazení prostých, na, bijekcí, či jejich kombinací?
• Relace ekvivalence, třída ekvivalence, tvrzení o třídách ekvivalence
• Částečné uspořádání, částečně uspořádaná množina, ostré částečné uspořádání, lineární uspořádání, Hasseův diagram
• Nejmenší a minimální prvek; největší je i minimální, ale ne naopak

18.10.

• Je-li a nejmenší prvek, pak je jediný minimální. Dva minimální prvky jsou neporovnatelné.
• Každá konečná částečně uspořádaná množina má aspoň jeden minimální prvek (důkaz indukcí).
• Každé konečné částečné uspořádání lze rozšířit na lineární uspořádání.
• Řetězec, antiřetězec, omega(P), alfa(P), množina minimálních prvků tvorí antiřetězec
• Věta o dlouhém a širokém
• Erdősovo–Szekeresovo lemma o monotónní podposloupnosti

1.11.

• Kombinatorické počítání: počet zobrazení z [n] do [m], počet podmnožin n-prvkové množiny, počet prostých zobrazení z [n] do [m], počet permutací na [n]
  • Úloha: každá n-prvková množina má 2^{n-1} podmnožin sudé velikosti
• Různé reprezentace permutací (slovem, orientovaným grafem, cyklickým zápisem, permutační maticí), značení S_n pro množinu všech permutací na [n]
• Binomický koeficient (kombinační číslo) n nad k
• Počet k-prvkových podmnožin n-prvkové množiny
• Základní vlastnosti kombinačních čísel (důkazy na cvičení), Pascalův trojúhelník
• Binomická věta
• Multinomická věta (jen znění), multinomický koeficient
• Princip inkluze a exkluze
• Problém šatnářky
• Pevný bod permutace, přeformulování problému šatnářky na počet permutací [n] bez pevného bodu

15.11.

• Řešení problému šatnářky - výpočet funkce š(n)
• Eulerova funkce phi(n)
  • Úloha: Spočítejte phi(n) pomocí principu inkluze a exkluze.
• Základy teorie pravděpodobnosti: konečný pravděpodobnostní prostor (Omega, P), elementární jev, jev, pravděpodobnost jevu, příklady
• K dopočítání: pravděpodobnost, že z 70 lidí má některá dvojice narozeniny ve stejný den
• Podmíněná pravděpodobnost P(A|B), Bayesova věta
• Nezávislé jevy A, B

22.11.

• Je-li P(B)>0, pak jevy A,B jsou nezávislé právě tehdy, když P(A|B) = P(A)
• Příklad nezávislých jevů AxX a XxB
• Nezávislé jevy A_1, A_2, ..., A_n
  • Úloha: najděte jevy A,B,C takové, že každé dva jsou nezávislé, ale všechny tři nezávislé nejsou.
• Příklad jevů A,B,C takových, že P(A průnik B průnik C)=P(A)*P(B)*P(C), a přitom A,B,C jsou závislé
• Náhodná veličina, střední hodnota náhodné veličiny,
• Výpočet střední hodnoty metodou indikátorů: indikátor jevu, věta o linearitě střední hodnoty a její použití
• Nezávislé náhodné veličiny X,Y

29.11.

• Pro nezávislé náhodné veličiny X,Y je střední hodnota součinu XY rovna součinu středních hodnot X a Y
  • Úloha: na příkladu ukažte, že to neplatí obecně pro závislé náhodné veličiny
• Úvod do teorie grafů: graf, vrcholy, hrany, značení, kreslení grafů
• Bijekce mezi grafy a symetrickými antireflexivními relacemi
• Úplný graf K_n, kružnice C_n, cesta P_n, úplný bipartitní graf K_{m,n}, bipartitní graf
• Izomorfismus grafů, podgraf, indukovaný podgraf
• Doplněk grafu
• Relace "býti izomorfní" je ekvivalence na množině grafů na [n] (důkaz je cvičení)
• Počet všech grafů na [n] a dolní odhad počtu tříd izomorfismu grafů na [n].
  • Úloha: pro nějaké n>=2 najděte graf na [n], jehož třída izomorfismu grafů na [n] má n! prvků.
• Cesta, tah, sled, kružnice a klika v grafu

6.12.

• Souvislý graf, relace "být spojený cestou" je ekvivalence na množině vrcholů grafu, komponenty (souvislosti) grafu
• Vzdálenost d_G(u,v), nejkratší cesta z u do v je indukovaná a nemusí být jediná, vzdálenost d_G je metrika
• Každý souvislý graf G s aspoň jedním vrcholem má vrchol v takový, že G-v je souvislý
• Stupeň vrcholu, izolovaný vrchol, k-regulární graf, skóre grafu
• Princip sudosti, každý graf má sudý počet vrcholů lichého stupně
• Izomorfní grafy mají stejné skóre
  • Úloha: najděte neizomorfní grafy se stejným skóre.
• Eulerovský (uzavřený) tah, eulerovský graf
• Graf je eulerovský právě tehdy, když je souvislý a má všechny stupně sudé

13.12.

• Poznámka o eulerovských orientovaných uzavřených tazích v orientovaných multigrafech, aplikace na existenci cyklické posloupnosti 0 a 1 délky 2^k, kde žádné dvě k-tice po sobě jdoucích číslic nejsou stejné
• Strom, les, list, každý strom s aspoň dvěma vrcholy má aspoň dva listy
• Přilepením nebo utržením listu získáme ze stromu strom
• Ekvivalentní charakterizace stromů

20.12.

• Informace o zkouškách
• Křivka, prostá křivka, oblouk, uzavřená křivka, prostá uzavřená křivka, topologická kružnice
• Jordanova věta o kružnici (bez důkazu)
• Rovinné nakreslení grafu, rovinný graf
• Příklady rovinných grafů
• Každý rovinný graf s n vrcholy má rovinné nakreslení, kde hrany jsou nakreslené jako úsečky, a dokonce vrcholy jsou mřížové body v mřížce 2n x 2n (bez důkazu)
• Stěna rovinného nakreslení (vnitřní a vnější)
• Eulerův vzorec pro souvislé rovinné grafy; úloha: zobecněte pro nesouvislé rovinné grafy

3.1.

• Horní odhad na počet hran rovinného grafu a rovinného grafu bez trojúhelníků
• Každý rovinný graf má vrchol stupně nejvýše 5, každý rovinný graf bez trojúhelníků má vrchol stupně nejvýše 3
• K_5 ani K_{3,3} není rovinný
• Dělení grafu, Kuratowského věta (dokázána pouze implikace "Je-li G je rovinný, pak neobsahuje dělení K_5 ani dělení K_{3,3}")
• Duál rovinného nakreslení
  • Úloha: najděte graf a dvě jeho rovinná nakreslení R_1 a R_2 taková, že duál R_1 není izomorfní duálu R_2
• Kreslení grafů na plochy
• (Dobré) obarvení grafu (k barvami), barevnost grafu

10.1.

• Klikovost a nezávislost grafu, odhady na barevnost
• Věta o 4 barvách (bez důkazu)
• Každý rovinný graf má barevnost nejvýše 6
• Každý rovinný graf má barevnost nejvýše 5
• Graf je bipartitní právě tehdy, když neobsahuje lichou kružnici (důkaz prohledáváním do šířky).