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