CourseWare Wiki
Switch Term
Summer 2023 / 2024
Winter 2023 / 2024
Summer 2021 / 2022
Winter 2021 / 2022
Summer 2020 / 2021
Winter 2020 / 2021
Summer 2019 / 2020
Winter 2019 / 2020
Summer 2018 / 2019
Winter 2018 / 2019
Summer 2017 / 2018
Search
Log In
b232
courses
a4b36acm1
2013_zs
pro_kaju
Differences
This shows you the differences between two versions of the page.
View differences:
Side by Side
Inline
Go
Link to this comparison view
Go
Go
courses:a4b36acm1:2013_zs:pro_kaju [2018/10/03 03:51]
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)