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>mimuw.edu.pl



CENT building room 03.111, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
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