Homepage
Curriculum vitae
Publikace
Výuka
Kontakt
   

Referáty z Diskrétní matematiky ZS 2009/2010

Toto není stránka aktuálního akademického roku.

Každý student musí napsat referát z předmětu Diskrétní matematika sám, žádná spolupráce na textu referátu není dovolena. Je pouze povoleno diskutovat o zadání referátu se spolužáky a položit otázky na cvičeních.

Bodování
V každém referátu jsou dva příklady, jeden z kombinatoriky, druhý z teorie grafů. Hodnotí se každý příklad 0/3/5 bodů, tj. stylem NE/TÉMĚŘ SPRÁVNĚ/ANO. V případě mimořádně kvalitního řešení příkladu lze udělit i 10 bodů za příklad. Referát vypracujte formou odborného článku: nadpis, jméno, abstrakt a přehledné členění na sekce. Doporučujeme vypracovat referát včetně titulního listu, na kterém budou uvedeny kromě názvu referátu i údaje studenta (jméno, osobního číslo, ...). Bude psán na počítači v rozsahu asi 2 až 5 stran A4. Referát odevzdáváte e-mailem v předepsaném formátu nebo na papíře příslušnému vyučujícímu (kontakt je uveden u každého zadání). Cvičící vás může vyzvat k přednesení vašeho referátu během cvičení.

Struktura referátu
Abstrakt je odstavec shrnující o čem referát je a co je hlavním přínosem vaší práce. Zahrnuje i podstatu zadání. Zadání referátu nekopírujte do výsledného textu, ale vlastními slovy v úvodu popište co jste řešili.

Preferujeme odevzdávání referátů e-mailem ve formátu PDF, případně postscript, přičemž v e-mailu musíte uvést studentské číslo a soubor přikládáte nesbalený! Součástí názvu souboru bude Váš login.
Pokud PDF zatím neumíte vytvářet, pořiďte si OpenOffice nebo pdfTeX, obojí je zdarma.
Výjimečně lze přijmout i jiné otevřené formáty, jako HTML. Export v těchto formátech však musí být proveden tak, aby byl výsledek přenositelný. Nebudou přijaty žádné referáty obsahující soubory nebo vsuvky ve formátu WMF(!) nebo používající špatně převedenou diakritiku ve jménech souborů.

Termín odevzdání
Termín odevzdání je v pondělí 7.12.2009 ve 13:00.
Číslo zadání bude studentům přiděleno na cvičení. Můžete se podívat na vzorový referát ve formátu pdf: dim_vzorovy_referat.pdf.

 

1. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .

Kombinatorika
Mějme písmena A,D,H,K,O,R,T,U. Kolik různých slov můžeme sestavit z těchto písmen, pokud tato slova nesmí obsahovat "podslova" AUTO, RUKA a HOD (například hAdUrTkO je nepřípustné slovo).

Teorie grafů
Trianglie je malá ostrovní země, ve které žádná cesta nekončí jinak, než křižovatkou ve tvaru Y. Mladý princ se vydá na cesty po ostrově. Nasedne na koně a chystá se odjet. Když projíždí cestou pod okny paláce, volá na něj královna z balkónu: "Ale princi, jak najdeš cestu zpět do paláce?" On ji odpověděl: "Neboj matko, vždy na každé druhé křižovatce odbočím vpravo a jinak budu odbočovat vlevo. Takto jistě dříve nebo později přijedu zpět před palác." Měl princ pravdu?
Návod: Úlohu namodelujte grafem, který je konečný. Dále si všimněte, že budete-li nějaký sled v grafu stále prodlužovat, tak dříve nebo později se musí některé vrcholy nebo hrany zopakovat.

 

2. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .

Kombinatorika
Popíšeme pravidla jedné hry s kostkami, které se někdy říká vrchcáby. Hráč hodí šest kostek a pokaždé musí odložit nejméně jednu bodovanou stranou a pak může házet dál, nebo předat hru dalšímu hráči. Pokud v některém hodu nehodí nic, ztrácí vše, co zatím v tomto kole nasbíral. Bodované kostky jsou s číslem 1 a 5. Body jsou také za jakoukoli trojici a za postupku. Pokud padnou více než tři stejné hodnoty, tak je bodujeme stejně jako trojice.
550 bodů
1100 bodů
3x11000 bodů
3x2200 bodů
3x3300 bodů
3x4400 bodů
3x5500 bodů
3x6600 bodů
1234562000 bodů (postupka)
Jaká je pravděpodobnost, že při jednom hodu všemi šesti kostkami nepadne žádná bodovaná kombinace?

Teorie grafů
Máme dán graf na devíti vrcholech, který je na obrázku. Vašim úkolem je ukázat, že do vrcholů místo písmen A až I nejdou vložit číslice 1 až 9 tak, aby žádná dvě po sobě jdoucí čísla (např. dvojka má sousedy 1 a 3) nebyla v grafu spojená hranou.
Návod: Využijte doplněk grafu.

graf 3x3 vrcholy

 

3. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .
(hodnocení tohoto referátu nebude probíhat mezi 5.12. a 16.12.2009; termín odevzdání však platí)

Kombinatorika
Najděte vhodná různá celá čísla a1, a2, ..., a6 a rozmístěte je na poctivou kostku tak, aby střední hodnota součinů horních a spodních stěn byla stejná jako druhá mocnina aritmetického průměru hodnot a1a6. Navíc požadujme, aby se střední hodnota součinů horních a spodních stěn rovnala některému číslu na kostce. Předpokládejte, že -50 ≤ a1, a2, ..., a6 ≤ 50.

Teorie grafů
Pan Wassermann bydlí v městečku, které je postaveno uprostřed jezera. Každý z obyvatel vlastní jeden dům plující na vodě. Domy jsou mezi sebou spojeny lávkami, a to tak, že každý dům je spojen lávkou s minimálně dvěma dalšími domy. Víme, že pokud se jedna libovolná lávka utrhne, je stále možno dostat se z každého domu do všech ostatních. Pan Wassermann rád navštěvuje své přátele. Ukažte, že si pan Wassermann může vždy naplánovat cestu k nějakému (libovolnému) příteli tak, že na zpáteční cestě do svého domu nepoužije žádnou lávku, kterou použil na cestě tam.

 

4. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .
(hodnocení tohoto referátu nebude probíhat mezi 5.12. a 16.12.2009; termín odevzdání však platí)

Kombinatorika
Nakreslíme pět kružnic tak, aby se navzájem protínaly jako na obrázku. Do každé z patnácti vyznačených oblastí položíme jednu minci lícem vzhůru. Nyní máme pouze pět přípustných operací:

kruhy a mince

  • Pa - všechny mince v kruhu A převrátíme (tzn. pokud byla nějaká mince v kruhu A lícem vzhůru, převrátíme ji lícem dolů, pokud byla lícem dolů, převrátíme ji lícem vzhůru).
  • Operace Pb, Pc, Pd, Pe v kruzích B, C, D, E definujeme obdobně.
Úkol: Ukažte, že není možné s využitím libovolného počtu operací Pa, Pb, Pc, Pd, Pe zařídit, aby pouze mince ve vyznačených (modrých) oblastech byly lícem dolů a ve všech zbývajících oblastech byly lícem vzhůru.

Teorie grafů
V severním Skotsku je útulné, podmračené městečko Walk & Dream, v němž se nachází 143 okouzlujících pamětihodností, jež jsou propojeny 142 úzkými a stinnými uličkami tak, že se případný návštěvník nikdy nemůže pohybovat v kruhu. A co víc, v centru Walk & Dream je blízko křižovatky nejnavštěvovanější místo "Crying Eyes Pub" (což je jedna z pamětihodností), kde se sbíhá 41 turistických uliček. Ukažte, že ve zmiňovaném severoskotském městečku je alespoň 41 slepých ulic.

 

5. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .

Kombinatorika
Stojím pod schodištěm s 23 schody a chystám se je vyjít. Každý krok bude buď přes dva nebo tři schody. Kolika různými způsoby mohu schodiště vyjít, pokud poslední krok bude vždy končit přesně na horním schodu?

Teorie grafů
Mějme graf G. Doplněk (komplement) grafu G značíme G a platí V(G) = V(G), E(G) = { xy : xy ∉ E(G) } pro každé dva vrcholy x,y ∈ V(G). Dokažte, že pokud |V(G)|≥6, pak G nebo G obsahuje cyklus délky 3.

Jestliže se u některých G nadtržítko nezobrazuje správně, tak použijte následující zadání:
Mějme graf G. Doplněk (komplement) grafu G značíme G' a platí V(G) = V(G'), E(G') = { xy : xy ∉ E(G) } pro každé dva vrcholy x,y ∈ V(G). Dokažte, že pokud |V(G)|≥6, pak G nebo G' obsahuje cyklus délky 3. Dokažte, že pokud |V(G)|≥6, pak G nebo G' obsahuje cyklus délky 3.

 

6. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .

Kombinatorika
Nechť 1 = d1 < d2 < ... < dk = a jsou všichni dělitelé čísla a. Číslo a se nazývá dokonalé, pokud a = d1+d2+...+dk-1. (Příklady: 6=1+2+3, 28 = 1+2+4+7+14). Dokažte, že pro každé dokonalé číslo a = d1+d2+...+dk-1 platí, že 1/d1 + 1/d2 + ... + 1/dk = 2.
Návod: Nejdříve si uvědomte, že pokud d dělí a, pak také a/d dělí a.

Teorie grafů
Mějme souvislý graf G, kde pro každé dva vrcholy x,y ∈ V(G) platí, že buď nemají žádného společného souseda nebo jich mají pět. Ukažte, že G musí být k-pravidelný pro nějaké k.
Návod: Nejdříve dokažte následující tvrzení: Nechť A,B ⊆ V(G) a nechť každý vrchol a ∈ A má přesně čtyři sousedy v B a každý vrchol b ∈ B má přesně čtyři sousedy v A. Potom |A| =|B|. Dále si uvědomte, že stačí dokázat deg(u) = deg(v), pro libovolné dva SOUSEDNÍ vrcholy u,v ∈ V(G).

 

7. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .

Kombinatorika
Ve skupině n lidí zná každý nějakou "horkou novinku" (zvanou také "drb"), kterou nikdo ze zbývajících lidí nezná. Navzájem si drby sdělují telefonem, přičemž při každém telefonátu si oba účastníci poví navzájem všechny drby, které se dozvěděli. Pokud například jeden telefonující zná jen jednu (svoji) horkou novinku a druhý již zná tři jiné, tak po skončení telefonu znají oba všechny čtyři drby. Ukažte, že pro n ≥ 4 vždy stačí 2n-4 telefonátů, aby se každý z n lidí dozvěděl všechny drby.
Návod: Označme si nejmenší počet telefonů pro skupinu n lidí jako D(n). Určete D(1), D(2), D(3), D(4) a dále postupujte matematickou indukcí.

Teorie grafů
Ve firmě pracuje kromě ředitele i několik zaměstnanců. Mužů je mezi zaměstnanci o tři více než žen. Během doby se zaměstnanci mnohokrát stěhovali a sdíleli kanceláře. Víme, že jedenáct zaměstnanců již během doby sdílelo kancelář s dvěma kolegy (neříkáme se dvěma současně!), tři se čtyřmi kolegy a ostatní sdíleli kancelář s jedním, třemi nebo pěti kolegy (nevíme kolik jich je, jen víme, že takoví zaměstnanci ve firmě jsou). Ředitel má nyní kancelář sám pro sebe. Bylo tomu tak vždy? Podrobně vysvětlete!

 

8. Zadání

Referát vypracovaný podle pokynů posílejte na adresu .

Kombinatorika
Dva desperáti se rozhodli, že ukončí svůj spor soubojem. Oba dobře ví, že jeden z nich je lepší střelec. První zasáhne a zastřelí svého soupeře s pravděpodobností p1, druhý s pravděpodobností p2. Aby byl souboj vyrovnaný, domluvili se, že budou střílet postupně. Nejprve vystřelí slabší střelec. Pokud mine, bude na řadě druhý střelec. Jestliže i ten mine, bude pokračovat opět první střelec. Souboj pokračuje tak dlouho, dokud nezůstane pouze jeden desperát. Jaké jsou pravděpodobnosti p1 a p2 úspěšné střelby, jestliže víme, že v této hře mají oba desperáti stejnou šanci přežít? Najděte všechna řešení!
Návod: Rozmyslete si pravděpodobnosti výhry po prvním kole, druém kole, třetím kole a zkuste zobecnit. Využijte znalost součtu geometrické řady.

Teorie grafů
Elektrická rozvodná síť tvoří kostru T grafu G, jehož vrcholy jsou místa spotřeby a transformační stanice. Hrany grafu reprezentují vedení vysokého i nízkého napětí v grafu. Představme si, že postavíme nějakou libovolnou(!) záložní síť, která také spojuje všechny vrcholy grafu G a která také tvoří kostru T' grafu G. Zdůrazněme, že záložní síť může být libovolná, ne taková, jakou si naplánujeme.

V případě poruchy, kdy dojde k přerušení nějakého vedení (hrany) e mezi dvěma vrcholy kostry T, bude přerušeno spojení v rozvodné síti. Ukažte, že v záložní síti T' vždy najdeme takové vedení e' mezi dvěma vrcholy, aby síť, která vznikne nahrazením přerušeného vedení e v síti T vedením e', spojovala všechna místa v síti popsané grafem G.

Jinými slovy ukažte, že v kostře T' vždy najdeme hranu e' tak, aby graf T - e + e', který vznikne nahrazením hrany e v kostře T hranou e', byl také kostrou grafu G.

 

Náhradní referát

Kombinatorika
Určete, kolik nul má na konci číslo 1063!.

Teorie grafů
Najděte všechny neizomorfní stromy Tn na n vrcholech s nejvyšším stupněm vrcholu n-3, pokud je n alespoň 6.

 

 

Mnoho zdaru při řešení samostatného referátu!

 

Poznámka

Pokud najdete v textu zadání chybu, dejte mi, prosím, vědět. Pokusím se chyby co nejdříve opravit.

Toto není stránka aktuálního akademického roku.

Zpět na stránku předmětu Diskrétní matematika.


email
kancelář EA536, tel. 597 325 972
Upraveno: 29.12.2011