Cvičení se koná každý čtvrtek ve 12:20 na Malé Straně v učebně S10 (záznam v SISu), stránky k přednášce najdete zde.
Pokud budete chtít přijít na konzultaci, napište mi e-mail (janvolec-tady_neco_chybi-jikos.cz) a domluvíme se.
Domácí úlohy budou zadávány na témata, která byla probrána na cvičeních. Na jejich vypracování bude zpravidla jeden týden. Řešení se odevzdávají písemně na začátku příslušného cvičení, kde si společně ukážeme jejich řešení. Pokud na cvičení neplánujete přijít, můžete před jeho začátkem zaslat řešení e-mailem.
Různé logické hříčky a příklady, příklad s 6 lidmi, kteří se navzájem nějak znají, asociativnost/komutativnost sjednoceni a pruniku, vzorce pro aritmetickou a geometrickou posloupnost, matematická indukce a příklad s vyžranou políčkovou sítí, 2^222 modulo 10.
Řešení domácích úloh, některé typy relací a jejich různé definice, max. počet částí roviny určený pomocí n přímek.
Řešily se příklady: antireflexivní, tranzitivní relace je silně antisymetrická; počet všech sudých resp. lichých podmnožin n-prvkové množiny; počet všech ekvivalencí na tříprvkové množině; počet všech dvojic množin, které jsou v inkluzi; průnik dvou uspořádaní je uspořádaní, rozdíl nikoli; relace na dvou prvcích, která není tranzitivní.
Počet skoro prostých (sprostých) funkcí, prosté (resp. surjektivní) zobrazení z konečné množiny do sebe sama je bijekce, počet permutací s právě jedním cyklem, počítání nějakých sum, dva kombinatorické důkazy binomické věty, princip inkluze a exkluze a příklad s pohádkovými postavami ve frontě.
Rekurzivní vzorec pro počet ekvivalencí, počet část. uspořádání na 3 prvcích (pomocí Hasseho diagramů), několik triků pro počítání různých sum (ukázáno na některých sumách z domácích úkolů), princip inkluze a exkluze a pokus o obecný vzoreček s náznakem důkazu, pravděpodobnost správnosti náhodného hesla, "narozeninový paradox".
Upozornění: příští týden bude písemka! Domací úlohy s pravděpodobností a se sumou i*2^i, po dvou nezávislé a totálně nezávislé jevy, pokud počet elementárních jevů je prvočíselný, jsou každé dva netriviální jevy závislé, úloha s šíleným cvičícím, příklad jevů, které jsou po dvou nezávislé, ale nejsou totálně nezávislé.
Psala se písemka, poté pár příkladů na linearitu střední hodnoty, střední počet pevných bodů permutace.
Ozvěny z písemky, počet všech relací na [n]×[n], pravděpodobnost, že 1 a 2 jsou ve stejném cyklu náhodné permutace na [n], střední počet přeživších zajíců, počet čísel od 1 do 100, která nejsou dělitelná 2,3 ani 5.
Domací úkol s PPO vs. POO, střední hodnota a rozptyl pro některá náhodná rozdělení, grafy, izomorfismus grafů, počet neizomorfních grafů na 3 vrcholech, každý graf obsahuje 2 vrcholy stejného stupně.
Doplněk nesouvislého grafu je souvislý, G je bipartitní iff G neobsahuje lichou kružnici, doplněk bip. grafu s alespoň 5 vrcholy není bipartitní, max. počet hran grafu na n vrcholech s k komponentami souvislosti, G lze nakreslit k tahy iff G obsahuje nejvýše 2k vrcholů lichého stupně.
Každý srom s vrcholem stupně d obsahuje alespoň d listů, minimální počet hran grafu na n vrcholech s k komponentami, několik ekvivalentních definic stromu, každý sovislý graf obsahuje vrchol, po jehož odebrání zůstane graf stále souvislý (tj. vrchol, který není artikulace).
Upozornění: příští týden bude písemka! Počet koster K_{2,n} a K_4 s bambulí, chybný důkaz 3-degenerovanosti rovinných grafů, příklad 4-regulárního rovinného grafu, příklad dvou nakreslení jednoho rovinného grafu s různými velikostmi stěn, Petersenův graf není rovinný.
Psala se písemka. Rovinný graf izomorfní svému duálu, řešení úkolu s počtem koster úplného grafu bez jedné hrany, alternativní důkaz věty o pěti barvách (pomocí tzv. Kempeho řetězců).
K-regulární bipartitní graf nemá most, graf s minimálním stupněm delta obsahuje cestu délky delta a kružnici délky alespoň delta+1, doplněk rovinného grafu s alespoň 11 vrcholy není rovinný, barevnost Petersenova grafu, d-degenerovaný graf, horní odhad barevnosti pomocí max. stupně resp. degenerovanosti, Eulerova formule pro rovinné grafy bez trojúhelníků a pro rovinné grafy bez trojúhelníků a čtyřcyklů.
| 1. úk. | 2. úk. | 3. úk. | 4. úk. | 5. úk. | 6. úk. | 7. úk. | 8. úk. | 9. úk. | 10. úk. | 11. úk. | 12. úk. | Σ př. | akt. | pí. 1 | pí. 2 | Σ | záp. | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 11 | 12 | 12 | 14 | 10 | 12 | 24 | 15 | 15 | 27 | 21 | 30 | 203 | 0 | 50 | 50 | 303 |
Objevíte-li někde chybu, dejte mi, prosím, vědět.
Stránka vytvořena za pomoci programů vi, bash a perl. Poslední změna: 05.02.2010