Odevzdávejte do 17.11. v jednom "soběstačném" PDF souboru!

Dobrovolný a nenárokový úkol, bonusovými body (kolem 1-20 i více) budou oceněny jen ta nejlepší řešení -- není limit na počet, ale jen na kvalitu.

 

Zadání příkladu

Představme si, že se studenti IB000 sejdou na velkém nádvoří dlážděném čtvercovými panely. Každý student stojí oběma nohama na jednom panelu (a nezasahuje do žádného jiného panelu), přičemž na jednom panelu může stát více studentů najednou. Pokud se však na jednom panelu sejdou více než čtyři studenti, pak jsou v jistém budoucím okamžiku čtyři z nich "vytlačeni", každý na jeden ze čtyř sousedních panelů. Zvýšení počtu studentů na sousedním poli pak může spustit další "vytlačování", atd. Předpokládejte ideálně, že dlážděné nádvoří je neomezeně velké a studenti nejsou u jeho krajů, neboli nikdy nedojde k vytlačení studenta mimo nádvoří. Výše je uveden příklad části procesu vytlačování, ukazující jistých prvních sedm kroků od počátečního stavu s 32 studenty na jednom panelu.

Ještě jeden detail akce vyžaduje bližší vysvětlení -- ve který okamžik totiž dochází k "vytlačení" studentů ze sledovaného panelu (kde je jich více než 4): Vždy v jeden okamžik dochází k "vytlačení" pouze z jednoho panelu ze všech. Panel k příštímu "vytlačení" je pak zvolen, zhruba řečeno, náhodně ze všech "přelidněných" panelů. Formálně je tato volba příštího panelu nedeterministická - je nutno zvažovat všechny možnosti volby, jak pro ně proces dopadne.

Vašim zadáním je řešit následující dva úkoly (nebo alespoň jeden z nich):

• Dokažte, že pro každé počáteční rozestavení konečného počtu studentů na nádvoří popsaný proces "vytlačování" vždy skončí v konečném počtu kroků (kdy na každém panelu zůstane nejvýše po čtyřech studentech).
• Dokažte, že ať probíhá "vytlačování" z přelidněných panelů v jakémkoliv pořadí, tak budou ve finálním výsledku počty studentů stojících na jednotlivých panelech vždy stejné. Neboli výsledné počty studentů nezávisí na nedeterministické volbě pořadí panelů k "vytlačování".

Vaše řešení musí být sepsáno formou přesného a korektního matematického důkazu. Jelikož v zadání nejsou "otevřené úkoly", u kterých by se daly hodnotit různé stupně splnění, základním porovnávacím kritériem pro rozhodnutí o udělení bonusových bodů bude elegantnost a délka (krátkost) vašeho důkazu. Proto se snažte napsat důkazy co nejhezčí a přitom ne dlouhé.

Obecné poznámky

S upřesňujícími dotazy se obracejte na cvičící v diskuzi na IS.
Nezapomínejte, že se jedná o vaši vlastní tvůrčí práci! Při opodstatněném podezření z opisování vám nebudou uděleny žádné body. (Respektive z každé třídy příliš podobně vypadajících řešení bude kladně ohodnoceno jen to, které bylo odevzdáno první. V extrémních případech můžeme sáhnout k záporným prémiím a nebo dokonce pak může být přijímání veškerých řešení předčasně zastaveno.) Také nebudou hodnocena řešení, které nevyhoví zde uvedeným formálním specifikacím.

Ve správně zpracovaném projektu očekáváme, že nejprve teoreticky analyzujete problém; poté popíšete slovně postup / algoritmus, který použijete na jeho řešení, a nakonec shrnete všechny dosažené výsledky. Při "počítačovém" řešení algoritmy popisujte podle formálních zásad zavedených v první lekci a také co nejlépe zdůvodněte jejich správnost. Jako příloha (v tomtéž PDF souboru) musí být zahrnut výpis vašeho programového kódu s komentáři, pro naši kontrolu (ten ale nenahrazuje výše zmíněný popis algoritmu!). Na programovacím jazyku nezáleží. Přiložte jen ten "výkonný" kód, nezajímají nás hlavičky knihoven ani vstupně/výstupní operace. Při teoretickém řešení zase formálně sepište použitá tvrzení a všechna vaše nová tvrzení korektně dokažte.

Důležitá poznámka se také týká využívání cizích zdrojů. Ne, nemáme nic proti tomu, když si pomůcky pro řešení projektu vyhledáte v literatuře či nejspíše přímo na internetu. V praxi přece také nebudete všechno řešit sami od začátku, ale s výhodou využijete již nalezené poznatky, takže učit se vyhledávat potřebné informace je také součástí výuky. Je však vždy nutné úplně citovat všechny zdroje, ze kterých jste čerpali poznatky (nejlépe formou funkčního www odkazu). Takže na toto myslete, neboť zatajení citací je víc než dostatečným důvodem k zamítnutí vašeho řešení. A rozhodně neoceníme, pokud si pod "využíváním cizích zdrojů" představíte prosté opsání programu řešícího projekt, třeba od spolužáka. Vaše řešení projektu by mělo být skutečnou "nadstavbou" nad obecně dobře známými poznatky.

Mnoho zdaru a zábavy!