Diskrétní matematika (NDMI002), ZS 2017/2018
Přednáška se koná ve čtvrtek v 9: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í Martina Mareše, Po 10:40
cvičení Petera Korcsoka, Po 14:00
cvičení Radka Huška, Po 15:40
cvičení Jany Syrovátkové, Út 12:20
přednáška Martina Tancera
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:
5.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
12.10.
- Kartézský součin, binární relace, reprezentace relací na množině X (výčtem, orientovaným grafem, maticí)
- Reprezentace relací mezi X a Y 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é vlastnosti má zobrazení vzniklé složením dvou zobrazení prostých, na, bijekcí, či jejich kombinací?
- Relace kvivalence, 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í
- Úloha: existuje nějaké lineární uspořádání na množině komplexních čísel?
19.10.
- Hasseův diagram
- Nejmenší a minimální prvek; nejmenší je i minimální, ale ne naopak; podobně největší a maximální
- Je-li a nejmenší prvek, pak je jediný minimální (obrácená implikace neplatí pro nekonečné množiny). 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, průnik řetězce a antiřetězce má nejvýše jeden prvek
- Věta o dlouhém a širokém, rozklad na omega(P) antiřetězců
26.10.
- Erdősovo–Szekeresovo lemma o monotónní podposloupnosti
- 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: kolik má n-prvková množina podmnožin sudé velikosti?
- Různé reprezentace permutací (slovem, orientovaným grafem, cyklickým zápisem, permutační maticí)
- 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
2.11.
- Binomická věta (s jednou nebo dvěma proměnnými)
- Multinomická věta (jen znění), multinomický koeficient
- Princip inkluze a exkluze
- Problém šatnářky
- Pevný bod permutace, značení S_n pro množinu všech permutací na [n], přeformulování problému šatnářky na počet permutací [n] bez pevného bodu
- Ř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.
9.11.
- 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 ze 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
- 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
16.11.
- 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, značení [X=a], P[X=a], 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
- Úloha: Ukažte, že jsou-li jevy A a B nezávislé, pak A a doplněk B jsou nezávislé (doplněk B je jev Omega \ B).
- Úloha: Ukažte, že jevy A a B jsou nezávislé právě tehdy, když jejich indikátory I_A, I_B jsou nezávislé.
- 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 náhodné veličiny, které nejsou nezávislé.
30.11.
- Ú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, nezávislá množina v grafu
7.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 (a ze souvislého grafu souvislý graf)
- 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ší)
- Eulerova formule pro souvislé rovinné grafy
- Úloha: zobecněte pro nesouvislé rovinné grafy
4.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
11.1.
- Liché kružnice mají barevnost 3
- 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).
- Úloha: má-li graf lichou kružnici jako podgraf, pak má i indukovanou lichou kružnici.