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í.


Rozhodovací stromy a chytré otázky

Z Informatika pro každého
Přejít na: navigace, hledání
Co jsem za zvíře? · Měření stromů a informací
ikona boxu
Co se naučíš:
  • zachytit průběh rozhodování pomocí rozhodovacího stromu
  • rozhodovat se podle daného stromu
  • spočítat nejnižší a nejvyšší počet otázek podle daného stromu
  • nakreslit co nejlepší strom pro daný problém (a počet možností)
  • porovnat očekávaný informační přínos daných otázek
  • vědět, čím se vyznačuje dobrá otázka, zformulovat ji pro danou situaci
  • používat metodu půlení intervalů pro určení čísla z daného rozsahu
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/Informace/Rozhodovací stromy a chytré otázky/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)

Rozhodovací strom znázorňuje celý rozhodovací proces a všechny alternativy najednou. To usnadní popis strategií, stejně jako další práci s nimi. Je totiž nejvyšší čas začít rozhodovací strategie porovnávat a kvantifikovat. Díky stromům je vidět, které strategie (popř. konkrétní otázky) jsou jak užitečné (kolik přináší informace, resp. kolik pravděpodobně ponechávají otázek). Postupně se vyjasňuje vztah mezi počtem otázek a počtem možností (hlouběji se mu věnujeme v následující hodině). Ukáže se také, že je rozdíl mezi nejlepším, průměrným a nejhorším případem. Stejně tak lze pomocí stromů snáze ukázat, že nás v naší situaci zajímá především případ průměrný, při opakovaném hraní.

Spojením dosavadních poznatků o hře, o povaze získávaných informací a o stromech (aspoň někteří) studenti dojdou k tomu, jak by měl vypadat optimální rozhodovací strom, optimální otázka nebo optimální strategie (v libovolném pořadí). Naším úkolem je nechat je poznatky precizně formulovat, doplnit případné mezery a závěry strukturovat. Vzhledem k pečlivé přípravě se studenti, kteří ke správným závěrům nedošli sami, plácnou do čela a okamžitě je pochopí. Přesto je na místě, aby si každý na konci hodiny metodu půlení intervalů vyzkoušel.

Rozhodovací strom je zároveň příkladem zápisu algoritmu (blízký vývojovým diagramům) a modelem procesu rozhodování, budeme se o něj jako o příklad opírat v další výuce. Jde také o přípravu ke grafům a ke kódování.


Navazujeme na hry se zjišťováním zvířat a čísel a jejich prvotní rozbory. Studenti zjistili, že dobře popsat svoje rozhodovací strategie není vzhledem k počtu větvení vůbec jednoduchý úkol. Seznámíme je proto s rozhodovacími stromy jako se zápisem rozhodovací stragegie.

Práce s rozhodovacími stromy je velmi intuitivní a pochopit vše potřebné nezabere studentům mnoho času. Cvičně si sestaví strom na svoje téma (nedostanou-li lepší nápad, mohou rozlišovat nějaké školní pojmy, třeba chemické prvky). Potom už si sestaví strom podle dotazovací strategie na hádání čísla, kterou zformulovali v předchozí hodině. I ti svéhlaví postupně ocení, když je seznámíme s vhodnějším programem k práci se stromy, než je Malování.

V další fázi se pustíme do hodnocení a tím do hlubší analýzy stromů. Studenti patrně navrhnou různá kritéria: nejméně potřebných otázek, pokud máme štěstí, smůlu, většinou nebo v průměru, složitost položených otázek (na pochopení, nebo na zodpovězení), vzájemná podobnost otázek (strom sleduje nějakou srozumitelnou strategii) atp.

Co se týče počtu pokládaných otázek, na stromech se jasně ukáže, že je třeba rozlišovat nejlepší a nejhorší případ (máme štěstí nebo smůlu). V souladu s předchozím hodnocením strategií nás nejvíce bude zajímat strom, který je optimální v průměru, tedy při mnohokrát opakovaném hraní.

Vhodnými otázkami studentům postupně pomáháme objevit optimální tvar stromu. Na stromech si povšimneme, jak tipování vede k jejich neúměrnému růstu: špatný tip vyloučí jedinou možnost, ke zjištění čísla budeme muset položit téměř stejný počet otázek, jako bez toho tipu. Chceme-li potlačit vliv náhody, sestavíme otázku tak, aby odpověď délku dalšího dotazování vůbec neovlivnila. V každém případě tak dostaneme stejné množství informace. Odpovídá to rozdělení zbývajících možností na poloviny. Takové otázky zároveň vedou ke stromům pěkně souměrným a tzv. vyváženým (všechny větve jsou téměř stejně dlouhé).

Studenti dojdou k tomu, že tedy každá otázka v optimální strategii dělí možnosti na poloviny. V případě čísel to studenti umí dvěma hlavními způsoby: rozdělením v polovině na nižší a vyšší čísla, a rozdělením na sudé a liché. Obojí dává dobrý smysl a lze použít, pro lidi je ale praktičtější první uvedený postup.

Jedno kolo zjišťování čísla půlením intervalů odehrajeme společně, aby postupu všichni porozuměli. Následně si to studenti vyzkouší ve dvojicích.


Další poznámky

  • I zde platí, že uvedený plán hodiny představuje jednu z možností. Studenti mohou uvažovat jiným směrem. V tom jim nebráníme, hodinu můžeme za běhu přizpůsobit. Nakonec beztak dojdou ke stejným výsledkům.

Už víme, že na informaci se můžeme dívat jako na úbytek možností. Zbývá nám tedy „jen“ najít příslušné otázky. Jenže jak určit, kolik ubude možností, když nevíme, jaká přesně přijde odpověď? Navíc bychom rádi našli obecné pravidlo, jaké otázky klást. Uměli bychom se pak ptát v různých situacích a také bychom díky obecnému pravidlu uměli klást otázky za sebou chytře tak, aby nás co nejkratší cestou vedly k cíli.

ikona boxu
Úloha: Podrobnější zkoumání

Podívejte se do svých záznamů a připomeňte si otázky, které jste kladli v průběhu zjišťování myšleného čísla. Vzpomeňte si také, které možnosti ještě u jednotlivých otázek připadaly v úvahu.

Spočtěte pro jednotlivé otázky:

  • Kolik ubude možností v případě odpovědi ANO, kolik v případě NE?
  • Kolikrát ze všech možností lze kterou odpověď očekávat?
  • Kolik možností ubude v příznivém případě, kolik v nepříznivém?
  • Kolik možností ubude v průměruPokud bychom se ve stejné situaci (tj. co už víme, a co je ještě nejisté) vyskytli opakovaně, např. tisíckrát, kolik bychom danou otázkou průměrně vyloučili možností??
  • Čím se vyznačuje dobrá otázka? Co to znamená, že je otázka dobrá? Proč?

Příklad: „Je to 11?“ a „Obsahuje to číslici 1?“

(Hledáme celé číslo z rozsahu 0-15, otázky jsme podrobněji zkoumali už v předchozí části.)

Otázka Odpověď Kolik možností odpověď vyloučí Jak často(při opakovaném hraní) lze odpověď očekávat Kolik otázka průměrně (při opakovaném hraní) vyloučí možností
„Je to 11?“ ANO 15 1/16Přibližně v jedné z šestnácti her (1⋅15 + 15⋅1)/16 V jednom případě vyloučí 15 možností, v patnácti případech vyloučí jedinou možnost, a pro průměr je třeba vydělit počtem všech případů, tedy šestnácti. = 1,875
NE 1 15/16
„Obsahuje to číslici 1?“ ANO 9 7/16 (9⋅7 + 7⋅9)/16 = 7,875
NE 7 9/16
ikona boxu
Další kritéria

Množství získané informace samozřejmě není jediným možným kritériem kvality otázky. Otázka má být srozumitelná a jednoznačná, nemá být zbytečně komplikovaná. Je praktické, když umožňuje snadné kladení dalších dobrých otázek, např. když ji lze jen po mírné úpravě použít i v nových podmínkách.

Příklady otázek

Pokud nemáte dost vlastních otázek:

  • Je myšlené číslo dvouciferné?
  • Je myšlené číslo sudé?
  • Je myšlené číslo prvočíslem?
  • Je na místě jednotek číslice 3?
  • Začíná číslo na písmeno D?
  • těžší otázka: Je ve dvojkovém zápisu čísla číslice 1 na místě čtyřek (tedy na 3. místě zprava)?

Rozhodovací stromy

ikona boxu
Stromy nejsou nutné
Není to obvyklé, ale některé třídy si vystačí počítáním průměrů a zbytek si už odvodí. Rozhodovací stromy tedy nepotřebují pro řešení úlohy a z tohoto hlediska je zbytečné s nimi zdržovat. V průběhu přemýšlení nejspíš stejně padne otázka, která k zavedení stromů přirozeně povede.

Někteří už možná vhodný způsob tušíteDovedete svoje tušení zdůvodnit?, někteří možná ne. Uvažovat současně o mnoha o různých cestách, jimiž se může zjišťování čísla ubírat, není snadné. Pomohou nám rozhodovací stromyPodobná schémata nazýváme stromy proto, že se postupně větví, a větve se nikdy znovu nespojují..

Znázorňují totiž celé dotazování vizuálně, všechny možnosti jsou vidět zároveň. Můžete se setkat s různými variantami, ale základ je vždy stejný:

NahořeSkutečně, informatici kreslí stromy zásadně převrácené. Kořen nahoru, listy dolů. Je to proto, že v kořeni obvykle začíná nějaká práce se stromem, a postup shora dolů je praktičtější. je výchozí uzel, tzv. kořen stromu. Obsahuje první otázku. Podle získané odpovědi pokračujeme po odpovídající hraně do příslušného podstromu a tak dál, až dojdeme ke konečné odpovědi. Ta je zapsaná v tzv. listu, tedy uzlu, ze kterého nevedou další hrany (protože neklade další otázky). Počet úrovní stromu od kořene k nejzazšímu listu nazýváme výškou stromu.

Příklad: Příklad rozhodovacího stromu

Rozhodovaci strom priklad jazyky.svg

Rozhodovací strom pro určení jazyka z psaného textu.

Kolik je nanejvýš potřeba otázek pro určení jazyka podle tohoto stromu? Kolik přinejmenším? S jakými texty nebude fungovat správně? Jak by bylo možné jej vylepšit?

ikona boxu
Mezipředmětové vazby
Rozhodovací strom je skoro totéž co klasifikační strom. Zařazení klasifikačních stromů v dalších předmětech prospěje nejen nám v informatice. Úloha na sestavení klasifikačního stromu pro rovinné útvary, světové jazyky, organismy v biologii atd. přinutí studenty dobře promyslet strukturu daných jevů, a tím prohloubí jejich porozumění

Podle rozhodovacího stromu může rozhodovat takřka kdokoliv — ve srovnání se slovním popisem postupu hrozí menší riziko popletení. Navíc díky stromu hned vidíme:

  • jestli nám někde něco nechybí (Vedou od každé otázky větve se všemi možnými odpověďmi? Najdeme v listech všechny možné výsledky?);
  • jak dlouho trvá hádání kterého čísla (stačí spočítat otázky na cestě od kořene do příslušného listu);
  • při použití stromu jednoduše vidímeZamysli se: jak je to ve stromu vidět?, které možnosti ještě připadají v úvahu, a které už ne.
ikona boxu
Stromy a paralelní vesmíry
Paralelní vesmíry jsou užitečným myšlenkovým nástrojem. Představ si, že se s každým rozhodnutím vesmír rozštěpí, začnou existovat jeho různé varianty. V každé variantě je zrealizováno jedno z možných výsledků rozhodnutí. Každý z těch vesmírů se samozřejmě opět štěpí, s každým dalším rozhodnutím, které v něm probíhá. Takže zatímco ty máš třeba objednaný oběd č. 1, v paralelním vesmíru máš objednanou dvojku. V dalším vesmíru vůbec neexistuješ, protože se rodiče (nebo jejich rodiče...) přeci mohli rozhodnout i jinak. Rozhodnutí probíhá obrovské množství, obrovské množství je tak i (smyšlených) paralelních vesmírů (a navíc se pořád dál větví). Paralelní vesmíry nutí uvažovat o tom, která rozhodnutí jsou skutečně svobodná, co je vskutku nemožnéNeuskutečnilo se to v žádném z vesmírů, a co je naopak nutnéJe to ve všech vesmírech.

Jistou útěchu v životě ti může přinést např. myšlenka, že v některém paralelním vesmíru si v rámci tělocviku právě užívášAle jsi to ještě ty? skok padákem. Motivační může být uvědomění, že jsi to právě ty, kdo si při každém rozhodnutí vybírá, ve kterém z potenciálních vesmírů chceš žít.

Ale proč to sem píšeme: Paralelní vesmíry a jejich větvení si lze představit (tedy až na to množství) právě jako rozhodovací strom.

ikona boxu
Úloha: Strom pro zjišťování čísla

Sestroj rozhodovací strom zachycující tvůj postup zjišťování čísla 0-15.

Stromy můžeš kreslit ručně, nebo použij nějaký program, např.:

  • LucidChart - on-line prostředí pro tvorbu všemožných schémat a diagramů

TODO: §samo/uč: v lucidu lze volit flowchart nebo co, jde to pak skoro samo

  • yEd - online i off-line program pro tvorbu grafů
  • Inkscape - univerzální vektorový grafický editor. Je tedy určen především ke kreslení, méně už na diagramy, ale taky jde použít.

Bitmapové editory jako např. Malování jsou naopak pro vytváření stromů zcela nevhodné a nejspíš by ti jen přidělaly práci.

Konkrétní detaily (tvary různých typů uzlů, styly čar atd.) se mohou lišit. Podstatné je, aby byl strom srozumitelný a jednoznačný. Rozhodovací uzly bývají ve tvaru kosočtverce, větve mívají šipky (a musí být samozřejmě nadepsané). Dobrým zvykem je systematické uspořádání, např. tak, aby byla výsledná rozhodnutí nějak seřazená, nebo tak, aby stejná odpověď šla vždy na stejnou stranu.

ikona boxu
Nápověda

Uvědom si, že první otázka by měla být vždy stejná. Na začátku každé hry jsi ve stejné situaci, nevíš o čísle nic. Není tedy důvod upřednostnit pokaždé jinou otázku. Při sestrojování stromu tedy začni první otázkou své dotazovací strategie, zapiš ji jako kořen stromu.

Od kořene (tedy první otázky) pak povedeš větve s možnými odpověďmi, každá bude končit uzlem s další otázkou a postupně se tak propracuješ ke všem možným výsledkům, uvedeným v listech stromu. TODO: řešení!!

TODO: bonusový úkol? nakresli další stromy: ptaní po cifrách, tipovačka, dvojkové cifry, nějaké násobky třeba

TODO: obrázek - příklad, nebo řešení? - zprvu sbalit

ikona boxu
Úloha: Srovnání stromů, tedy herních strategií

Porovnej svůj strom se stromy spolužáků. Které stormy ukazují lepší strategii? Shodnete se na odpovědi? Jak je na stromu vidět, která dotazovací strategie je lepší?

TODO: příklady

resp pro samouky?! tipovačka půlení po desítkových cifrách ... aby byly nějak rozdílné, a přitom dávaly smysl dej jim různý layout, at je jasné, že na něm nezáleží

Srovnáním různých stromů vedoucích ke stejnému rozhodnutí tedy vidíme, který strom je pro která myšlená čísla efektivnější. Různé strategie se liší v nejnižším i nejvyšším počtu potřebných otázek. Už jsme ale odhalili, že dobří hráči jsou efektivní nezávisle na tom, které číslo zrovna zjišťují. Formulují otázky tak, aby se co nejvíce přiblížili výsledku, i když mají zrovna smůlu. Snaží se totiž dosáhnout co nejnižšího průměrného počtu otázek. Ten je rozhodující, když hrajeme několik her za sebou, a také když chceme maximalizovat naše šance na výhru.

Otazník
Zamysli se a odpověz:

Rozhodni o pravdivosti následujících tvrzení a své rozhodnutí zdůvodni:

Pro libovolný rozhodovací strom platí, že...

...průměrný počet potřebných otázek je vždy vyšší, než nejnižší počet potřebných otázek.
...průměrný počet potřebných otázek není nikdy vyšší, než nejvyšší počet potřebných otázek.
...nejnižší počet potřebných otázek je vždy nižší, než nejvyšší počet potřebných otázek.
...pokud se průměrný počet potřebných otázek shoduje s nejnižším, pak se shoduje i s nejvyšším počtem potřebných otázek.
ikona boxu
Nápověda

Nenech se zmást tím, že jsme v kapitole o rozhodovacích stromech. Jedná se o známé vlastnosti průměru. Pozor na speciální případ: co se stane, když počítám průměr několika stejných hodnot?

Řešení

Ne, ano, ne, ano. TODO: doplň zdůvodnění, asi příkladem, možná i obrázkem


ikona boxu
Úloha: Vylepšení

Jestli chceš, svůj strom vylepši. Jak se pozná, že už to nejde (tedy ne, že to nejde tobě, ale že to není možné)?

ikona boxu
Nápověda
Snaž se přeskupit listy a uzly tak, aby byly listy co nejblíže kořeni.

Optimální rozhodovací strom

TODO: já celou dobu postupně mimovolně přecházím

ze slovníku „zjišťujeme číslo“ do slovníku "chodíme stromem". Připadá mi to srozumitelné a záměrně pašuju do výkladu inf. způsob vyjadřování, ale nevím, jestli to někoho (ty nejztracenější studenty) nemate příliš.

to dej asi do metodiky, a tady si to kontroluj

celkově tedy: hádání-zjišťování-cestování

Nejlepším řešením je pěkně rovnoměrně vystavěný strom. Všimni si, že každá otázka odstraní vždy právě polovinu zbývajících možností. Úbytek možností tak nezávisí na tom, jestli dostaneme odpověď ANO nebo NE. Úspěch ve hře tak nijak nezáleží na tom, jestli máme štěstí, nebo ne.

Rozhodovaci strom optimalni bez otazek.svg

Optimální tvar rozhodovacího stromu.

Počty otázek potřebných k dosažení libovolného listu se téměř neliší. Na obrázku si také můžeme zkontrolovat, že listy není možné ve stromě vměstnat nikam výš a tím hledání zkrátit. Všechna větvení jsou plně využita. Kdybych chtěl k některému číslu dojít dřív, musel bych několik jiných čísel přesunout dál od kořene stromu, a k jejich zjištění by tak bylo potřeba více otázek. Vylepšit situaci jednoho čísla na úkor několika jiných čísel se ale v souhrnu nevyplatí.

Stromy radeji vyrovnavej.svg

Zelený list můžeme přesunout libovolně blízko ke kořeni a uspíšit tak jeho uhodnutí, jenže tím neúměrně prodloužíme cestu k červenému podstromu a celkovou situaci tak v průměru zhoršíme.
ikona boxu
Chcete vědět víc?

TODO: tohle je NE je stejně dobré jako ANO? Odpovědi ANO a NE ne jsou z informačního hlediska rovnocenné, samy o sobě žádný význam nemají. Lidé ale nejsou jednoduché stroje a při vzájemné komunikaci nepřijímají informace zdaleka jen z obsahu sdělovaných slov. Jistě postřehnete zásadní rozdíl ve vyznění těchto informačně téměř rovnocenných otázek:

  • „Je vynesený koš?“
  • „Vynesl jsi koš?“
  • „Že jsi pořád nevynesl koš?“

Stroje jsou v tomto ohledu pro leckoho příjemnější, než lidé: Nepoužívají ke komunikaci žádné neurčité náznaky.

V případě zjišťování jednoho z šestnácti čísel tedy snadno zjistíme, že potřebujeme pokaždé čtyři otázky. Nejlepší, průměrný a nejhorší počet se neliší.

TODO: bck: Liší se nanejvýš o jednu otázku — a to v případě takového počtu listů, pro který nelze dokonale vyrovnaný strom sestrojit.

Může se ovšem stát, že je hledaných možností např. jen dvanáct, a nelze sestavit strom, v němž by každé hledání bylo stejně dlouhé.

ikona boxu
Úloha: Rozhodovací strom pro 12 možností

Sestav co nejlepší rozhodovací strom pro 12 možností.

  • Co v tomto případě znamená „co nejlepší“ strom?
  • Jaké v něm bude nejdelší a nejkratší dotazování? O kolik se budou lišit?
  • Jak takový strom systematicky a spolehlivě sestavit?

Nemusíš pracovat v hlavě, strom si nakresli, nebo sestroj na počítači!

ikona boxu
Co je příčina, co je důsledek?

Zajímavé je, že lze optimální rozhodovací strom popsat i naopak. Platí tedy oba směry:

  1. Pokud se nejkratší a nejdelší dotazování ve stromu liší nanejvýš o jedinou otázku, je strom optimálníPrůměrná délka dotazování v něm je nejkratší možná.
  2. Je-li strom optimálníPrůměrná délka dotazování v něm je nejkratší možná, liší se nejkratší a nejdelší dotazování v něm nanejvýš o jedinou otázku.

Kritéria kvality stromu jsou stejná jako doposud: chceme co nejkratší dotazování nezávisle na štěstí, tedy v průměrném případě. I v takovém případě se tedy držíme zásady vměstnat co nejvíce možností co nejblíže ke kořeni, a co nejvíce větvení tak plně využít. Výsledkem pro libovolný počet možností (takže i 12) je, že se rozdíl nejkratšího a nejdelšího dotazování liší nanejvýš o jedinou otázku (a průměrná délka dotazování proto bude „někde mezi“).

Stromy 12 moznosti.svg

Tři optimální a jeden neoptimální rozhodovací strom pro 12 možností - který to je?

Optimální dotazovací strategie

ikona boxu
Chcete vědět víc?

Myšlenku půlení intervalů lze samozřejmě zorganizovat i jinak. Můžeme se např. ptát, jestli je hledané číslo menší než medián atp. Výhody půlení intervalů zůstanou zachovány.

Už víme, jak optimální dotazovací strategie vypadá, tedy jaký je tvar příslušného stromu. Jaké ale konkrétně pokládat otázky, aby rozdělovaly zbývající možnosti na poloviny a vyšel tak pěkně rovnoměrný strom? Oblíbenou strategií informatiků je tzv. půlení intervalůMůžete se setkat i s názvem binární vyhledávání, to je obdobný princip.. Předpokladem je, že pracujeme s kompletním rozsahem čísel (bez „děr“).

ikona boxu
Pamatuj si: Postup půlení intervalů

Zeptáme se, jestli je hledané číslo větší nebo rovno číslu uprostředPři sudém počtu možností žádná „prostřední“ neexistuje. Zvolíme tedy třeba jednu ze dvou prostředních. zbývajícího rozsahu. Odpověď vyloučí přesně polovinu čísel (ledaže jich byl lichý počet). Navíc budou zbývající čísla opět tvořit nepřerušenou posloupnost, takže na ně můžeme požít stejný princip, dokud se nedostaneme ke hledanému číslu.

Strom 0 15.svg

Příklad rozhodovacího stromu pro nalezení celého čísla v rozsahu 0—15, který využívá princip půlení intervalů.
ikona boxu
Polovina z poloviny z poloviny

Všimněte si zajímavého „triku“ v popisu postupu půlení intervalů: „Zjisti, ve které polovině prohledávaného intervalu je hledané číslo, a pak pokračuj prováděním tohoto postupu od začátku, a pracuj při tom už jenom se správnou půlkou původního intervalu“. Totéž je vidět i na rozhodovacím stromu: jakmile se rozhodneme pro jednu ze dvou odpovědí a část stromu, kterou už jistě nebudeme potřebovat, si odmyslíme, zbyde nám sice menší, ale opět strom (navíc odpovídající stejným pravidlům). Takové použití „sebe sama“ nazýváme rekurze. Je to neskutečně užitečný a mezi informatiky proto oblíbený nástroj. S rekurzí se ještě mnohokrát setkáme. TODO: odkaz to dané kapitoly

TODO:

Příklad:

worked example, nebo 3
ikona boxu
Úloha: Zkus si to!

Postup půlení intervalů vyzkoušej, nejlépe ve dvojici. Můžeš vyzkoušet různé rozsahy čísel. Byl potřeba správný počet otázek?

Postup půlení intervalu nijak nezávisí na tom, kolik máme možností. Lze použít stejně dobře na čísla 0—15, jako na čísla 1—100, ale také -23465—1,23654756⋅1012. To je jistě ulehčující zjištění — jen si představ, že by bylo nutno sestrojit příslušný rozhodovací strom!

Ve variantě se zvířaty zůstává princip stejný. Každou otázkou se snažíme rozdělit zbývající zvířata (alespoň přibližně) na poloviny a ptáme se, ve které polovině se zvíře nachází. Postup opakujeme, dokud nezbyde jediné zvíře. Samozřejmě k účinnému dělení zvířat na potřebné skupiny je třeba se ve zvířatech poměrně dobře vyznat — přinejmenším vědět, kolik je asi tak zvířat s různými vlastnostmi a jejich kombinacemi. Pak si můžeme v každé situaci vybrat tu vlastnost, která rozdělí zbylé možnosti co možná nejrovnoměrněji.

I kdybychom o zvířatech věděli jen málo, jako informatici si poradíme. Když budeme opravdu chtít, vzájemně se domluvíme a všechna myslitelná zvířata očíslujeme. A tím jsme vlastně hotovi — zjišťovat efektivně čísla už přeci umíme. Přitom očíslovat v principu dovedeme cokoliv, co lze použít v naší hře. Původní zadání (zjišťování myšleného zvířete) jsme převedli na zadání, které dovedeme pohodlně řešit (zjišťování myšleného čísla). To je další z oblíbených informatických „triků“.

Shrnutí

ikona boxu

Rozhodovací stromy umožňují přehledně znázornit celý rozhodovací proces. Zároveň umožňují zkoumat a porovnávat, jak jsou různá rozhodování efektivní. Rozhodování začíná v kořeni, z jednotlivých uzlů se pokračuje do příslušných větví podle získaných odpovědí (informací), dokud se nedojde ke konečnému rozhodnutí, zapsaného v listu stromu. Co do počtu položených otázek rozlišujeme nejkratší, průměrné a nejdelší rozhodování (to odpovídá tzv. výšce stromu).

Optimální rozhodovací strom pro stejně pravděpodobné možnosti je vyrovnaný, každé rozhodování vyžaduje téměř stejný početPočet se liší nanejvýš o jedna, a to v případě, kdy zcela vyrovnaný strom pro daný počet možností sestavit nelze. otázek. Zbývající možnosti tak dělí vždy na stejně početné skupiny, v případě otázek se dvěma možnými odpověďmi (např. ANO a NE) tedy na poloviny.

Optimální herní strategie pro hádání myšleného číslaNebo čehokoliv jiného, co dovedeme seřadit, nebo si jinak pomoci k možnosti dělení možností na poloviny. spočívá v půlení intervalů. Opakovaně dělíme zbývající možnosti na poloviny a zjišťujeme, ve které z nich se nachází to, co hledáme - s touto polovinou pak postup opakujeme, dokud nezbyde jediná možnost.

Půlení intervalů lze využít i pro řešení mnoha dalších vyhledávacích problémů. V informatice jde o jeden z nejpoužívanějších postupů.