První sada zadání

Napsat referát z předmětu Diskrétní matematika musí každý student sám, žádná spolupráce na výsledném textu referátu není dovolena. Je však povoleno o zadání referátu volně diskutovat se spolužáky i na cvičeních, vše kromě samotného zpracování. Hodnocení referátů je buď 0 nebo 10 bodů, tj. stylem ANO/NE. V případě mimořádně kvalitního referátu lze udělit i 20 bodů. Referát odevzdáváte vyhlašovateli tématu e-mailem nebo na papíře. Cvičící vás také může vyzvat k ústnímu přednesení vašeho referátu během cvičení.

Každý referát vypracujete formou odborného článku, tj. musí mít nadpis, jméno, abstrakt a přehledné členění na sekce, to vše psané na počítači v rozsahu asi 2 až 5 stran A4. Abstrakt je zhruba jeden 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 opište vlastními slovy v úvodu, popište co jste vlastně řešili. Pro ukázku správného stylu uvádíme dva referáty DIM z roku 2003: 1. referát a 2. referát s extra body.

Následují zadání první sady samostatných referátů pro předmět Diskrétní matematika. K vybranému tématu se přihlásíte v KatISu (až do nastavených limitů).

1. Algoritmus pro počet inverzí

Referát vypracovaný podle pokynů posílejte na adresu: Radim<tečka>Baca<zavináč>vsb<tečka>cz.

Navrhněte algoritmus, který spočítá počet inverzí v permutaci n prvků { 1, 2, ..., n } v podstatně méně než n² krocích. Dokažte správnost Vašeho algoritmu.
(Inverzí v permutaci { r₁, r₂, ..., r_n } rozumíme dvojici i, j takovou, že r_i < r_j a přitom i > j.)

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

2. Pokrytí šachovnice I

Referát vypracovaný podle pokynů posílejte na adresu: aim<zavináč>seznam<tečka>cz.

Máme šachovnice o rozměrech n×n políček. K dispozici máme neomezený počet dílků ve tvaru kostek známé hry TETRIS, každý složený ze čtyř čtverečků stejného rozměru jako jedno políčko šachovnice. Pro která n je možno šachovnici pokrýt dílkem "I" (4×1 políčko)? Pro která n je možno šachovnici pokrýt dílkem "O" (2×2 políčka)? Pro která n je možno šachovnici pokrýt dílkem "T" (3 a 1 políčko uprostřed)? Pro která n je možno šachovnici pokrýt dílkem "L" (3 a 1 políčko na kraji) Pro která n je možno šachovnici pokrýt dílkem "S" (2 a 2 políčka).
Své tvrzení dokažte.

3. Pokrytí šachovnice II

Referát vypracovaný podle pokynů posílejte na adresu: aim<zavináč>seznam<tečka>cz.

Máme šachovnice o rozměrech 2ⁿ×2ⁿ, na které chybí jedno políčko. K dispozici máme neomezený počet dílků ve tvaru L složené ze tří čtverečků stejného rozměru jako jedno políčko šachovnice. Ukažte, že šachovnici (bez chybějícího políčka) je možno vždy pokrýt příslušným počtem dílků ve tvaru L. Umíte sestavit obecnou formuli pro počet různých pokrytí? Pokud ano, formuli dokažte.

4. Střední hodnota prvočíselné kostky

Referát vypracovaný podle pokynů posílejte na adresu: Stepan<tečka>Raska<zavináč>seznam<tečka>cz.

Máme k-stěnnou kostku, jejíž stěny jsou očíslovány prvními k prvočísly.
Zapíšeme si číslo p, které nám padne při prvním hodu kostkou. Nyní p-krát hodíme k-stěnnou kostkou. Jaká je střední hodnota součtu ok při těchto p hodech?

Vyčíslete střední hodnotu pro k = 6, 10 a 12.

5. Střední hodnota náhodné kostky

Referát vypracovaný podle pokynů posílejte na adresu: Stepan<tečka>Raska<zavináč>seznam<tečka>cz.

Máme k-stěnnou kostku, jejíž stěny jsou očíslovány 1, 2, ..., k.
Zapíšeme si čísla c₁, c₂, ..., c_k, která nám padnou při k hodech kostkou. Tato čísla zapíšeme na k nálepek, kterými přelepíme stěny kostky. Předpokládáme, že nová "náhodná" kostka je spravedlivá, tj. že nalepené papírky neovlivní relativní četnosti jednotlivých stran. Jaká je střední hodnota součtu ok při k hodech novou "náhodnou" kostkou?

6. Mississ

Referát vypracovaný podle pokynů posílejte na adresu: Michael<tečka>Kubesa<zavináč>vsb<tečka>cz.

Mějme dáno slovo (posloupnost) "MISSISSIPPI". Kolik z něj lze vytvořit různých slov takových, že neobsahují vybranou podposloupnost (podslovo, které vznikne vynecháním některých, ne nutně sousedících, písmen) "MISSISS"?

MISSISSIPPI ANEB V ČEM JE CHYBA

Všichni z Vás se dopracovali k závěru, že všech možných různých slov, které lze vytvořit že slova MISSISSIPPI je (11!)/(4!4!2!).

Mnoho z Vás zjistilo, že slov, které obsahují podslovo MISSISS (písmena tohoto podslova nemusí bytí nutné sousedící!!!) je (11 nad 7)(4!)/(2!2!). Tedy úvahu jste vedli takto. Výběru 7 pozic z 11 a obsadím je písmeny slova MISSISS (v tomto pořadí!). Takových různých výběru ovšem existuje (11 nad 7). Dále ke každému takovému výběru nechám na zbývajících pozicích permutovat zbylá písmena I,I,P,P. Takových různých permutaci ale je (4!)/(2!2!).

Úvaha je to pěkná, leč není správná, neboť některá slova obsahující podslovo MISSISS započítáváte vícekrát. Ukažme si příklad.

DOMLUVA: Písmena umístěna na VYBRANÉ pozice budou psána velkým a zbylá malým písmem.

(a) Vyberme pozice 1,3,5,6,7,9,10. Potom ovšem jedno z takto vzniklých slov bude:

MiIpSSIiSSp

(b) Vyberme pozice 1,2,5,6,8,9,10. Potom ovšem jedno z takto vzniklých slov bude:

MIipSSiISSp

Tato slova jsou ovšem stejná, zatímco Vy jste je považovali za nutně různá. (Vnímavý posluchač jistě vidí, že bychom umělí najít i další výběry přinášející totéž slovo.

Jak tuto chybu odstranit?

7. Večírek I

Referát vypracovaný podle pokynů posílejte na adresu: Radim<tečka>Baca<zavináč>vsb<tečka>cz.

Na večírku se sešly 4 manželské páry. Dlouholetá zkušenost lidského rodu říká, že pokud má být na večírku zachován klid, neměli by manželé sedět vedle sebe. Kolika různými způsoby lze rozesadit těchto 8 lidí kolem kulatého stolu tak, aby manželé neseděli vedle sebe?
(Dvěma různými rozesazeními rozumíme, že pro alespoň jednu osobu platí, že že má v těchto dvou rozesazeních různého pravého resp. levého souseda.)

8. Večírek II

Referát vypracovaný podle pokynů posílejte na adresu: Michael<tečka>Kubesa<zavináč>vsb<tečka>cz.

Na večírku je 25 lidí. Víme, že libovolná dvojice zná dohromady všech zbývajících 23 lidí. Lze tyto účastníky večírku rozesadit kolem kulatého stolu tak, že každý sedí mezi svými známými? Své rozhodnutí pečlivě zdůvodněte.

9. Důkaz I

Referát vypracovaný podle pokynů posílejte na adresu: ondik<tečka>kok<zavináč>seznam<tečka>cz.

Dokažte platnost následujícího vztahu:

Návod: Mějme množiny M, N, kde |M|=m a |N|=n. Obě strany rovnosti určují počet všech uspořádaných dvojic množin (X,Y), kde X je libovolná podmnožina množiny M a Y je libovolná m-prvková podmnožina množiny N ∪ X.

10. Důkaz II

Referát vypracovaný podle pokynů posílejte na adresu: ondik<tečka>kok<zavináč>seznam<tečka>cz.

Dokažte:

11. Vážení mincí

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Máme dáno n mincí. Jedna z nich je falešná, což se projeví jinou hmotností mince. Nevíme však, jestli je těžší nebo lehčí než ostatní mince. K dispozici máme rovnoramenné váhy.
Kolik nejméně vážení potřebujete pro nalezení falešné mince*? Najděte algoritmus vážení a jeho správnost dokažte.
 *   Alternativně můžete vyřešit podobnou (možná lehčí?!?) úlohu, kdy se navíc snažíme zjistit, zda falešná mince je lehčí nebo těžší než pravá mince.

12. Čtyřstěn

Referát vypracovaný podle pokynů posílejte na adresu: martin<tečka>kot<zavináč>vsb<tečka>cz.

Máme dán na "šachovnici" ve tvaru rovnostranného trojúhelníka o straně délky n. Trojúhelník je rozdělen na menší rovnostranné trojúhelníky o straně délky 1. Do jednoho vrcholu umístíme čtyřstěn o straně 1. Čtyřstěn můžeme po šachovnici přemisťovat, avšak pouze překlopením přes hranu (jako kdyby byl velmi těžký). Je možné takto projít celou šachovnici, abychom na každé poli postavili čtyřstěn pouze jedenkrát? Své tvrzení dokažte.
Jaký je nejmenší počet s políček, na kterých se čtyřstěn objeví vícekrát? Pokud se na políčku čtyřstěn objeví k-krát, do celkového součtu s započítáme políčko (k-1)-krát.
Zjistěte číslo s řešení pro n = 4, 5 a 6.

Sestavte algoritmus, který najde řešení s minimálním s.

Programovací jazyk je libovolný, nejdůležitější součástí vašeho řešení je slovní popis a rozbor činnosti vašeho algoritmu, zahrnující i zdůvodnění jeho správnosti, a komentovaný výpis hlavních částí vašeho programu. (Do komentovaného výpisu programu zahrňte jen skutečně výkonné části kódu, není důležité, jak ošetřujete vstup a výstup a jaké máte knihovny.) Mějte na paměti, že výpis programu je jen přílohou, klíčový je slovní popis a rozbor.

13. Egyptské zlomky

Referát vypracovaný podle pokynů posílejte na adresu: lukas<tečka>konecny<zavináč>volny<tečka>cz.

Obyvatelé staroegyptské říše zapisovali zlomky jako součet převrácených hodnot celých čísel. Například 4/5 = 1/2 + 1/4 + 1/20.
Vezmeme následující algoritmus pro zápis zlomku p/q v uvedeném tvaru. Je-li 0 < p < q, napiš zlomek 1/ceil(q/p) a vypočítej p/q - 1/ceil(q/p) (kde ceil(x) je horní celá část čísla x). Je-li výsledek nenulový, vyjádři výsledný zlomek opět pomocí uvedeného algoritmu.
Dokažte, že tento algoritmus je konečný (tj. vždy skončí po konečném počtu kroků).

14. Pokrytí šachovnice III

Referát vypracovaný podle pokynů posílejte na adresu: martin<tečka>kot<zavináč>vsb<tečka>cz.

Máme šachovnice o rozměrech n×n políček. K dispozici máme neomezený počet dílků ve tvaru kostek známé hry TETRIS, každý složený ze čtyř čtverečků stejného rozměru jako jedno políčko šachovnice. Navrhněte algoritmus, který spočítá počet pokrytí šachovnice o rozměrech n×n pro různé dílky hry TETRIS. Tj. spočítá počet různých pokrytí dílkem "I" (4×1 políčko), počet různých pokrytí dílkem "O" (2×2 políčka), počet různých pokrytí dílkem "T" (3 a 1 políčko uprostřed), počet různých pokrytí dílkem "L" (3 a 1 políčko na kraji) a počet různých pokrytí dílkem "S" (2 a 2 políčka).
Zjistěte počty řešení pro n = 8, 10 a 12.

15. Pokrytí šachovnice IV

Referát vypracovaný podle pokynů posílejte na adresu: martin<tečka>kot<zavináč>vsb<tečka>cz.

Máme šachovnice o rozměrech 2ⁿ×2ⁿ, na které chybí jedno políčko. K dispozici máme neomezený počet dílků ve tvaru L složené ze tří čtverečků stejného rozměru jako jedno políčko šachovnice. Navrhněte algoritmus, který spočítá počet pokrytí šachovnice (bez chybějícího políčka) příslušným počtem dílků ve tvaru L.
Zjistěte počty řešení pro n = 8, 10 a 12.

16. Permutace nejvyššího řádu

Referát vypracovaný podle pokynů posílejte na adresu: Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Mějme množinu [1,n] a její permutaci p. Složené permutace s sebou p o p označíme p², identickou permutaci označíme i . Řád permutace je takové nejmenší číslo n, pro které je pⁿ = i. Navrhněte algoritmus, který pro dané n najde permutaci nejvyššího řádu.
Zjistěte počty řešení pro n = 10, 12 a 30.

Mnoho zdaru při řešení samostatných referátů!

Poznámka

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