Diskrétní matematika – cvičení
V ZS 2017/2018 vedu cvičení z Diskrétní matematiky [NDMI002] k přednášce Honzy Kynčla. Cvičení se koná každé pondělí od 10:40 v S7.
Zápočet si lze vysloužit za získání alespoň 128 bodů za domácí úkoly (sepsány níže). Každý domácí úkol lze řešit 14 dní od zadání za plný počet bodů, pak na cvičení povím nápovědu a bude možné získat poloviční počet bodů.
Řešení úkolů můžete odevzdávat buďto na papíře, nebo posílat e-mailem ve formátu PDF na adresu mj+cvic@ucw.cz. Body za úkoly se budou objevovat zde, pokud chcete být uvedeni pod přezdívkou, nebo dokonce vůbec, upozorněte na to s prvním odevzdaným úkolem.
O domácích příkladech můžete diskutovat s ostatními, řešení ale musíte zformulovat a sepsat samostatně. Všechna tvrzení řádně zdůvodněte. Můžete samozřejmě používat tvrzení dokázaná na přednášce nebo na cvičení. Nebojte se odevzdat i jen částečné řešení.
Co jsme dělali
| datum | co se cvičilo |
|---|---|
| 2017-10-02 | Hříčky: Devatero mincí. Topinka. Popletené truhly. Mravenci na tyči. Lámání čokolády. Hra s čokoládou. Šachovnice. Rozcestí. Moucha kaskadérka. |
| 2017-10-09 | Indukce: Součet mocnin dvojky. Součet vážených mocnin dvojky. Součin zlomků. Dělitelnost. Dělitelnost podruhé. Součin prvočísel. Vztahy pro Fibonacciho čísla. Součet čtverců. Pluska a minuska. Egyptské zlomky. |
| 2017-10-16 | Množiny a relace: Russelův paradox. 3 operace. Vlastnosti relací. Relace podobojí. Relace podžádnou. Prostá funkce. Skládání relací. Stejné potence. |
| 2017-10-23 | Relace a funkce: Skládání funkcí. Ekvivalenční třídy. Relace dělitelnosti. Uspořádání na objednávku. Lexikografické uspořádání (slovník). Součin uspořádání (ledničky). Isomorfismus relací. |
| 2017-10-30 | Kombinatorické počítání: Počty funkcí. Počty relací. k-tice. Kuličky a přihrádky. Rovnice. Konec faktoriálu. |
| 2017-11-06 | Kombinační čísla: Stověžatá. Binomická věta. Přesmyčky. Vytýkání z kombinačního čísla. Loupežnická banda. Vnořené podmnožiny. Šotek. |
| 2017-11-13 | Inkluze a exkluze: Eratosthénovo síto. Helmův žleb. Méně zmatená šatnářka. Eulerova funkce. |
| 2017-11-20 | Pravděpodobnost: Kostky jsou vrženy. Unicyklická permutace. Nezávislé jevy. Sousedovic Pepíček. Podmíněná pravděpodobnost. Skleněnky. |
| 2017-11-27 | Pravděpodobnost 2: Psaníčka. Mincovní hody. Šatnářka se vrací na místo činu. Na honu. Základní rozdělení. |
| 2017-12-04 | Grafy (isomorfismus): Standardní grafy. Petersenův graf. Isomorfismus jako relace. Nedokonalý isomorfismus. Zoo na 4 vrcholech. |
| 2017-12-11 | Grafy (skóre, souvislost): Co znamená stejné skóre? Skóre z jedniček či dvojek. Sled implikuje cestu. Liché sledy. Doplněk nesouvislého. Bipartitní grafy. |
| 2017-12-18 | Grafy (stromy, tahy): Co se pozná ze skóre. Košaté stromy. Ještě jedna definice stromu. Lesní formule. Kostra. Extrémní grafy. Kreslení více tahy. Kneserovy grafy. |
| 2018-01-08 | Rovinné grafy: Platónská tělesa. Jednoznačnost duálu. Doplněk rovinného grafu. Eulerova formule pro nesouvislé grafy. Petersenův graf. Kreslení na plochy. |
Domácí úkoly
| série | úkoly | ||
|---|---|---|---|
| 2017-10-02 Hříčky | mince | 5 | Falešná mince |
| 12m | 10 | 12 mincí | |
| 13m | 5 | 13 mincí | |
| coko | 20 | Lichá čokoláda | |
| sack | 5 | 10 pytlů | |
| sacks | 2 | Jiných 10 pytlů | |
| miu | 8 | MIU systém | |
| duck | 7 | Kačenka | |
| 2017-10-09 Indukce | elka | 5 | Pokrytí šachovnice |
| cutp | 5 | Krájíme rovinu | |
| cuts | 8 | Krájíme prostor | |
| cube | 10 | Součet třetích mocnin | |
| fib | 8 | Fibonacciho formule | |
| fidiv | 7 | Fibonacciho dělitelnost | |
| 2017-10-16 Množiny a relace | rnonc | 4 | Skládání relací nekomutuje |
| rexpf | 7 | Mocniny relace | |
| rexpi | 7 | Mocniny do nekonečna | |
| ceqv | 8 | Uzavřenost ekvivalencí | |
| cord | 8 | Uzavřenost uspořádání | |
| 2017-10-23 Relace a funkce | bnz | 4 | Spočetná bijekce |
| bnn2 | 6 | Spočetná bijekce podruhé | |
| eq4 | 8 | Ekvivalence na čtyřech prvcích | |
| ord3 | 8 | Uspořádání na třech prvcích | |
| ord4 | 7 | Uspořádání na čtyřech prvcích | |
| vsdiv | 7 | Výška a šířka dělitelnosti | |
| 2017-10-30 Kombinatorické počítání | nekl | 10 | Neklesající funkce |
| samo | 7 | Samotář Šmudla | |
| trpi | 8 | Trpaslíci a trpaslice | |
| pes | 15 | Pestrá šachovnice | |
| 2017-11-06 Kombinační čísla | hesla | 12 | Pomsta šíleného sysadmina |
| sdp | 8 | Skoro disjunktní podmnožiny | |
| loup | 6 | Ještě jednou loupežníci | |
| sierp | 16 | Sierpi\'nského koberec | |
| pdiag | 14 | Pascalova diagonála | |
| 2017-11-13 Inkluze a exkluze | cens | 10 | Censura |
| ssum | 8 | Šatnářčina suma | |
| srek | 14 | Šatnářčina rekurence | |
| fna | 12 | Funkce na | |
| 2017-11-20 Pravděpodobnost | 2cyk | 10 | Permutace se dvěma cykly |
| 1a2 | 10 | Jednička a dvojka | |
| 3a4 | 6 | Trojka a čtyřka | |
| koza | 6 | Auto a koza | |
| napr | 10 | Napravování mincí | |
| 2017-11-27 Pravděpodobnost 2 | 2kos | 6 | Dvě kostky |
| 2kosf | 8 | Dvě kostky s falší | |
| serie | 10 | Počet sérií | |
| ppvv | 16 | Házená | |
| ntrk | 14 | Netransitivní kostky | |
| 2017-12-04 Grafy | pest | 9 | Pestrý graf |
| skup | 6 | Skoro úplné grafy | |
| dokr | 8 | Doplněk kružnice | |
| selfc | 12 | Sám sobě doplňkem | |
| strn | 10 | Strnulec | |
| nop2 | 4 | Graf bez cestičky | |
| nop3 | 6 | Graf bez cesty | |
| 2017-12-11 Grafy 2 | likr | 8 | Lichá kružnice |
| reg | 12 | Regulární grafy | |
| bico | 6 | Bipartitiní doplněk | |
| minsc | 8 | Minimální stupeň a cesta | |
| bipg | 10 | Bipartitní podgraf | |
| 2017-12-18 Grafy 3 | nkost | 9 | Graf s daným počtem koster |
| niso | 12 | Co nejvíce grafů | |
| nzst | 8 | Nezávislá množina ve stromu | |
| pvv | 10 | Počet vnitřních vrcholů | |
| 2018-01-08 Rovinné grafy | kmn | 8 | Úplné bipartitní grafy |
| 4cube | 10 | 4D krychle | |
| ak6 | 10 | Kreslení na anuloid | |
| sko6r | 10 | Skoro 6-regulární rovinné grafy | |
| doro | 10 | Doplňky rovinných grafů | |
| psten | 8 | Maximální počet stěn | |