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

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>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