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-02Hříč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-09Indukce: 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-16Množ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-23Relace 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-30Kombinatorické počítání: Počty funkcí. Počty relací. k-tice. Kuličky a přihrádky. Rovnice. Konec faktoriálu.
2017-11-06Kombinač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-13Inkluze a exkluze: Eratosthénovo síto. Helmův žleb. Méně zmatená šatnářka. Eulerova funkce.
2017-11-20Pravděpodobnost: Kostky jsou vrženy. Unicyklická permutace. Nezávislé jevy. Sousedovic Pepíček. Podmíněná pravděpodobnost. Skleněnky.
2017-11-27Pravděpodobnost 2: Psaníčka. Mincovní hody. Šatnářka se vrací na místo činu. Na honu. Základní rozdělení.
2017-12-04Grafy (isomorfismus): Standardní grafy. Petersenův graf. Isomorfismus jako relace. Nedokonalý isomorfismus. Zoo na 4 vrcholech.
2017-12-11Grafy (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-18Grafy (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-08Rovinné 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
mince5Falešná mince
12m1012 mincí
13m513 mincí
coko20Lichá čokoláda
sack510 pytlů
sacks2Jiných 10 pytlů
miu8MIU systém
duck7Kačenka
2017-10-09

Indukce
elka5Pokrytí šachovnice
cutp5Krájíme rovinu
cuts8Krájíme prostor
cube10Součet třetích mocnin
fib8Fibonacciho formule
fidiv7Fibonacciho dělitelnost
2017-10-16

Množiny a relace
rnonc4Skládání relací nekomutuje
rexpf7Mocniny relace
rexpi7Mocniny do nekonečna
ceqv8Uzavřenost ekvivalencí
cord8Uzavřenost uspořádání
2017-10-23

Relace a funkce
bnz4Spočetná bijekce
bnn26Spočetná bijekce podruhé
eq48Ekvivalence na čtyřech prvcích
ord38Uspořádání na třech prvcích
ord47Uspořádání na čtyřech prvcích
vsdiv7Výška a šířka dělitelnosti
2017-10-30

Kombinatorické počítání
nekl10Neklesající funkce
samo7Samotář Šmudla
trpi8Trpaslíci a trpaslice
pes15Pestrá šachovnice
2017-11-06

Kombinační čísla
hesla12Pomsta šíleného sysadmina
sdp8Skoro disjunktní podmnožiny
loup6Ještě jednou loupežníci
sierp16Sierpi\'nského koberec
pdiag14Pascalova diagonála
2017-11-13

Inkluze a exkluze
cens10Censura
ssum8Šatnářčina suma
srek14Šatnářčina rekurence
fna12Funkce na
2017-11-20

Pravděpodobnost
2cyk10Permutace se dvěma cykly
1a210Jednička a dvojka
3a46Trojka a čtyřka
koza6Auto a koza
napr10Napravování mincí
2017-11-27

Pravděpodobnost 2
2kos6Dvě kostky
2kosf8Dvě kostky s falší
serie10Počet sérií
ppvv16Házená
ntrk14Netransitivní kostky
2017-12-04

Grafy
pest9Pestrý graf
skup6Skoro úplné grafy
dokr8Doplněk kružnice
selfc12Sám sobě doplňkem
strn10Strnulec
nop24Graf bez cestičky
nop36Graf bez cesty
2017-12-11

Grafy 2
likr8Lichá kružnice
reg12Regulární grafy
bico6Bipartitiní doplněk
minsc8Minimální stupeň a cesta
bipg10Bipartitní podgraf
2017-12-18

Grafy 3
nkost9Graf s daným počtem koster
niso12Co nejvíce grafů
nzst8Nezávislá množina ve stromu
pvv10Počet vnitřních vrcholů
2018-01-08

Rovinné grafy
kmn8Úplné bipartitní grafy
4cube104D krychle
ak610Kreslení na anuloid
sko6r10Skoro 6-regulární rovinné grafy
doro10Doplňky rovinných grafů
psten8Maximální počet stěn

Výsledky

jméno příklady bodů
Tomáš Domesmince(5) sack(5) 12m(10) 13m(5) sacks(2) miu(8) duck(7) cube(10) cuts(8) fib(8) cutp(5) fidiv(7) elka(5) rnonc(4) rexpi(7) ceqv(8) rexpf(7) cord(8) bnz(4) bnn2(6) eq4(8) ord3(8) vsdiv(7) samo(7) trpi(8) pes(15) nekl(10) loup(10) sdp(8) sierp(16) pdiag(14)240.0
René Gabesamsack(5) sacks(2) mince(0) miu(0) coko(0) 12m(10) duck(7) elka(0) cutp(5) cuts(0) cube(10) rnonc(4) bnz(4) eq4(6) vsdiv(0) samo(7) trpi(8) hesla(0) sdp(6) loup(6) cens(10) srek(0) fna(12) koza(6) 2cyk(10) 3a4(0) 2kos(6) 2kosf(8) dokr(8) pest(9) nop2(4)153.0
Tomáš Havelka12m(10) sack(5) miu(8) duck(7) fib(8) elka(5) fidiv(0) cuts(0) cutp(5) bnn2(0) bnz(0) eq4(8) samo(7) trpi(8) pes(15) hesla(12) loup(6) cens(10) koza(6) ntrk(14)134.0
Richard Hladíkmince(5) 12m(10) 13m(5) sack(5) sacks(2) miu(8) duck(7) fidiv(7) cube(10) rnonc(4) rexpf(7) rexpi(7) ceqv(8) cord(8) bnz(4) bnn2(6) eq4(8) ord3(8) ord4(7) vsdiv(7) nekl(10) samo(7) trpi(8) pes(15)173.0
Matěj Hrbáčeksack(5) sacks(2) duck(7) 12m(10) 13m(5) fib(8) cube(10) elka(5) cutp(5) rnonc(4) ceqv(8) cord(8) rexpi(7) rexpf(7) bnz(4) bnn2(6) vsdiv(0) samo(7) trpi(8) hesla(12) sdp(0) cens(10) srek(14) koza(6) loup(3) 2kos(6) 2kosf(8) nop2(4) nop3(6) reg(0) bico(0) minsc(8)193.0
Michal Hurábelka(5) cutp(5) cube(10) fib(8) fidiv(7) reg(0) bico(6) minsc(0) likr(0) bipg(0) nkost(9) pvv(0) nzst(8)58.0
Daniela Chomová12m(10) 13m(0) sack(5) sacks(2) duck(7) fidiv(7) fib(8) cube(10) elka(0) miu(4) rnonc(4) rexpf(0) trpi(0) samo(7) pes(15) hesla(12) cens(10) koza(6) loup(6) ntrk(14) dokr(8)135.0
Jakub Kozelmiu(8) sack(5) sacks(2) mince(0) duck(0) 12m(10) elka(5) cutp(5) cuts(0) fib(8) rnonc(4) rexpf(0) ceqv(0) cord(0) bnz(4) bnn2(0) eq4(8) ord3(0) ord4(0) nekl(10) samo(7) trpi(0) pes(15) hesla(12) sdp(0) koza(6) napr(10) pest(9) selfc(0) nop2(4) nop3(6)138.0
Lukáš Kriškomince(5) 12m(10) 13m(5) sack(5) sacks(2) miu(8) duck(7) elka(5) cutp(5) cube(10) fib(8) rnonc(4) rexpi(7) rexpf(7) fidiv(3.5) cord(8) ceqv(8) bnz(4) bnn2(6) vsdiv(3) eq4(0) samo(7) trpi(8) pes(15) hesla(12) sdp(8) loup(10) sierp(16) ssum(8) srek(14) fna(12) cens(10) 3a4(6) 2cyk(10) 1a2(10) koza(6) pest(9) skup(6) dokr(8) strn(10) nop2(4)309.5
Ivan Krasičenkosack(5) sacks(2) 12m(10) miu(8) mince(5) cutp(5) elka(5) cube(10) rnonc(4) rexpf(7) rexpi(7) bnz(4) bnn2(6) eq4(8) ord3(8) cens(10) fna(12) 2cyk(10) pest(9)135.0
Stanislav Lukešsack(5) sacks(2) 12m(10) duck(7) mince(5) miu(8) fib(8) cube(10) ceqv(8) rexpi(7) rnonc(4) fidiv(7) bnn2(6) bnz(4) eq4(8) ord3(8) ord4(7) sierp(16)130.0
Matouš Maříkmince(5) 12m(10) 13m(5) sack(5) sacks(2) miu(8) duck(7) elka(5) cutp(5) cuts(0) fib(8) fidiv(7) cube(5) rnonc(4) rexpi(7) rexpf(7) ceqv(0) bnn2(6) bnz(4) ord3(8) ord4(0) eq4(4) nekl(0) samo(7) trpi(8) 2cyk(0) 3a4(6) koza(6)139.0
Štěpán Stenchlákmince(5) sack(5) sacks(2) miu(8) duck(7) elka(5) cutp(5) cube(10) fib(8) fidiv(7) rnonc(4) rexpf(7) rexpi(7) ceqv(8) cord(8) bnz(4) bnn2(6) eq4(8) vsdiv(0) hesla(0) sdp(8) loup(6) cens(10) ssum(8) fna(12) pest(9) skup(6) dokr(8) selfc(12) strn(10) nop2(4) nop3(6)213.0
Václav Šraier12m(10) duck(7) sack(5) sacks(2) mince(5) cube(10) elka(5) fidiv(7) fib(8) rnonc(4) rexpi(7) bnz(4) bnn2(6) vsdiv(7) eq4(8) samo(7) trpi(8) hesla(0) loup(6) cens(10) koza(6)132.0
Michal Töpfersack(5) sacks(2) miu(8) fib(8) fidiv(7) cube(10) elka(5) mince(5) 12m(10) 13m(5) duck(7) cuts(8) cutp(5) rnonc(4) rexpf(7) rexpi(7) ceqv(8) cord(8) bnz(4) bnn2(6) eq4(8) sdp(8) 2kos(6) 2kosf(8)159.0
Pavel Turinskýsack(5) sacks(2) mince(5) cube(10) elka(5) fib(8) fidiv(7) rexpi(7) rnonc(4) rexpf(7) ceqv(8) cord(8) bnn2(6) bnz(4) eq4(8) ord3(8) ord4(7) vsdiv(7) trpi(8) nop2(4)128.0
Václav Volhejn12m(10) sack(5) miu(8) elka(5) cutp(5) cube(10) coko(20) rexpf(7) rexpi(7) rnonc(4) nekl(10) sierp(16) pdiag(14) 2cyk(10)131.0
Lia Zulkarneevasack(5) miu(8) 12m(10) elka(5) cutp(5) fidiv(7) fib(8) cuts(8) cube(10) rexpf(7) rexpi(7) ceqv(0) cord(0) rnonc(4) ord3(8) ord4(0) bnz(4) bnn2(6) vsdiv(0) nekl(6) samo(7) trpi(0) loup(6) sdp(6) hesla(0) srek(14) ssum(8) fna(12) cens(10) eq4(4) sierp(8) 2cyk(10) 1a2(10) 3a4(6) koza(6)215.0
Jiří Žilkahesla(0) cens(10) srek(14)24.0
Ferda Mravenec609

Pokud jste úkol odevzdávali na papíře a nemáte v tabulce plný počet bodů, stavte se někdy za mnou, rád vysvětlím. Pokud takové řešení v tabulce zcela chybí, nejspíš nebylo podepsané.

Stránku spravuje Martin Mareš