Cvičení z Diskrétní matematiky.

Zde budou informace pro studenty Diskrétní matematiky (2014/2015), páteční cvičení od 12:20 k přednáškám M.Tancera.

Co se dělalo na cvičení:

  • 1. hodina: podmínky na zápočet, Prázdná množina a zavedení přirozených čísel, Co je to důkaz, jak chápat důkaz a jeho typy, důkaz indukcí, Značení a jednoduché příklady (Suma, produkt, kombinační čísla, fibonacciho čísla), Jednodušší příklady na indukci (dokazování vzorečků, grafické příklady, slovní úložky), Jak indukci nepoužívat viz. příklad: Circle Division by Chords
  • 2. hodina: Příklad rovnice která neplatí pro žádné \(n\), ale indukční krok splňuje, Důkaz pomocí nejmenšího protipříkladu (\(\sum_1^n F_i^2=F_nF_{n+1}\)), Vyjádření uspořádáné dvojice, pomocí pojmu množina, Definice relace, symetrie, transitivity, reflexivity, Jak reprezentovat relace (výčet, matice, orientovaný graf), příklady (která relace je funkcí?, počty relací (všech, reflexivních) ).
  • 3. hodina: Testík, propagace textu o relacích od Pavla Klavíka, Zavedení pojmu grafu a stupně, DK principu sudosti pomocí nejmenšího protipříkladu, předvedení Dú2/2 (vyjádření \(n\) pomocí součtu různých Fibonacciho čísel), Příklady (Zachování reflexivity pokud R a S reflexivní → (RUS;RnS;R-S;RoS;R¨¹)?, Platí relace je Sl. antisymetrická → každá její podrelace je také Sl. antisymetrická, \(R\subseteq X^2\) je transitivní \(\Leftrightarrow R\circ R\subseteq R\)), Důkaz Sporem, rozdíl mezi důkazem pro všechna a protipříkladem.
  • 4. hodina: Testík 2, Rozebraný DK: Relace R je transitivní právě tehdy když \(R^2 \subseteq R\), definování funkce, příklady na určování funkcí a jejich vlastností (prostá, ná), jejich zachovávání při skládání, částečně uspořádaná množina, hasseho diagram, definování největšího/nejmenšího/maximálního/minimálního prvku, dále suprema a infima na množině včetně prázdné množiny, Příklad na jejich určování.
  • 5. hodina: příklad z testíku 2 (složení dvou ekvivalencí nemusí být ekvivalence)+ časté chyby, rozdíl mezi důkazem pro všechna a existuje, ČUM -- pokračování (připomenutí věty o dlouhém a širokém, důsledek Erdös-Szekeres věta o vybrané monotóní podposloupnosti+DK), příklad: (těsnost E-S důsledku). Kombinatorické počítání (bin. koef, pascalův trojúhelník, multinomický koeficient[příklad s MISSISSIPPI], binomická věta) příklady (výběr k prvků z n prvkové množiny s/bez opakování (ne)záleží na pořadí --[POZOR na nezáleží na pořadí s opakováním: zkuste si to sami promyslet, popřípadě přečíst tento článek], počítání počtu podmnožin, kombinatorické počítání dvěma způsoby (vybírali jsme předsedu a jeho tým); vodníci a čarodejnice v řadě, tak že žádní dva vodníci nestojí vedle sebe.).
  • 6. hodina: (J. Musílek): Zopakování pojmů z částečného uspořádání, Hasseho diagramy, chyby v úkolech, složitější příklady na suprema a infima. Princip inkluze a exkluze (Zopakování + příklady [Počet skoroprvočísel (tedy neprvočísel nedělitelných 2,3,5), kolika způsoby mohu zpermutovat množinu {A..P} tak, že tam nebude po vyškrtání některých písmen žádné ze slov PONK, COP, DOBA jako vybrané podslovo]).
  • 7. hodina: Poučení z Dú: (ne vždy je indukce nejsnažší možnost, Vodníci a čarodejnice v kruhu: proč musím počítat až na otočení kruhu.), Pravděpodobnostní počítání: zopakování pojmů z hodiny (Pravděpodobnostní prostor, def nezávislé jevy, podmíněná pst, bayssova věta, věta o úplné psti) Příklady (viz. PDF,Pst že 2 lidi mají narozeniny ve stejný den, [P(A|B),P(B|A),P(A^_|B),P(A|B^_],P(A^_|B^_)). Není úkol!
  • 8. hodina: Testík 3, příklad s vodníky a čarodejnicemi potřetí, Pokračování pravděpodobnosti: příklady (P(2 lidi z n mají narozeni ve stejný den), nezáskok př. 4, \(P(A\cap B), P(A\cup B), P(B\cup \bar A), P(B|A)\) pokud známe \(P(A),P(B), P(A|B)\).) Definice náhodná veličina, střední hodnota, rozptyl, věta o linearitě střední hodnoty. Ukázán příklad s n střelci, kteří si náhodně vyberou n zajíců, kde nás zajímá stř hodnota # přeživších zajíců (řešeno pomocí indikátorové metody), Markovova nerovnost (DK pomocí indikátorové metody).
  • 9. hodina Ekvivalentní definice pravděpodobnostního prostoru, PIE z axiomů pstního prostoru, nezávislé jevy náhled na definici, rozptyl a grafický význam čebyševovy nerovnosti. Úvod do teorie grafů: (Definice, reprezentace, některé významné grafy (klika, cesta, nezávislá množina, cyklus), souvislost, komponenty souvislosti), příklad: algoritmus na rozpoznání komponent souvislosti.
  • 10. hodina: (J.Musílek):Testík 4, Teorie grafů (Izomorfismus grafů,Věta o skóre, Stromy, Orientované eulerovské podgrafy+DK). Úkol není!
  • 11. hodina: Velká písemka! --pokud nebudete moci přijít napište předem a včas email a domluvíme se na případné náhradě. Úkol není!
  • 12. hodina: Rovinné nakreslení, indukce na grafech (varovný příklad: Každá rovinná triangulace obsahuje vrchol stupně ≤3. Protipříklad dvanáctistěn), Eulerův vzorec, Kuratowského věta i varianty s kontrakcí, Příklady (Eulerův vzorec pro nesouvislé grafy, nakreslení K_6 na torus, Zjišťování zdali jsou Petersen a další rovinnými grafy, Kreslení grafů na sféru a do 3D, pouze pomocí úseček). Dále můžete vyzkoušet planarity.net, kde si můžete kreslit grafy rovinně, popřípadě se podívat na youtube na "alternativní" důkaz věty o pěti barvách.
  • 13. (poslední) hodina:

Domácí úkoly:

Při vymýšlení úkolů můžete spolupracovat, chtěl bych ale abyste řešení sepsali každý sám. Všechny kroky se snažte pečlivě zdůvodnit, je to důležitější než mít správný výsledek. Naopak můžete používat cokoli z přednášek či cvičení bez důkazu, jen vždy uveďte, co právě používáte. Pokud nechcete mít zveřejněno jméno na webu použijte k podpisu úkolu navíc přezdívku. Ještě bych rád upozornil, že bodové hodnocení jednotlivých příkladů nemusí vždy odpovídat jejich obtížnosti.

  • 1.úkol odevzdávejte do 12:20 dne 10/10/2014
  • 2.úkol odevzdávejte do 12:20 dne 17/10/2014
  • 3.úkol odevzdávejte do 12:20 dne 24/10/2014
  • 4.úkol odevzdávejte do 12:20 dne 31/10/2014
  • 5.úkol odevzdávejte do 12:20 dne 7/11/2014
  • 6.úkol odevzdávejte do 12:20 dne 14/11/2014
  • 7.úkol odevzdávejte do 12:20 dne 28/11/2014
  • 8.úkol odevzdávejte do 12:20 dne 5/12/2014
  • 9.úkol odevzdávejte do 12:20 dne 9/1/2015
  • 10.úkol odevzdávejte do 23:59 dne 28/2/2015

Požadavky na zápočet:

V průběhu semestru bude 1 velká písemka za 50 bodů. Po skoro každém cvičení budou domácí úkoly za 5 bodů každá série, které bude vždy potřeba odevzdat do dalšího cvičení!

Zápočet lze získat za splnění všech následujících podmínek:

  • Alespoň 25/50 bodů z písemek.
  • Alespoň 25/50 bodů z úkolů.

Kromě toho bude asi 5 krát v semestru 10-15min testík za cca 2 body každý z něhož body mohou být započítány, stejně jako body z aktivity, do libovolné části.

Pokud někdo o trochu (alespoň 25b celkem) nesplní požadavky, tak přesto může dostat zápočet při ústním dozkoušení, které bývá zpravidla poslední týden semestru či až v průběhu zkouškového.

Výsledky a nárok na zápočet:

Dosavadní výsledky v google dokumentu.


masarik<a>kam.mff.cuni.cz


Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
tel +420 22191 4294

Profile for TarkenCZE-Maso sDýní