Embedded Files
Zadání
Zadání
Rozpracovat nějakou bobří úlohu na menší.
Podrobnější pokyny a příklad:https://popelka.ms.mff.cuni.cz
Řešení
Řešení
Úloha: "Placené mosty"
Město se rozprostírá na jezeře s mnoha ostrovy.
Ty jsou spojeny pomocí mostů, jak je znázorněno na obrázku.
Mosty jsou buď veřejné (plná čára) nebo zpoplatněné (přerušovaná čára).
Sandra chce dojet z domova (ostrov s domem) na ostrov s lesem.
Sandra má dostatek peněz na zaplacení nejvýše dvou zpoplatněných mostů (přerušovanou čarou).
Jaký je nejmenší počet mostů po kterých musí projít?
A) 7
B) 5
C) 6
D) 4
E) Nechci odpovídat
Řešení zjednodušené (bez ohledu na placené / neplacené mosty)
Kolik nejméně mostů musí Sandra přejít při cestě z domova do lesa?
Kolik existuje nejkratších cest mezi domovem a lesem?
Kolik nejméně ostrovů musí Sandra přejít při cestě z domova do lesa?
Má vliv velikost ostrova na délku trasy z domova do lesa?
Má vliv délka mostu na délku trasy z domova do lesa?
Lze nejkratší cestu z domova do lesa zapsat pomocí nějakých symbolů (čísel/písmen)?
Které cesty vedou z domova na ostrov s lesem?
Řešení dle zadání (s ohledem na placené / neplacené mosty)
Jaký význam má čárkovaná čára?
Jaký význam má plná čára?
Lze si znázornit placené a neplacené mosty, lépe graficky / symbolicky zobrazit?
Kolik placených mostů může Sandra maximálně přejít?
Musí Sandra využít vždy placené mosty?
Kolik nejméně mostů musí Sandra přejít při cestě z domova do lesa?
Kolik existuje nejkratších cest mezi domovem a lesem?
Kolik nejméně ostrovů musí Sandra přejít při cestě z domova do lesa?
Má vliv velikost ostrova na délku trasy z domova do lesa?
Má vliv délka mostu na délku trasy z domova do lesa?
Lze nejkratší cestu z domova do lesa zapsat pomocí nějakých symbolů (čísel/písmen)?
Které cesty vedou z domova na ostrov s lesem?
Které z cest splňují omezení nejvýše dva placené mosty?
Jaký postup můžeme použít, abychom našli nejkratší cestu, která splňuje omezení na placené mosty?
Jak rychle nám bude trvat najít správnou cestu? Dalo by se to udělat rychleji?
Jaké různé příklady můžeme zkusit, abychom zkontrolovali, že postup opravdu funguje?
Existuje nějaký jiný způsob, který by mohl být jednodušší nebo rychlejší?
Cílem této úlohy je naučit se řešit problémy s využitím teorie grafů a algoritmického myšlení.
Žák se naučí:
zobrazit situace pomocí grafu
žák se naučí znázornit některé situace (ostrovy jsou uzly a mosty jsou hrany) jako graf
pracovat s omezením/podmínkou
žák se naučí pracovat s omezením / podmínkou (max. počet placených mostů, které lze překročit), což je klíčové při hledání správných řešení
hledat optimální cestu
žák se naučí, jak najít nejkratší nebo nejvýhodnější cestu v grafu, což je základní algoritmická dovednost při hledání optimálních řešení
algoritmické myšlení a efektivitu
žák se naučí navrhnout řešení, které bude nejrychlejší, což je důležité z hlediska efektivity, a dále se naučí, že existují různé způsoby, jak úlohu řešit, a že některé jsou rychlejší než jiné
testování řešení
žák se naučí, že po vytvoření algoritmu je nutné ho otestovat na různých případech, neboť to pomáhá ověřit správnost řešení a rozvíjí schopnost hledat a opravovat chyby
Page updated
Google Sites
Report abuse