Základní informace

Letošní kvalifikační úloha z logiky je zaměřena na prozkoumávání dvourozměrných celulárních automatů. Typickým příkladem takového automatu je Game of Life. Kvalifikační úloha se skládá z několika menších úloh, celkový počet získaných bodů se počítá jako součet bodů za dílčí podúlohy. Úlohy můžete řešit v libovolném pořadí, avšak doporučujeme postupovat v pořadí, ve kterém jsou na webu (od jednodušších ke složitějším).

Úlohy jsou různých typů a obtížností. V každé úloze budete pracovat:

• s dvourozměrnou mřížkou složenou z buněk, každá buňka může mít právě jednu barvu (červená, zelená, modrá, šedá);
• s pravidlem, které určuje, jak se vytváří nové generace mřížky.

Příklad pravidla: “když mám alespoň 3 zelené sousedy a jsem zelená, zůstávám zelená, jinak se stávám šedou”. Toto pravidlo se použije na každou buňku v mřížce a vznikne nová mřížka – nová generace. Pravidlo platí pro všechny buňky v mřížce stejně a uplatňuje se zároveň.

Naše prostředí se v mnohých faktorech od klasického Game of Life liší. V jednotlivých úlohách se setkáte s různými pravidly, počty barev, počátečními stavy atp.

Úlohy jsou rozděleny do tří kategorií:

1. V první kategorii budete znát pravidlo, podle kterého simulace funguje. Vaším úkolem bude správně rozmístit buňky do mřížky tak, abyste splnili zadání.
2. U druhé kategorie budete pravidlo sami tvořit a zapisovat, a to na základě zadání a testování v přiložené simulaci.
3. V poslední kategorii bude vaším úkolem ukázat, že za daného pravidla nelze vytvořit námi zadanou konfiguraci.

Maximální bodový zisk jednotlivých úloh je různý v závislosti na jejich náročnosti. Co přesně se u jednotlivých úloh hodnotí je popsáno u každé úlohy zvlášť. Skóre uvedené u odevzdaných úloh je jen orientační a bude později systémem přepočítáno na výsledný bodový zisk. Jeho význam závisí na úloze (např. počet obarvených buněk v nejvyšším řádku). Svá dílčí řešení (popis pravidla, počáteční konfigurace) odevzdáváte přímo do jednotlivých úloh, slovní popis řešení pro úlohy, které ho vyžadují, odevzdejte v jednom dokumentu pro všechny části společně do odevzdávárny N-trophy webu. Svá řešení pište výstižně, stručně, ale na nic nezapomeňte. Body dostanete za logickou argumentaci, nikoliv za omáčku okolo.

Zde na webu naleznete cvičný simulátor (tzv. klikátko), ve kterém si můžete zkoušet, jak simulace funguje pro různá pravidla a konfigurace, a detailní popis, jak funguje simulace a jakým způsobem se zapisují pravidla.

Všechny úlohy jsou otevřené po celou dobu kvalifikace. Úlohy je možné odevzávat opakovaně až do vyčerpání limitu počtu odevzdání. Počítá se nejlepší odevzdání.

Tato úloha má web proto, aby vám usnadnila studium celulárních automatů. Web není určen k tomu, abyste řešení úloh zjistili crackováním. Při řešení úloh se řidťe zásadou fair play. Kdybyste narazili na libovolný problém, ozvěte se na logika@ntrophy.cz.