Diskrétní matematika DMI002 (ZS 2011/12)

přednášející O. Pangrác

Přednáška se koná ve čtvrtek od 12:20 v posluchárně S5. Druhé paralelce přednáší P. Kolman.

Konzultační hodiny: po předchozí emailové dohodě.

Doporučená literatura: J. Matoušek a J. Nešetřil: Kapitoly z Diskrétní matematiky, Karolinum 2000 (dotisk 2002, 2007 a 2009, předchozí vydání MatfyzPress 1996). Na přednášce budou probrány partie vybrané z první poloviny knihy. Ve starším vydání knihy je několik chyb, pozor na ně.

Pro úvod do matematické pravděpodobnosti se připravuje studijní text, který bohužel není momentálně dostupný. O vhodné literatuře budu informovat v průběhu přednášky.

Cvičení a zápočty: Informace o zápočtech se dozvíte od svého cvičícího. Pokud se chcete potrénovat v řešení úloh (nejen z DM), můžete se podívat na webovou sbírku úloh.

Kombinované studium: Pro samostané studium je dobré průběžně sledovat (na této stránce) odpřednesenou látku a příslušné části studovat dle literatury. Nicméně doporučuji se alespoň jednou přijít na přednášku podívat, ať vidíte, jak to vypadá a jakým způsobem se přednáší. Zkoušet se totiž bude podobně, jenom s tím rozdílem, že mluvit budete vy... Pro získání zápočtu si můžete vybrat ze dvou možností. Můžete spolu s interními studenty navštěvovat některé cvičení (třeba by stačilo i s frekvencí jednou za dva týdny). V tom případě se domluvte přímo s cvičícím, nejprve zda je možné jeho cvičení navštěvovat (kapacitní důvody apod.) a pak také na podmínkách udělení zápočtu. Druhou možností je samostatná práce doma. V tom případě je třeba vyřešit následující příklady. Ty jsou rozděleny do tří tematických celků (kombinatorika, pravděpodobnost, grafy), z každé části obsahující 5 úloh je nutné správně vyřešit alespoň 3. Řešení zasílejte emailem, preferuji formát PDF. Pro lepší přehlednost v dokumentu uveďte své jmého a taktéž zadání řešených úloh.

Zkoušky: termíny a přihlašování pomocí studiního informačního systému.

Stručný obsah přednášky (průběžně aktualizován):

• 6.10. Úvod. Množiny a relace, vlastnosti relací.
• 13.10. Ekvivalence a rozkladové třídy. Částečné uspořádání, lineární usp., Hasseho diagramy a příklady. Booleovské uspoř. a vnoření, šířka a délka, věta o dlouhém a širokém.
• 20.10. Funkce (prostá, na, bijekce) a jejich počty. Počty podmnožin (všech, podle mohutnosti), kombinační čísla a jejich základní vlastnosti. Binomická věta.
• 24.10. Binomická a multinomická věta. Dirichletův princip a princip inkluze a exkluze (pro 2 a 3 množiny), aplikace. Erdos-Szekeresovo lemma o monotoních podposloupnostech.
• 27.10. Pravděpodobnost: diskrétní pstní prostor a klasický konečný pstní prostor. Podmíněná pravděpodobnost a nezávislé jevy.
• 3.11. Náhodné veličiny, střední hodnota a její linearita, rozptyl. Markovova a Čebyševova nerovnost. Základní pravděpodobnostní rozdělení (rovnoměrné, binomické, Poissonovo).
• 10.11. Pravděpodobnostní rozdělení (Pascalovo, geometrické a hypergeometrické). Několik aplikací pravděpodonosti.
• 24.11. Grafy: definice a reprezentace grafů, homomorfismus. Základní příklady (prázdný, úplný, cesta, kružnice, bipartitní grafy). Souvislost grafů a vzdálenost v grafech, okolí a stupeň vrcholu. Princip sudosti.
• 8.12. Základní grafové operace (přidání a odebrání hrany a vrcholu, dělení a kontrakce hrany). Stromy a kostry. Cesta, tah a sled a jejich vztah.
• 15.12. Eulerovské grafy (bez orientovaných). Skore grafu a věta o skore. Barevnost grafů a vztah k dalším grafovým parametrům (klikovost, nezávislost).
• 22.12. Barvení d-degenerovaných grafů. Rovinné grafy (základní pojmy), stěny rov. nakreslení, Eulerův vzorec, věta o max. počtu hran rovinného grafu. Kuratowskeho věta (bez důkazu obrácené implikace).
• 5.1. Barevnost rovinných grafů (dva důkazy existence 5-obarvení). Platonská tělesa.
• 12.1. Barevnost grafů bez trojúhelníků, maximální počet hran grafů bez trojúhelníků. Orientované grafy - slabá a silná souvislost, analogie Eulerovy věty a její aplikace.