Úlohový okruh 2

  Poselství Franka Drake-a nepozemšťanům poprvé odeslané v roce 1974 z radioteleskopu v Portorickém Arecibu si postupně vydobylo jistou proslulost[citation needed] tím, že dosud žádný pozemský znalec ani laik, kterému byla tato zpráva předložena ve svém bitovém zakódování a který ji dopředu neznal, nedokázal zprávu dekódovat.

Můžeme tedy zkusit podobný systém.

Výchozí společná situace

Máme posloupnost znaků 0 a 1 určité délky L. Budeme ji říkat kód zprávy. Zprávu máme rozdělit na úseky stejné délky W (kromě posledního, jenž může být kratší), těm budeme říkat řádky, a napsat je zarovnané pod sebe neproporcionálním fontem, címž vznikne textový obdélník, kterému budeme říkat zpráva. Pokud poslední řádek obdélníku vyjde kratší, doplníme ho uměle přidanými nulami.

Vzor úlohy

Máme určit, jak volit délku řádku W, případně najít všechny možnosti volby W, aby ve zprávě byly splněny určité podmínky, které většina obyvatel Mlečné dráhy v mezihvězdné komunikaci automaticky předpokládá. Podle volby podmínek vznikne úloha.

Podmínky vedoucí na jednotlivé úlohy

1. Žádné dvě jedničky nesmí ve zprávě sousedit, uvažujme A) 4-okolí, B) 8-okolí.

2. Ve zprávě neexistuje separovaná jednička obklopená pouze nulami.

3. Každý sloupec zprávy musí obsahovat alespoň K1 a nejvýše K2 jedniček.

4. Zpráva obsahuje alespoň/nejvýše/právě K1 nulových řádků a alespoň/nejvýše/právě K2 nulových sloupců.

5. Jedničky musí tvořit jedinou souvislou oblast A) bez děr, B) s možnými dírami.

6. Zpráva se zkládá pouze z obdélníků tvořených jedničkami a oddělených nulami. A) Stejně velkých. B) Různě velkých.

7. Každý řádek/sloupec je/není palindrom.

8. Zpráva rotovaná o 180° splývá sama se sebou.

9. Každý řádek/sloupec zprávy má na začátku/konci K nul.

10. Žádný řádek/sloupec se ve zprávě neopakuje.

11. Každý řádek/sloupec v binárním kódu představuje prvočíslo.

12. Počty jedniček v řádcích/sloupcích tvoří neklesající posloupnost.

13. Zpráva obsahuje oblast jedniček, do níž lze vepsat obdélník s velkým obsahem (alespoň P).

14. Bounding box obsahující všechny jedničky je co nejmenší možný co se obvodu/obsahu týče.


Úlohový okruh 1

Lze uvažovat u určitém prostředí, o nějakých okolnostech, ve kterých relativně přirozeně vznikají úlohy. Níže je mírně rozvinut jeden takový snadný příklad. V podstatě jde o jakousi obdobu deskové hry, Monopoly, Osadnící z Katánu, apod., viz jejich seznamy např. zde a zde. Důležitý je větší počet účastnících se agentů, který prostředí dodává jistý spád a nádech osobního dramatu.

V pravoúhlé síti se pohybují robůtky.

1. Každý robůtek má svou barvu a pouze na políčku označeném kolečkem se svou barvou se může otáčet na libovolnou stranu.
2. Přes políčka označená křížkem jeho barvy robůtek nesmí přecházet.
3. Jinak se robůtek může pohybovat jen rovně horizontálně nebo vertikálně.
4. Na políčkách můžou být uloženy také předměty.
5. Přesun na sousední políčko trvá vždy jeden takt, na každém políčku lze i neomezeně čekat.
6. Na začátku si robůtek vybere směr svého pohybu.

Úloha 1.

Robůtek je vlevo nahoře, zde i dále vidíme možný příklad vstupu úlohy.

Která políčka jsou pro robůtka nepřístupná?
Kolik jich je přístupných tak, že se z nich může vrátit na výchozí pozici?
Rozvinutí: Za jak dlouho může obejít všechna jemu dostupná políčka a vrátit se zpět?


Úloha 2.

Mohou se oba robůtky na některém políčku potkat? Na kolika a kterých?
Rozvinutí: Za jakou nejkratší dobu se mohou potkat?


Úloha 3.

Mohou oba robůtky sebrat všechny hvězdičkové objekty?
Rozvinutí: Za jakou nejkratší dobu tak mohou učinit?
Rozvinutí: Předpokládejme, že robůtek unese jen jeden objekt a všechny objekty je nutno odnést na výchozí pozici některého z robůtků. Jak rychle to lze stihnout?
Rozvinutí: Objektíky mohou být různé, je třeba z nich poskládat nový robůtek.


Úlohy další

Úloha se mění, když přibydou některé specifikace:
A. Robůtky mají udělat nějakou činnost, nesmí se však k sobě přiblížit na vzdálenost menší než D.
B. Lze navíc odstranit či ponechat možnost čekání na políčku.
C. Lze omezit počet návštěv některých políček.
D. Robůtek má pohon jen na určitý počet kroků.
E. Robůtek může být poškozený a moci pouze zatáčet vždy jen o 90° jedním směrem.

etc.


Přechod ke grafům

Ve všem dosud uvedeném lze nahradit šachovnicovou síť obecným grafem, v uzlech definovat pravidla průchodu a odbočování.
Opět, vzniká značné množství dalších podnětů, např., když se dále omezíme jen na jisté typy grafů, třeba stromy.


Přechod ke stategickým hrám

Necháme robůtky provozovat své tahy na střidačku a dáme jim antagonistické cíle.
Jeden má dohonit druhého.
Mají si vyměnit místa a nepřiblížit se k sobě příliš a podobně.

courses/a4b36acm2/2013_zs/pro_kaju.txt · Last modified: 2018/10/03 03:51 (external edit)