Cvičení z Diskrétní matematiky.

Zde budou informace pro studenty Diskrétní matematiky (2013/2014), páteční cvičení od 9:00 k přednáškám O. Pangráce.

Co se dělalo na cvičení:

  • 1. hodina: 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 (Potenční množina, celé časti, fibonacciho čísla), Jednodušší příklady na indukci (dokazování vzorečků, grafické příklady, slovní úložky), logické úložky.
  • 2. hodina: Zopakování pojmu relace a souvisejících pojmů. Jak si relaci představit (Graf, Matice). Skládání relací a pár slov o funkcích. Příklady( (f(n)=2n;g(n)=h. celá část(n/2); fog;gof; jsou prosté/ná?); f(g(x)) prostá X→X musí být prostá f či g?; počty relací (všech, reflexivních, symetrických, antisymetrických); Zachování reflexivity pokud R a S reflexivní → (RUS;RnS;R-S;RoS;R¨¹)? ) Zavedení pojmu ekvivalence, Příklad( Rozhodněte zda jde o ekvivalence a určete jejich třídy: a[N; xRy ↔ p|(x-y) p€N p≥2] b[Z-{0}; xRy↔ x|y & y|x ] c[N; xRy↔ \E z€N z|y & z|x] d[jako [c] z≥2] )
  • 3. hodina: Pro zajímavost Bellovo číslo , Zopakování ČUM, lineární uspořádání, zavedení pojmů (izomorfismus, supremum, infimum), příklady (vlastnosti relace dělitelnosti {suprema, infima největší nejmenší prvek, hasseho diagram, atd.},supremum prázdní množiny, lineární uspořádání na konečné množině je jedno až na izomorfismus) Zopakování věty o dlouhém a širokém, Erddös-Szekeres lemma [kapitoly 2.4.6] + DK.
  • 4. hodina: Rozdíl mezi "důkazem" pro všechna a existuje "protipříklad", Úvod do kombinatorického počítání příklady (#fcí, # fcí prostých, # podmnožin, # sudých/lichých podmnožin, #permutací. # k-prvkových podmnožin, odvození součtových vzorců na komb. čísla), zopakování vztahů komb. čísel: {součet sousedních,(n-k)-prvkové}), Pascalův trojúhelník, multinomický koeficient (i kombinatorická interpretace -- příklad mississippi), multinomická věta bez DK. Příklady ( k prvků vybíráme z n bez/s opakováním (ne)záleží na pořadí; 8 čarodejnic, 6 vodníků ti nesmí stát vedle sebe, #pořadí; Pravděpodobnost že z n lidí májí alespoň 2 narozeniny ve stejný den ), permutace (vizualizace, skládání, cykly), příklady ( #permutací s !1 cyklem, úprava sumy s kombinačním číslem ).
  • 5. hodina: Propagace textíku o relacích (je užitečný třeba na písemku či zkoušku), Pár slov o úkolech (řešení úlohy 2 z úkolu 3), Dirichletův princip a jak nemusí fungovat v nekonečné verzi + příklady (Pro všechna n existuje r≠s tž n|3^r-3^s) a podobné, Inkluze a Exkluze + příklady ( kolik zbude prvků z množiny {1..n} po vyškrtání násobků čísel 2,3,5,7; kolika způsoby mohu zpermutovat množinu {A..P} t že tam nebude po vyškrtání některých písmen žádné ze slov PONK,COP,DOBA; #fce ná a jejich vztah k # ekvivalencí s právě k třídami viz. Stirlingova čísla druhého druhu ) Problém šatnářky + příklady (# permutací s právě k pevnými body, vzorečky).
  • 6. hodina: Časté problémy v domácích úkolech (př 4.4, 4.5, 4.6, 4.7), Zopakování axiomatiky psti, podmíněné psti, nezávislých jevů, Bayesovy věty a věty o úplné pravděpodobnosti. Naznačení problémů s nekonečnými pstními prostory. Příklady na Bayese a úplnou pst, Bertrandův paradox a příbuzné.
  • 7. hodina: Proběhla pravděpodobnost s Martinem Kouteckým.
  • 8. hodina: písemka 1
  • 9. hodina: Upřesnění důkazu skládíní inverzí tranzitivní relací (nemusí vs. existuje příklad) být tranzitivní, Z úkolů (Ekvivalence větčinou vyžaduju důkaz pro obě implikace. Pokud mám dokázat platnost tvrzení pro 6 něčeho, neznemená to, že pokud existuje něco co toho má 9, tak je to protipříklad (viz. úkol 7.2)), Připomenutí základních pojmů z grafů ( Orientovaný graf, Důležité grafy {cesta, strom, bipartitní graf, klika/úplný graf, prázný graf}, Reprezentace {nakreslení, matice sousednosti, matice incidence}, Operace na grafu{kontrakce, podrozdělení, atd.}, Jak chápat formální zápis, Izomorfismus {příklad: je to ekvivalence}, (Indukovaný) podgraf, Souvislost, komponenta souvislosti {příklad algortimus na její nalezení}, Vzádlenost {příklad, že je to metrika}, Stupeň, Skóre, Princip sudosti, Cesta/Sled/Tah ), Příklady( Min/max #hran v G s c komponentami souvislosti, G je nesouvislý jaký má doplňek )
  • 10. hodina: Věta o skóre grafu i s Důkazem. Indukce na obecných grafech a její problémy vs. indukce na stromech a užitečnost věty o konstrukci stromů přidáváním listů. k-tá mocnina matice sousednosti je počet sledů délky k. Zopakování pojmů týkající se kreslení grafů z přednášky{ Nakreslení (rovinné),stěna, Eulerova věta, maximální #hran (bez trojúhelníku), Kuratowského věta, }, Zmínil jsem také {kreslení pomocí úseček, existenci polynomiáního algoritmu na kreslení rov. grafů}, Cvičení{ Souvislé neizomorfní grafy na co nejméně vrcholech, tak aby měli stejné skóre. Euler pro nesouvislé, těsnost odhadů(co je to triangulace, chyby v indukci na triangulaci), nakreslení K_6 na Torus (způsob jak to kreslit přehledně), Nakreslení na sféru či do 3D, pro jak velké n(umíme =7) najdu doplněk G roviného tak aby byl také rovinný, podrozdělení zachovává rovinnost }, zapomněl jsme vám říci, abyste vyzkoušeli planarity.net.
  • 11. hodina: Požární plašení, Podrobné řešení příkladu z DU {9/4 a, b, c, e, (f naznačení jak to mohlo jít rozebrat-charakterizaci neumím)}, Prázdný graf vs. Graf bez jediného vrcholu, Resty z minule {maximum bez trojúhelníku se nabývá, Doplněk rovinného grafu na 11 vrcholech nemůže být rovinný, dvacetistěn je rovinný graf, Petersen není rovinný (zmíněna charakterizace rovinných grafů za pomoci minorů) }, Duální graf (definice se smyčkami a násobnými hranami), cvičení na duální grafy (G* bez smyček), Anketa :).
  • 12. hodina: Typické chyby v DU série 10 (obvzláště záludnosti indukce a nespecifikovanosti zadání), Dokončení příkladů na duál grafu (G* bez násobností,G1 izoG2 ale G1* není izo G2*, G* izo G***), barevnost (zopakování pojmů a úložky (odhady pomocí klikovosti, max nezávislé množiny atd.), připomenutí některých vět (věty o pěti barvách a nastínění jejich algoritmické složitosti), eulerovské grafy, rozklad na cykly, hamiltonovská kružnice, cvičení {např: charakterizace eulerovského neuzavřeného tahu; Grafy se stejným skóre, ale jeden hamiltonovský a druhý ne}, přání hezkých Vánoc.
  • 13. hodina: písemka 2
  • 14. hodina: Zopakování problematických bodů písemky { př 3,4 čt i pá verze } připomenutí Spernerova lematu pro trojúhelníky a jeho použití na důkaz neremízovosti hry HEX (viz. kapitoly) , dávání zápočtů :)

Domácí úkoly:

  • 1.úkol odevzdávejte do 9:00 dne 11/10/2013
  • 2.úkol odevzdávejte do 9:00 dne 18/10/2013
  • 3.úkol odevzdávejte do 9:00 dne 25/10/2013
  • 4.úkol odevzdávejte do 9:00 dne 1/11/2013
  • 5.úkol odevzdávejte do 9:00 dne 8/11/2013
  • 6.úkol odevzdávejte do 9:00 dne 15/11/2013
  • 7.úkol odevzdávejte do 9:00 dne 22/11/2013
  • 8.úkol odevzdávejte do 9:00 dne 29/11/2013
  • 9.úkol odevzdávejte do 9:00 dne 6/12/2013
  • 10.úkol odevzdávejte do 9:00 dne 13/12/2013
  • 11.úkol odevzdávejte do 9:00 dne 20/12/2013
  • 12.úkol odevzdávejte do 9:00 dne 3/1/2014
  • 13.úkol odevzdávejte do 9:00 dne 10/1/2014

Požadavky na zápočet:

V průběhu semestru budou 2 písemky, každá po 50 bodech. Po každém cvičení (kromě posledního) budou domácí úkoly za 8 bodů, které bude 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ň 100 bodů celkem.
  • Alespoň 50/100 bodů z písemek.
  • Alespoň 35/104 bodů z úkolů.

Pokud někdo o trochu nesplní požadavky, tak přesto může dostat u mě zápočet za vyřešení většího množství obtížných příkladů a/nebo napsáním těžké písemky.

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í