Differences

This shows you the differences between two versions of the page.

Link to this comparison view

courses:a4b36acm1:2013_zs:pro_kaju [2018/10/03 03:51] (current)
Line 1: Line 1:
 +=== Úlohový okruh 2 ===
 +{{ :​internal:​arecibo0.jpg?​nolink&​100| }}
 +{{ :​courses:​a4b36acm:​2013_zs:​arecibo0.jpg?​100| }}
 +Poselství Franka Drake-a nepozemšťanům poprvé [[http://​cs.wikipedia.org/​wiki/​Zpr%C3%A1va_z_Areciba|odeslané v roce 1974]] ​ z radioteleskopu v Portorickém Arecibu si postupně vydobylo jistou proslulost<​sup>​[citation needed]</​sup>​ 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ř. [[http://​www.listchallenges.com/​92-best-board-games-of-all-time|zde]] a [[http://​en.wikipedia.org/​wiki/​List_of_board_games|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.\\
 +
 +{{:​courses:​a4b36acm:​2013_zs:​robots1.jpg?​300|}} ​    
 +
 +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. ===
 +{{:​courses:​a4b36acm:​2013_zs:​robots2.jpg?​300|}} ​
 +
 +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. ===
 +{{:​courses:​a4b36acm:​2013_zs:​robots3.jpg?​300|}}
 +
 +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/a4b36acm1/2013_zs/pro_kaju.txt · Last modified: 2018/10/03 03:51 (external edit)