Cvičení z Diskrétní matematiky.

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

Co se dělalo na cvičení:

  • 1.hodina: cvičí D. Knop: základní příklady na indukci.
  • 2.hodina: Zavedení pojmu grafu a stupně, Důkaz pomocí nejmenšího protipříkladu (princip sudosti), Vyjádření přirozených čísel a uspořádáné dvojice, pomocí pojmu množina a prázdná 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, symetrických, antisymetrických) Zachování reflexivity pokud R a S reflexivní → (RUS;RnS;R-S;R"xor"S)? Příklady relací které (ne)jsou Sym a (ne)jsou Asym zároveň ), Důkaz sporem, Rozdíl mezi důkazem pro všechna a protipříkladem.
  • 3. hodina: Testík, Možná by se vám mohl hodit text o relacích od Pavla Klavíka, příklady na relace, definování funkce, příklady na určování funkcí a jejich vlastností (prostá, ná) a jejich zachovávání při skládání, definování pojmů ekvivalence a třídy ekvivalence a příklady na jejich určování, částečně uspořádaná množina, 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í.
  • 4. hodina: Č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říklady (izomorfismus konečných lin. uspořádání, těsnost E-S důsledku, \((Y,S)\) je čum a \(f:X\rightarrow Y\) funkce, definujme \( (X,R)\) tak \(xRy \Leftrightarrow (f(x)Sf(y)\wedge f(x)\neq f(y)) \vee x=y\), je potom \((X,R)\) také čum?, je lineární pokud je lineární \((Y,S)\)? 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)).
  • 5. hodina: úkol 3/1 - správné nakreslení Hasseho diagramů + složitější příklady na suprema, infima; Kombinatorické počítání: Alternatvní zdůvodnění řešení výběru s opakováním kde nezáleží na pořadí, příklady (Vodníci a čarodejnice v řadě, žádní dva vodníci nesmí stát vedle sebe; počítání permutací s právě dvěma cykly (zamyslete se, nemusí se rozlišovat sudé a liché případy), vlastnosti pascalova trojúhelníku), princip inkluze a exkluze (ukázán příklad: [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])
  • 6. hodina: Testík 3, 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!
  • Státní svátek
  • 7. hodina: Testík 4, Vysvětlení příkladu z úkolu: (hledání neizomorfních čum na množině N), pokračování v pravděpodobnosti (Ekvivalentí definice pstního prostoru (z přednášky a cvičení), 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, 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).
  • 8. hodina(M.Böhm): Testík 5, teorie grafů -- příklady viz. PDF.
  • 9. hodina(M.Böhm): teorie grafů -- příklady viz. PDF.
  • 10. 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ě. 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.
  • 11. hodina
  • Testík 6, Opakování některých příkladů z písemky a úkolů (odtrhávání vrcholů tak aby graf zůstal souvislý, neskóre, rozdávání karet, charakterizace bipartitních grafů), Věta o eulerovském tahu pro orientované grafy +DK, 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 (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).

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 23:59 dne 15/10/2014
  • 2.úkol odevzdávejte do 17:20 dne 20/10/2014
  • 3.úkol odevzdávejte do 17:20 dne 27/10/2014
  • 4.úkol odevzdávejte do 17:20 dne 3/11/2014
  • 5.úkol odevzdávejte do 17:20 dne 10/11/2014
  • 6.úkol odevzdávejte do 17:20 dne 1/12/2014
  • 7.úkol odevzdávejte do 17:20 dne 8/12/2014
  • 8.úkol odevzdávejte do 17:20 dne 15/12/2014
  • 9.úkol odevzdávejte do 17:20 dne 5/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í