Rozhodovací stromy a chytré otázky — metodické poznámky k hodině

Související materiály:

• Kapitola učebnice
• Plán hodiny (k použití přímo ve výuce)

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.

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.

Průběh hodiny

Práce s rozhodovacími stromy je velmi intuitivní a pochopit vše potřebné studentům obvykle nezabere mnoho času. Cvičně si sestaví strom na téma, které je zajímá (nedostanou-li lepší nápad, můžeme nabídnout téma podle jejich studijního zaměření nebo jiných zájmů). 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 (a obecně grafy), 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í. Tenhle přechod (od jednoho konkrétního dotazování/rozhodování, kde mohu mít štěstí, k průměrné výkonnosti) může být pro některé studenty obtížný. Studenti pak potřebují více přímých zkušeností se stromy a dotazováním (ať už v kontextu hry nebo jiném), aby mohli dojít k potřebným zobecněním.

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.
• Hodina těsně navazuje na předchozí. Pokud větší část studentů na předchozí hodině chyběla, bude na začátku potřeba aspoň stručné opakování.
• 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í.