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: Plán hodiny (k použití přímo ve výuce), TODO: [[[: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)

V této hodině se žáci seznámí s jedním z užitečných modelů k řešení problémů. Zároveň je to model k nahlížení na realitu, byť jen v jednoduchých a omezených případech. Žáci využijí grafy a další předchozí znalosti a zkušenosti. Rozvíjejí citlivost k systematickým postupům, vidí jejich zápory (práce navíc, zejm. u jednoduchých problémů) ale i klady (možnost o řešení definitvně rozhodnout, nikoliv jen tušit na základě nahodilých pokusů). Kromě toho jsou stavové prostory přípravou na pokročilejší oblasti. Žáci vidí (zatím nikoliv na vlastní kůži), že velikost problému může způsobit, že bude prakticky neřešitelný - i když třeba řešení existuje a způsob jeho hledání známe.

TODO: na tohle pak navazuje... prostor část. řešení, procházení, limity podrobněji

Samotný průběh hodiny není ničím neobvyklý, žáci prostřednictvím řešení úloh poznávají a procvičují práci se stavovými prostory.


Jako první žáci řeší úlohu o převozníkovi, neboli o vlku, koze a zelí. Někteří mohou mít potíže způsobené zejm. tím, že je v v průběhu převážení potřeba zhoršit již dosaženého výsledku a jedno zvíře poslat zpět. V každém případě je pro ně ale úloha poměrně nepřehledná.

Pro porovnání jim učitel ukáže odpovídající stavový prostor. Na něm je vidět, že záleží na znázornění a problém se může stát velmi snadným. Učitel v několika větách vysvětlí potřebné souvislosti a předvede postupné sestavování stavového prostoru. Řešení problémů se tak mění na sestavení "bludiště" a prosté hledání cesty v něm.

Dále žáci řeší cvičné úlohy a všímaji si dalších detailů: jak záleží na tom, co vše do modelovaných stavů (ne)zahrnou, na přehledném uspořádání stavů a přechodů, na velikosti stavového prostoru (počtu stavů).

Na závěr učitel pro úplnost doplní některá úskalí použití stavových prostorů.

Další poznámky

  • Žáci mohou podle vlastního uvážení použít počítač a nějaký edior (např. LucidChart). Nevýhodou ve srovnání s tužkou a papírem je určitá těžkopádnost, výhodou usnadnění úprav a přeuspořádání.
  • Nepominutelným krokem k řešení je vhodné kódování stavů, i tomu je potřeba věnovat pozornost. I před tím, než se seznámí se stavovým prostorem, mají žáci přirozenou snahu úsporně zaznamenávat postup řešení, což často ke stručnému zakódování stavů vede.
  • Rychlejší žáci mohou řešit další úlohy, náměty jsou uvedeny níže. Nemusí přitom zůstat pouze u nalezení samotného řešení, mohou se věnovat i pokročilejším otázkám:
    • Jak velký přibližně je stavový prostor dané úlohy?
    • Jak stavy přehledně uspořádat?
    • Kolik různých řešení existuje? Našli všechna?
    • Našli řešení v nějakém ohledu nejlepší?
    • Jak při samotné konstrukci (zejm. většího) SP postupovat sytematicky, nic nevynechat?
ikona boxu
Úloha: Další úlohy

Poháry 2
Na stole stojí pět pohárů, jeden je překlopený. V jednom kroku se smí otočit vždy přesně 2 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?


Přesýpací hodiny
Máte 2 přesýpací hodiny – jedny sedmiminutové, jedny čtyřminutové.
Jak s jejich pomocí změřit přesně 9 minut?


Přesýpací hodiny 2
Máte 2 přesýpací hodiny – jedny sedmiminutové, jedny jedenáctiminutové.
Jak s jejich pomocí změřit přesně 15 minut?


Šňůry
Máme zapalovač a dva provazy. Každý z nich hoří půl hodiny, jenže nerovnoměrně (některé úseky hoří pomaleji, některé rychleji).
Jak odměřit tři čtvrtě hodiny?


Delší šňůry
Máme zapalovač a dva provazy. Každý z nich hoří jednu hodinu, jenže nerovnoměrně (některé úseky hoří pomaleji, některé rychleji).
Jak odměřit čtvrt hodiny?


Odměřování tekutin 49-6
Potřebujeme naměřit přesně 6 litrů vody, jenže máme jen dvě nádoby, o objemu 4 a 9 litrů. Jak postupovat?


Odměřování tekutin 45-2
Potřebujeme naměřit přesně 2 litry vody, jenže máme jen dvě nádoby, o objemu 4 a 5 litrů. Jak postupovat?


Odměřování tekutin 34-2
Potřebujeme naměřit přesně 2 litry vody, jenže máme jen dvě nádoby, o objemu 3 a 4 litry. Jak postupovat?


Odměřování tekutin 743-223
7, 4 a 3-litrová nádoba, 7 litrů vody v největší nádobě. Rozděl vodu na 2, 2 a 3 litry.


Odměřování tekutin 2073-15
20, 7 a 3-litrová nádoba, 20 litrů vody v největší nádobě. Odměř 15 litrů, nic nesmíš vylít.


Rodinka na výletě
Rodiče a dvě děti se potřebují dostat přes řeku. Všimnou si rybáře, který souhlasí, že jim půjčí svou lodičku. Lodička je ovšem malá, pojme buď jednoho dospělého, nebo dvě děti.
Jak se rodina dostane na druhý břeh a vrátí lodičku?


Rodinka v tunelu
Tatínek, maminka, syn a dcera potřebují projít tunelem. Tatínek projde tunelem za jednu minutu, maminka za dvě, syn za čtyři a dcera za pět. Jenže v tunelu je tma a oni nemají moc svíček nazbyt. Bez svíčky se ovšem do tunelu nedá, a i se svíčkou mohou projít nanejvýš dva lidé.
Jak zorganizovat průchod tunelem tak, aby spotřebovali co nejméně svíčky?

Váhy a závaží

TODO: přidej do úloh: Žabky

Ú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 (klepněte na rozbalovací tlačítko).

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

Jednoduché bludiště.svg

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.

Stavový prostor pro vlka, kozu a zelí, včetně označení stavů.

SP VKZ.svg

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 nebo otáčení pohárů. 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

Přelívání vody a uspořádání stavového prostoru

ikona boxu
Úloha:

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

Samotné řešení už by pro vás mělo být jednoduché. Ne každému se ale lehce hledalo mezi již zaznamenanými stavy (aby jeden stav nezaznamenali vícekrát). K tomu pomůže si stavy v nakresleném stavovém prostoru nějak systematicky uspořádat. V případě přelívání je stav definován objemem vody ve dvou nádobách, tedy dvěma celými čísly v rozsahu 0—5 a 0—3. Dvojice seřazených hodnot uspořádat umíme! TODO: přepracuj, aby na to přišli sami?Vzpomeňte si na šachovnici, tabulkový kalkulátor nebo na kreslení a vůbec pohyb ve Scratchi. Na dvojice hodnot se můžeme dívat jako na souřadnice.

Počáteční stav, kdy jsou obě nádoby prázdné (obsahují 0 litrů vody), umístíme do počátku (souřadnice [0,0]). Čtyři litry se vejdou jen do pětilitrové nádoby, takže konečné stavy budou (zakreslené na souřadnicích) [4,0], [4,1], [4,2], [4,3] (obsah druhé nádoby není pro splnění úkolu důležitý).

Stavy uspořádané podle souřadnic.

SP Přelívání.svg

TODO: zapracuj další uspořádání: u vlkozy stačilo jít cca časově, obecně to bude n-rozměrné podle každé proměnné, takže jaké jsou ještě možnosti? Sanžit se to uspořádat do roviny, kde je pak přehlednější postup, ale hůř se hledá stav? ha! trade-off!

Otazník
Zamysli se a odpověz:

Jak uspořádat stavové prostory v předchozích úlohách?

Velikost stavového prostoru

TODO: tohle celé pak posunout na později do nějaké závěrečné diskuze (tedy ne počítání, ale ten důvod) Důležitým kritériem pro rozhodnutí, jestli k řešení problémů využít stavové prostory, je jejich velikost. POkud je stavový prostor příliš velký, může nám jeho prohledávání trvat příliš dlouho. Uvedené problémy jsou cvičné, ve skutečném světě se snadno setkáme s případy, kdy lze z každého stavu pokračovat třeba do osmi nových stavů a řešení vyžaduje desítky takových kroků.

Příklad: Velký stavový prostor

Celkem bychom tak dostali např. 850 stavů, což je (23)50 = 2150 stavů. Když víme, že 210 je o něco více než 103, máme přibližně 215*10 ≈ 1015*3 = 1045 stavů. Kdybychom každý z nich zkontrolovali během jediného tiku gigahertzového procesoru, který tedy tikne miliardkrát (109) za sekundu, potřebovali bychom 1045-9 = 1036 sekund. I kdybychom s tím začali na počátku samotného vesmíru, zdaleka bychom ještě nebyli hotovi. Museli bychom pokračovat ještě trilionkrát déle. I kdybychom použili všechny počítače na světě, výsledku bychom se nedožili.

Nechceme-li se zaplést do nezvládnutelného úkolu, vynasnažíme se počet stavů odhadnout předem.

Pro začátek si ukážeme dvě jednoduchá pravidla.

  1. Pokud lze prostor rozdělit na několik částí, může být výhodné odhadnout velikost každé části a odhady následně sečíst.
  2. Pokud je stav dán hodnotami několika proměnných se známým rozsahem, odhadneme celkový počet stavů součinem velikostí těchto rozsahů.

Příklad: Počet stavů při přelívání nádob

Máme nádoby, které plníme po celých litrech v rozsahu 0—3 a 0—5. Třílitrová nádoba se tedy může nacházet nanejvýš ve čtyřech různých stavech, pětilitrová v šesti.

Celkem tedy jistě neexistuje více než 4*6 = 24 různých stavů naplnění nádob. Nezapomeňte, že se jedná o horní odhad. Nikde není dáno, že bude všech 24 stavů opravdu dosažitelných. Určitě jich ale nebude víc.

TODO: tady je třeba něco udělat

Shrnutí

ikona boxu
  • Některé problémy můžeme modelovat pomocí stavových prostorů. Ty zachycují různé stavy, do kterých se při řešení problému můžeme dostat, a přechody mezi nimi.
  • Ve stavovém prostoru se nebudeme točit v kruzích a zároveň žádný možný postup neopomeneme. Díky tomu můžeme např. rozhodnout, které řešení vyžaduje nejméně kroků, nebo např že žádné neexistuje.
  • Nehledě na to, o čem vlastně konkrétní problém je, postupujeme pokaždé stejně:
  1. Rozhodneme, čím přesně je definován stav, a jak to zaznamenávat. Přitom se snažíme pracovat právě jen s tím, co potřebujeme k vyřešení úlohy.
  2. Popíšeme výchozí a cílový stav.
  3. Postupně podle charakteru daného problému přidáváme do prostoru další stavy a jejich vzájemná propojení.
  4. Nakonec buď narazíme na řešení (cílový stav), nebo zjistíme, že jsme vyzkoušeli všechny možnosti, do cíle nedošli, a řešení tedy neexistuje.
  • Využití stavových prostorů k řešení problémů má své meze. Například může být stavový prostor nezvládnutelně velký (když je stavů příliš mnoho).