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