Diskrétní matematika (NDMI002), ZS 2016/2017
Přednáška se koná v úterý ve 14:00 v S3 na Malé Straně.
Záznam v SISu, sylabus
Na případných konzultacích se můžeme domluvit osobně nebo e-mailem (kyncl zavináč kam.mff.cuni.cz).
Doporučená literatura:
Další zdroje:
Odkazy na cvičení a paralelní přednášky:
cvičení ST 14:00 S8 a ST 15:40 S7
cvičení Jana Musílka, PO 14:00
cvičení Jana Musílka, CT 14:00
 
přednáška prof. Martina Loebla
a lecture by Hans Raj Tiwary
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).