Odkazy na kapitoly k ověřování najdete na úvodní stránce. Tyto vzdělávací materiály jsou alfa verzí určenou k ověřování ve školním roce 2018/2019 v rámci projektu CZ.02.3.68/0.0/0.0/16_036/0005322 Podpora rozvíjení informatického myšlení.


Projdi bludiště, zachráníš kozu

Z Informatika pro každého
Přejít na: navigace, hledání

TODO: doplnit chapnav, xx chapnav

Úvod
ikona boxu
Co se naučíš:
  • orientovat se v nakresleném stavovém prostoru
  • sestrojit stavový prostor a najít v něm řešení problému

TODO: bude toho víc: meze, atd., popř. až u toho procházení?

ikona boxu
Obvyklý průběh hodiny a metodické poznámky


Informace v tomto boxu lze zobrazit samostatně (např. pro tisk).

Související materiály: [[[:Archiv:Učebnice/Modely/Projdi bludiště, zachráníš kozu/Hodina/PRIM-UL]] Plán hodiny] (k použití přímo ve výuce), TODO: [[[:Archiv:Učebnice/Modely/Projdi bludiště, zachráníš kozu/Hodina/PRIM-PL]] Pracovní list pro studenty] ------------- vkládat podmínečně, jen pokud PL existuje TODO: vytvořený v rámci projektu PRIM. --- doplň odkaz na PRIM, vkládej jako šablonu, aby se vložil externí odkaz

TODO: RVP TODO: Používá systémový přístup k řešení problému, Pro řešení problému sestaví model, algoritmizace (strategie)

Rozho v další výuce. Jde také o přípravu ke grafům a ke kódování.

Obecný "vzorec" je zase obdobou předchozích. Předložíme úlohy, k jejichž řešení se hodí využít nějaký informatický koncept. Žáci se s tím nějak perou, podle možností objeví buď to, co "potřebujeme", nebo si aspoň problém osahají natolik, aby byli schopni ten koncept pochopit a ocenit. Uspořádání práce (samostatná, ve dvojicích, skupinová), je plně v kompetenci učitele.



Žáci řeší vlastními silami a vyřeší to nejspíš graficky pomocí nákresů či stavů, které mohou nastat (aniž by tušili cokoliv o stavovém prostoru). Cílem je vyřešit, opět tak, abych uměl řešení přesvědčivě vysvětlit ostatním (pomocí grafu). U těchto úloh to mj. vede na snahu nějak symbolicky zapsat jednotlivé kroky (raději než slovně), což můžeme brát jako "předstupeň" stavového prostoru. Kdo je nějak moc napřed, dostane těžší zadání, např. ukázat, že jeho řešení je nejlepší, nebo najít řešení všechna.

Úvodní úloha

Zkuste vyřešit následující úlohu. Všímejte si, kdy řešíte metodou pokus-omyl, a kdy postupujete systematicky. TODO: doplň všude nápovědy a řešení TODO: BonusBox odhadněte čas, sledujte, a totéž u bludiště...

ikona boxu
Úloha:

Vracíte se domů jako každý den, se svým vlkem, kozou a obrovskou hlávkou zelí. Jenže u přívozu není převozník, který vás jinak vždy postupně převeze. Musíte se přes řeku převézt sami. Na přívoz se vejde člověk a pak už jen jeden kus nákladu. Přitom ale nikdy nesmí bez dozoru zůstat vlk a koza, ani koza a zelí.

Jak převážení zorganizovat, aniž by došlo k nějaké úhoně?

Bylo to těžké? A umíte navíc ukázat, že je váš postup řešení nejlepší, a jestli existují nějaké další? Případně, pokud řešení neexistuje, umíte ukázat proč? "Zkoušel jsem to opravdu dlouho" žádného informatika jako důvod nepřesvědčí.

Bludiště

ikona boxu
Úloha:

Najděte cestu mezi zelenými políčky v následujícím bludišti.

Jednoduché bludiště.svg

Najdete v bludišti cestu mezi dvěma zelenými poli?

TODO: nahraj obrázek bludiště

Najít cestu v bludišti se zdá mnohem jednodušší, než vyřešit úlohu s převážením. Ukážeme si ale, že je to totéž.

Podívejte se na bludiště s doplněnými popisky.

SP VKZ.svg

N?

Obtížnost úlohy s převážením spočívá ponejvíce v udržení přehledu o tom, co už jsme zkoušeli (netočit se v kruzích) a nevynechání žádné možnosti, která by mohla vést k cíli.

Prvním krokem k tomu, abychom tyhle nepříjemnosti odstranili, je začít sledovat, co už jsme vyzkoušeli. Abychom si mohli zaznamenat stav, vek terém se zrovna nacházíme, muslíme nejprve rozmyslet, čím vším je stav určen. V případě úlohy o převážení je jasné, že nás zajímá, na které straně řeky se nacházejí vlk, koza a zelí. Nesmíme ale zapomenout také na polohu lodičky (i s "převozníkem"). Tomu odpovídají označení jednotlivých stavů na obrázku výše. Svislá čára symbolizuje řeku a tím značí, na které straně se co nachází. Písmena jsou podtržená na té straně, na které je v daném stavu lodička. Chceme se tedy dopracovat ze stavu zakódovaného jako VLK| do stavu |VLK.

Stanovené označování stavů nám umožní vypisovat, kterých stavů jsme již dosáhli, a kontrolovat, abychom nezkoušeli totéž stále dokola. Nezjistíme ale, jestli jsme žádnou možnost nevynechali. Proto jednotlivé stavy propojíme podle toho, jak mezi nimi lze přecházet. Pak můžeme mnohem snáz zkontrolovat, jestli jsme v každém stavu vyzkoušeli všechny možnosti.

Ve výsledném diagramu potom už poměrně snadno najdeme cestu z výchozího do cílového stavu (nebo zjistíme, že taková cesta neexistuje). Všimněte si, že v tu chvíli už nijak nezáleží na tom, jestli se jedná o kozy v řece nabo otáčení sklenic. Hledáme prostě cestu grafem, stejně jako třeba GPS navigace v autě.

TODO: tady je třeba něco udělat TODO: bonus box: proč se to jmenuje prostor? no dá se v tom chodit, má smysl v topm měřit vzdálenost mezi "body"...

Poháry

ikona boxu
Úloha: Otáčení pohárů

Na stole stojí pět pohárů, prostřední je překlopený dnem vzhůru. V jednom kroku se smí otočit vždy přesně 3 poháry: stojící se překlopí, překlopené se postaví.

Jak poháry otáčet, aby nakonec všechny poháry stály? TODO: obrazek s peti pohary, prostrednim preklopenym TODO: bonus:argument přes sudé/liché

ikona boxu
Nápověda

Postupuj podle kroků z předchozího popisu:

  1. Rozhodni, čím přesně je definován stav, a jak to zaznamenávat.
  2. Popiš výchozí stav.
  3. Popiš cílový stav.
  4. Postupně podle pravidel (otáčení tří pohárů) vytvářej další stavy a propojuj je do stavového prostoru, dokud se nedopracuješ do cílového stavu, nebo nevyčerpáš možnosti.

TODO: doplnit řešení

Řešení

Všimni si, že není důležité, které poháry jsou jak otočené. Záleží jen na jejich celkových počtech. bonusová otázka: kolik bychom tedy měli stavů? (32 vs. 6, když chytře modelujeme) mám připravený obrázek ve složce



ikona boxu
Úloha:

Potřebujeme naměřit přesně 4 litry vody, jenže máme jen dvě nádoby, o objemu 3 a 5 litrů. Jak postupovat?

ikona boxu
Úloha:

Na stole stojí pět pohárů, jeden je překlopený. V jednom kroku se smí otočit vždy přesně 3 poháry: stojící se překlopí, překlopené se postaví.

Kolik nejméně kroků je potřeba, aby všechny poháry stály?