Cvičení z Diskrétní matematiky.

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

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¨¹)? ) Zopakování pojmu ekvivalence, Tvrzení [kapitoly 1.6.3] + DK.
  • 3. hodina: 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) Úvod do kombinatorického počítání (#fcí, # fcí prostých, # podmnožin, # sudých/lichých podmnožin, #permutací. # k-prvkových podmnožin+ souvislost s komb. číslem, vztahy komb čísel {součet sousedních,(n-k)-prvkové}) vše i s DK, Pascalův trojúhelník, Příklady (odvození součtových vzorců na komb. čísla, kombinatorické počítání).
  • 4. hodina: Rozdíl mezi "důkazem" pro všechna a existuje "protipříklad", Pro zajímavost Bellovo číslo , Binomická věta + DK, 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, Trojúhelníkové číslo a souvislost s Pascalovým Trojúhelníkem ).
  • 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: Byla imatrikulace.
  • 7. hodina: Zopakování axiomatiky psti, podmíněné psti, nezávislých jevů, Bayesovy věty a věty o úplné pravděpodobnosti. Střední hodnota, linearita střední hodnoty, Indikátorová metoda, příklad se zajíci a střelci [kapitoly]. Další příklady na střední hodnotu, Příklad na pst že se narodili dva chlapci | že jeden z nich je chlapec. Monty hall a upozornění na Bertrandův paradox. Rozptyl, co to je rozdělení, Binomické rozdělení, náznak jak to funguje pro nekonečné pstní prostory, příklady. Markovova nerovnost + DK indikátorovou metodou, čebyševova nerovnost bez DK, ale s obrázkem.
  • 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í, Rozbor 4. příkladu z písemky, 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}, 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 ), 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ů, Příklady( Min/max #hran v G s c komponentami souvislosti, G je nesouvislý jaký má doplňek )
  • 10. hodina: 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íněna verze s minory) }, Zmínil jsem také{kreslení pomocí úseček, existenci polynomiáního algoritmu na kreslení rov grafů}, Cvičení{ Euler pro nesouvislé, těsnost odhadů(co je to triangulace, chyby v indukci na triangulaci), nakreslení K_6 na Torus, Nakreslení na sféru či do 3D, Nerovinnost petersenova grafu, Doplněk rovinného grafu na 11 vrcholech nemůže být rovinný, pro jak velké n takový doplněk najdu, podrozdělení zachovává rovinnost }, zapomněl jsme vám říci, abyste vyzkoušeli planarity.net.
  • 11. hodina: Podrobné řešení příkladu z DU {9/4 a,b,c,(e bude znovu příště),(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á, dvacetistěn je rovinný graf}, Duální graf (definice se smyčkami a násobnými hranami), cvičení na duální grafy (G* bez smyček, G* bez násobností,G1 izoG2 ale G1* není izo G2*, Kdy paltí G** izo G) Připomenutí pojmů barevnosti a barvení grafů z hodiny (korektní obarevení, barevnost), cvičení (chi(G)≥V+alfa(G)), Anketa :).
  • 12. hodina: Typické chyby v DU série 10 (obvzláště záludnosti indukce a nespecifikovanosti zadání), Charakterizace pro neobsahování sudé kružnice (DU 9/4e), barevnost (zopakování pojmů a dokončení úloh z minula, 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, věta o skóre, cvičení{např: charakterizace eulerovského neuzavřeného tahu; souvislé neizomorfní grafy se stejným skóre na co nejméně vrcholech; 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ř 5 čt verze} Zavedení pojmu kombinatorické hry. DK 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 23:59 dne 10/10/2013
  • 2.úkol odevzdávejte do 23:59 dne 17/10/2013
  • 3.úkol odevzdávejte do 23:59 dne 24/10/2013
  • 4.úkol odevzdávejte do 23:59 dne 31/10/2013
  • 5.úkol odevzdávejte do 23:59 dne 7/11/2013
  • 6.úkol odevzdávejte do 23:59 dne 14/11/2013
  • 7.úkol odevzdávejte do 23:59 dne 21/11/2013
  • 8.úkol odevzdávejte do 23:59 dne 28/11/2013
  • 9.úkol odevzdávejte do 23:59 dne 5/12/2013
  • 10.úkol odevzdávejte do 23:59 dne 12/12/2013
  • 11.úkol odevzdávejte do 23:59 dne 19/12/2013
  • 12.úkol odevzdávejte do 23:59 dne 2/1/2014
  • 13.úkol odevzdávejte do 23:59 dne 9/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í