Mendelova zemědělská a lesnická univerzita v Brně Institut celoživotního vzdělávání
Výuka algoritmizace a vazba na ostatní předměty Závěrečná práce
Vedoucí práce: doc. Ing. Dr. Jiří rybička
Mgr. Miroslav Janyš
Ústí nad Orlicí 2008
2
Děkuji doc. Ing. Jiřímu Rybičkovi za cenné rady a připomínky, které mi poskytl při tvorbě této závěrečné práce.
3
Prohlašuji, že jsem tuto závěrečnou práci vyřešil samostatně s použitím literatury, která je uvedena v seznamu literatury.
V Ústí nad Orlicí 20. srpna 2008
………………………………
4
Abstract Janyš M., Teaching Algorithmisation and Relationships to Other Subjects. Ústí nad Orlicí, 2008 The final paper deals with the basics of the Algorithms topic and its utilisation in some subjects. The theory is accompanied with examples and demonstrations. The aim of the paper is to show the connection and relations of computer science to other subjects.
Abstrakt Janyš M., Výuka algoritmizace a vazba na ostatní předměty. Ústí nad Orlicí, 2008 Závěrečná práce zpracovává základy tématického celku algoritmy a jeho užití v některých předmětech. Teorie je doplněna příklady a ukázkami. Cílem práce je ukázat propojení a vazbu výpočetní techniky na ostatní předměty.
5
Obsah 1. Úvod a cíl práce
6
1.1 Úvod do problematiky ..................................................................................6 1.2 Cíl práce........................................................................................................6 2. Analýza problému
7
2.1 Pojem algoritmus ..........................................................................................7 2.2 Algoritmus ve výuce.....................................................................................7 3. Algoritmus a jeho charakteristiky
8
3.1 Algoritmická úloha a její specifikace ...........................................................8 3.2 Algoritmus a jeho vlastnosti .........................................................................10 3.3 Zápis algoritmů.............................................................................................12 4. Užití a ukázky algoritmů ve výuce
19
4.1 Proč vývojový diagram.................................................................................19 4.2 Nástroje pro tvorbu diagramu.......................................................................20 4.3 Postup algoritmizace při řešení úloh ............................................................20 4.4 Jednoduché algoritmy bez použití cyklu a větvení.......................................20 4.5 Algoritmy s užitím větvení ...........................................................................24 4.6 Algoritmy s použitím cyklu.........................................................................28 5. Závěr
35
6. Literatura
36
6
1. Úvod a cíl práce 1.1 Úvod do problematiky Tato závěrečná práce zpracovává problematiku algoritmizace ve výuce. Algoritmický přístup k řešení problémů je celkem běžný a používaný v pedagogické praxi. Přírodovědné předměty, zejména pak matematika, fyzika, chemie, biologie nebo informatika a výpočetní technika často vyžadují přesnou specifikaci vstupních a výstupních dat a následný algoritmický návrh řešení. Tento způsob myšlení a řešení úloh se může užít i v dalších předmětech. Můžeme tak doplnit výuku o nové přístupy a ukázat propojení informatiky a dalších předmětů. 1.2 Cíl práce Koordinátor informačních a komunikačních technologií (dále jen ICT) by měl pomáhat kolegům při aplikacích ICT na škole a metodicky usměrňovat výuku v různých předmětech. Ne každý vyučující je schopen efektivně využívat výpočetní techniku a algoritmizovat úlohy. Algoritmický přistup k řešení problémů a jeho zpracování je pro většinu učitelů velmi náročný. V oblasti algoritmizace má každý učitel své postupy a těžko přijímá nové, pokud mu nejsou správně vysvětleny. Pokusil jsem se spolupracovat s učiteli různých předmětů a vytvořit s jejich pomocí algoritmy jimi navržených úloh. Ukázky dané problematiky pro jiné předměty jsou proto důležité pro přijetí nového postupu. V úvodu práce jsou vysvětleny základní pojmy, které by měli vyučující znát, pokud by chtěli zkusit algoritmicky zpracovat určitý problém, úlohu nebo příklad. Tento úvodní výklad je svým podáním více zaměřen na informatiku a výpočetní techniku. Dále na ukázkách z několika dalších předmětů je ukázán algoritmický přístup a zpracování úkolů.
7
2. Analýza problému 2.1 Pojem algoritmus Pojem algoritmus není nový. Setkáváme se s ním už u starých Babylóňanů. Pojem algoritmus patří mezi základní, prvotní matematické pojmy. Takovéto pojmy nedefinujeme přímo, ale pomocí jejich vlastností, jejich chováni, účinků apod. Intuitivně pod pojmem algoritmus rozumíme postup, návod jak řešit libovolnou úlohu, problém nebo příklad. Algoritmus je tedy obecný návod, jak postupovat. Je tvořen posloupností pokynů (příkazů, instrukcí), které popisují určitou činnost. Je to přesně definovaná konečná postupnost pravidel, jejichž realizace nám pro vstupní data umožní po konečném počtu kroků získat výstupní data. 2.2 Algoritmus ve výuce Vytvoření algoritmu je určitá, obvykle dost náročná duševní práce. Základním krokem při řešení každé úlohy, každého problému je vědět, co chceme řešit, co je dáno, tedy jaké jsou vstupní informace nebo údaje, a co požadujeme jako výstup řešení, jaké jsou výstupní informace nebo údaje. Toto je dobré si uvědomit při řešení všech úloh a problémů ve vyučování. Většina studentů je připravena takto přemýšlet hlavně v matematice, fyzice, informatice nebo přírodovědných předmětech. Stejným způsobem lze řešit úlohy a takto uvažovat i v jiných předmětech, kde pak můžeme získat velmi přehledné a názorné postupy. Zápis řešení je pak dalším logickým krokem řešení. Nejjednodušší zápis algoritmu je pomocí prostředků přirozeného jazyka. Běžně se využívá při zpracování a řešení úloh. Ve většině příkladů takto řešitel pracuje, aniž si to uvědomuje. Z dalších možných zápisů je pro výuku vhodný zápis pomocí vývojových diagramů. Seznámit se se základními značkami a principy tvorby vývojových diagramů je pro vyučující i žáky poměrně snadné. Proto algoritmizace úloh a jejich zápis v této formě je ve většině předmětů možný a vhodný. Současně by však bylo chybou snažit se algoritmizovat vše a za každou cenu.
8
3. Algoritmus a jeho charakteristiky Každou úlohu, kterou chceme řešit, musíme správně pochopit. Musíme se s ní seznámit a vědět co chceme řešit. Úloha musí být přesně specifikována. To znamená, že musíme přesně vědět, co je dáno, tedy jaké jsou vstupní informace nebo údaje, a co požadujeme jako výstup řešení, jaké jsou výstupní informace nebo údaje. Podle algoritmů neřeší úlohy pouze člověk, ale také stroj (např. počítač). Člověku nebo stroji, který pracuje podle daného algoritmu, říkáme realizátor algoritmu nebo procesor. Procesor proto, že řešení úlohy se obvykle neuskutečňuje v jednom kroku, ale tvoří určitý proces. Pojem realizátor používáme častěji ve spojeni s člověkem, procesor se strojem (počítačem). Řešení úlohy podle daného algoritmu říkáme realizace algoritmu. Aby procesor mohl pracovat podle daného algoritmu, musí být algoritmus zapsán v takovém jazyce, kterému procesor rozumí, s pomocí takových akci, které je schopen provádět. To je i jeden z důvodů, proč by se algoritmizaci a tvorbě algoritmů měla věnovat pozornost právě ve spojitosti s počítačem. Počítač umí provádět jen velmi elementární akce a jeho mateřský jazyk je velmi vzdálen našemu jazyku. Proto se při tvorbě algoritmu nesnažíme psát algoritmy hned v jazyce určitého procesoru, ale v jazyce, který je bližší řešené úloze. Z tohoto jazyka je potom obvykle přepíšeme do požadovaného jazyka. V souvislosti s výukou a vazbou na ostatní předměty využijeme zápis algoritmu pomocí vývojových diagramů. 3.1 Algoritmická úloha a její specifikace Z hlediska výuky jsou důležité takové úlohy, jejichž řešením získáme nové informace. Protože jsou produktem řešení, nazveme je výstupní informace nebo výstupní údaje. Informace, z kterých při řešení úloh vycházíme, nazýváme vstupní informace nebo také vstupní údaje. Pomoci vstupních a výstupních údajů zadáme úlohu k řešení, určíme, jakou úlohu budeme vlastně řešit. Vstupní údaje známe před začátkem řešení jako konkrétní údaje. Výstupní údaje před řešením v konkrétním tvaru neznáme. Výstupní hodnoty zadáváme implicitně - skrytě, pomoci podmínek, které musí tyto údaje splňovat. Jestliže řešíme například úlohu, v které je třeba najít největší společný dělitel dvou celých kladných čísel A, B, vstupními údaji budou dána dvě celá kladná čísla A, B jako konkrétní hodnoty. Výstupní hodnotu určíme pomoci podmínky, že to bude největší celé číslo, které děli A i B beze zbytku. Podmínku, kterou musí splňovat výstupní údaje, nazýváme výstupní podmínka. Ani vstupní údaje nemohou mít libovolnou hodnotu, ale musí vyhovovat jisté podmínce, kterou nazýváme vstupní podmínka. Vstupní a výstupní podmínkou charakterizujeme úlohu, kterou máme řešit, specifikujeme to, co je třeba řešit. Nejde nám o jednu konkrétní úlohu, ale o celou třídu úloh, jejichž vstupní údaje splňuji vstupní podmínku a výstupní údaje výstupní podmínku. Protože na řešení takovéto úlohy chceme vytvořit algoritmus, budeme ji nazývat algoritmická úloha.
9
Skutečnost, že úloha je specifikována, že víme, co máme řešit, ještě neznamená, že se nám musí vždy podařit utvořit odpovídající algoritmus na její řešeni. Existuji úlohy, pro které to není možné. Jakékoliv údaje o řešení úlohy je však možné udělat jen tehdy, když víme, co je třeba řešit. Protože specifikace úlohy platí pro libovolnou úlohu dané třídy, budeme vstupní a výstupní údaje často označovat symbolicky. Neřekneme, že je třeba najít největší společný dělitel čísel například 286 a 2 268, ale obecně čísel A a B. Budeme-li řešit kvadratickou rovnici, můžeme použit tvar: AX2 + BX + C = 0 a kořeny budeme označovat jako X1 a X2. Takovéto symbolické označení vytvoříme z písmen a číslic, přičemž prvním znakem bude vždy písmeno. Nazveme je identifikátory. Identifikátory jsou například A, B, KOEFICIENT, POLOMĚR, PI, X1, X2 atd. V úlohách budeme většinou používat pro identifikátory malá písmena, čímž zdůrazníme, že jde o konkrétní úlohu. V specifikaci a v algoritmech budeme pro identifikátory používat velká písmena, čímž zdůrazníme obecnost specifikace a algoritmu. Takovéto označení identifikátorů je velmi výhodné například při řešení úloh v matematice, fyzice, chemii nebo v informatice. V jiných předmětech je většinou méně použitelné. Pokud by nás zajímalo především řešení úloh na počítači, chápeme identifikátor jako symbolické označeni místa, kde si počítač uchovává danou hodnotu. Během řešení úlohy mohou být v daném místě různé hodnoty, ale v každém okamžiku jen jedna. Můžeme říci, že je to vlastně objekt, který během řešeni úlohy mění svoji hodnotu. Podobně jako v matematice nazveme tento objekt proměnná. Pro jednoduchost a stručnost neříkáme proměnná označená například identifikátorem A, ale jednoduše proměnná A. Hovoříme také o vstupních a výstupních proměnných, které pro konkrétní úlohy nabudou konkrétních hodnot. Vstupní a výstupní podmínka se bude týkat právě hodnot proměnných. K zápisu specifikací úloh používáme nejčastěji jazyk výrokových forem, který budeme doplňovat výrazy z přirozeného jazyka. Jestliže se podmínka skládá z několika části, které musí platit současně, jednotlivé části doplníme o logické spojky. V některých předmětech lze použít pouze výrazy přirozeného jazyka. Ukázka specifikace úlohy z matematiky – obsahy rovinných obrazců Úlohu výpočtu povrchu a objemu krychle se stranou a můžeme specifikovat takto: Vstupná proměnná: A Vstupní podmínka: A je celé kladné číslo Výstupní proměnné: POVRCH, OBJEM Výstupní podmínka: POVRCH = 6 * A2, OBJEM = A3 Úloha může mít jeden nebo více vstupních údajů. Každá konkrétní úloha si vyžaduje takový počet konkrétních vstupních hodnot, kolik jich určuje specifikace úlohy. Specifikace úlohy nemusí být vždy nutnou součástí řešení, ale je nutné si výše uvedené pojmy uvědomit a v návrhu řešení je brát v úvahu.
10
Úlohy – procvičení specifikace úloh – matematika a informatika Specifikujte následující úlohy : Je dáno reálné číslo r. Najděte obsah kruhu, délku kružnice, objem koule s poloměrem r. 2. Jsou dány přímky 3x - 2y + 1 = 0, x - 5y + 2 = 0 . Zjistěte, zda bod se souřadnicemi [a, b] je jejich průsečíkem. 3. Jsou dána tři čísla a, b, c. Najděte maximální a minimální z nich. 1.
3.2 Algoritmus a jeho vlastnosti Po specifikaci úlohy, po specifikaci toho, co je třeba řešit, přistupujeme k tomu, jak řešit, tj. k tvorbě postupu řešení, návrhu algoritmu. Zde už je třeba brát v úvahu nejen samotnou úlohu, ale i realizátora - procesor postupu řešeni. Každý procesor je schopen vykonávat určitý počet akcí - operací, přičemž každá akce má předepsány podmínky realizace, účinek realizace a konečnou dobu trvání. Co znamená vytvořit postup řešení? Nejprve zjistíme, zda lze úlohu řešit použitím některé z akci procesoru. Jestliže ano, použijeme ji a úlohu máme vyřešenu. Jestliže ne, musíme úlohu rozkládat na podúlohy, a to tak dlouho, dokud neodpovídají podúlohám, které umíme řešit některou akci procesoru. Kombinaci - akcí odpovídajících jednotlivým podúlohám dostaneme hledaný postup řešení. Jeho použitím pro vstupní údaje zajistíme jejich transformaci, převod na výstupní údaje, tj. údaje splňující výstupní podmínku. Jestliže vezmeme úlohu z příkladu v předchozí kapitole (povrch a objem krychle) a procesor umí násobit celá čísla, potom postup řešení je přímočarý. Stačí použít výstupní podmínku, v které umocněni nahradíme násobením. Akce, které je procesor schopen vykonávat, jsou obvykle jednoduché a transformaci vstupních údajů na výstupní je třeba zajistit jejich postupné skládání. Transformace se tedy neuskutečňuje v jednom kroku, ale postupně tak, jak se provádějí jednotlivé akce procesoru. Každá akce mění hodnoty - stav proměnných vyskytujících se v algoritmu. Postup řešení předpisuje následnost provádění jednotlivých akci. Obecná pravidla určující postupnou - transformaci vstupních údajů na výstupní nazýváme algoritmus. Pro algoritmus jako postup řešení úlohy většinou platí tzv. základní vlastnosti: hromadnost, determinovanost a rezultativnost. Hromadností algoritmu rozumíme skutečnost, že algoritmus je použitelný nejen pro jednu konkrétní úlohu s konkrétními vstupními údaji, ale pro libovolné vstupní údaje splňující vstupní podmínku. Determinovanost algoritmu znamená, že v každém kroku algoritmu musí být jednoznačně určeno, co se má provést. Realizace algoritmu nesmí být podmíněna jinými podmínkami než těmi, které jsou v něm uvedeny.
11
Rezultativnost algoritmu znamená, že proces předepsaný algoritmem je konečný, že skončí po konečném počtu kroků. Někdy říkáme stručně, že algoritmus je konečný. Tyto vlastnosti by měli námi navržené algoritmy splňovat. Jednotlivé pojmy jsou vysvětleny při řešeni jednoduché úlohy. Příklad – matematika – řešení kvadratické rovnice v R Algoritmus řešení kvadratické rovnice s reálnými koeficienty, přičemž nás budou zajímat pouze reálné kořeny. Předpokládáme, že procesor umí provádět předepsané operace. Specifikace úlohy Vstupní proměnné : A, B, C Výstupní podmínka : A, B, C jsou reálná čísla, B2 – 4.A.C = 0, A<>0 Výstupní proměnné : X1 , X2 Výstupní podmínka : A.X12 + B.X1+C = 0, A.X22 + B.X2 + C = 0 Algoritmus – popis prostředky přirozeného jazyka 1. 2. 3.
Polož A, B, C rovnající se koeficientům konkrétní kvadratické rovnice a pokračuj 2. krokem. Vypočítej hodnotu diskriminantu D, tedy B2 - 4.A.C, a pokračuj 3. krokem. −B− D −B+ D Polož X1 rovné hodnotě výrazu , X2 rovné hodnotě a skonči. 2.a 2.a
Tento algoritmus je použitelný pro libovolnou trojici reálných čísel A, B, C splňujících vstupní podmínku, a má tedy i požadovanou vlastnost hromadnost. Vlastnost determinovanost je podmíněna znalostí provádění uvedených operací, což jsme předpokládali. Každý krok algoritmu potom jednoznačně určuje, jaké operace je třeba v daném kroku provést, a také to, kterým krokem pokračovat po jejich provedení. Konečnost procesu realizace algoritmu je zřejmá. Algoritmus skonči ve 3. kroku.
12
Úlohy – fyzika, informatika, procvičení tvorby algoritmu – zápis přirozeným jazykem Je dáno přirozené číslo c představující časový interval vyjádřený v sekundách. Vytvořte algoritmus pro vyjádření daného časového intervalu v hodinách, minutách a sekundách. 2. Jsou dána dvě celá kladná čísla a, b. Vytvořte algoritmus pro výpočet součinu a . b pomoci sčítání. 1.
3.3 Zápis algoritmů Pro zápis algoritmů můžeme použít přirozený jazyk. Toto je asi nejjednodušší a nejpřirozenější způsob zápisu algoritmů. Takto zapsané algoritmy se užívají ve výuce, aniž bychom je takto pojmenovali. Z logicky souvisejících akcí jsme vytvoříme jednotlivé kroky algoritmu, přičemž předpokládáme, že realizace algoritmu obsahuje informaci o tom, který krok se bude provádět jako následující. Tento zápis obyčejně zjednodušujeme tímto předpokladem: jednotlivé kroky algoritmu se provádějí postupně za sebou tak, jak jsou zapsány, jestliže není explicitně udáno jiné pořadí. Další možností, jak algoritmus zapsat, je použít vývojového diagramu. Tento způsob je jednoduchý a srozumitelný nejen pro žáky, ale i pro vyučující nepočítačových předmětů. Stačí se seznámit s několika základními značkami a jejich významem. Jazyk vývojových diagramů má definovánu abecedu, která je v tomto případě definována množinou přípustných značek – bloků určených normou ČSN ISO 5807 ČSH 369030. Do značek zapisujeme činnost nebo činnosti, které se mají v daném s místě algoritmu provést. Tok řízení se zapisuje orientovanou spojnici jednotlivých značek. Z množiny přípustných značek stačí ukázat jen základní, které nám postačí pro zápis libovolného algoritmu. Jsou zobrazeny na obr. 1 až 4.
13
Obr. 1. Začátek algoritmu. V tomto místě začíná realizace algoritmu.
Obr. 2. Konec algoritmu. V tomto místě končí realizace algoritmu.
Obr. 3. Zpracování. Do bloku zpracováni zapisujeme akce, které se mají provést, jestliže se řízení předá tomuto bloku.
Obr. 4. Rozhodování. Do rozhodovacího bloku zapisujeme podmínku. Její splněni nebo nesplněni urči blok, kterému se v dalším kroku předá řízení.
Konstrukce algoritmu ze specifikace úlohy není přímočará. Přímočaře můžeme postupovat při jednoduchých úlohách. Základní technikou konstrukce algoritmů pro složitější úlohy je jejich rozklad na jednodušší podúlohy. Budeme používat tři druhy rozkladů : konjunktivní, disjunktivní a repetiční. Konjunktivní rozklad je takový rozklad, při kterém bude řešení úlohy sestávat z postupného řešení všech podúloh, na které jsme danou úlohu rozložili. Při disjunktivním rozkladu bude řešení (konkrétní) úlohy sestávat z řešení pouze jedné, vybrané podúlohy. Při repetičním rozkladu bude řešení úlohy sestávat z několikanásobného opakování řešeni dané podúlohy. Těmto rozkladům odpovídají tyto algoritmické konstrukce: konjunktivnímu rozkladu odpovídá sekvence, disjunktivnímu rozkladu odpovídá větvení, repetičnímu rozkladu odpovídá cyklus.
14
Sekvence je algoritmická konstrukce vytvořená z akcí a1, a2, ..., an odpovídajícím podúlohám p1, p2, ..., pn, na které jsme rozložili úlohu p. Sekvence se realizuje tak, že se realizuji jednotlivé akce a1, a2, ..., an, a to v takovém pořadí, jak jsou napsány, jestliže není explicitně udáno jiné pořadí. V jazyce vývojových diagramů zapisujeme sekvenci takto (možný je i vertikální zápis):
Vývojový diagram sekvence V jazyce založeném na češtině zapisujeme sekvenci takto: proveď a1, a2,……aN
Větveni (někdy též binární větveni, rozhodování, podmínka) je algoritmická konstrukce utvořená z podmínky b a akcí a1, a2 odpovídajících podúlohám p1, p2, na které jsme rozložili úlohu p. Větveni se realizuje tak, že jestliže je podmínka b splněna, realizuje se akce a1, jinak akce a2. V jazyce vývojových diagramů zapisujeme větveni takto:
Vývojový diagram větvení V jazyce založeném na češtině zapisujeme větvení takto: jestliže b pak a1 jinak a2 + znamená splněni podmínky b - znamená nesplnění podmínky b
15
Speciálním případem větvení je situace, kdy je jedna akce, např. a2, prázdná. Realizace je potom taková, že jestliže je podmínka b splněna, provede se akce a1, jinak se neprovede nic. V jazyce vývojových diagramů zapisujeme tento druh větvení:
Vývojový diagram větvení s prázdnou akcí V jazyce založeném na češtině zapisujeme větvení takto: jestliže b pak a1 + znamená splněni podmínky b - znamená nesplnění podmínky b
Cyklus je algoritmická konstrukce utvořená z podmínky b (podmínka opuštění cyklu) a z akce a odpovídající podúloze p, nebo z akci a1, a2 odpovídajících podíílohám p1, p2. Podle způsobu organizace podmínky b a akce a, popřípadě akcí a1, a2, rozlišujeme tři typy cyklů: 1. cyklus s podmínkou na konci 2. cyklus s podmínkou na začátku 3. cyklus s pevným počtem opakování
16
Cyklus s podmínkou na konci zapisujeme v jazyce vývojových diagramů tak, jak je znázorněno na obrázku:
Vývojový diagram cyklu s podmínkou na konci V jazyce založeném na češtině zapisujeme cyklus s podmínkou na konci takto: opakuj a dokud nebude b
Realizuje se následovně: realizuje se akce a. Potom se zjišťuje, zda je nebo není splněna podmínka. Říkáme, že testujeme podmínku b. Jestliže je splněna, realizace cyklu konči. Jestliže splněna není, opakuje se proces realizace akce a a testu podmínky b, a to tak dlouho, dokud podmínka není splněna:
17
Cyklus s podmínkou na začátku zapisujeme v jazyce vývojových diagramů tak, jak ukazuje obrázek:
Vývojový diagram cyklu s podmínkou na začátku V jazyce založeném na češtině zapisujeme cyklus s podmínkou na začátku takto: opakuj dokud nebude b prováděj a Realizujeme následovně: Testuje se podmínka b. Jestliže je splněna realizace cyklu konči. Jestliže není splněna, opakuje se realizace akce a a testu podmínky b, a to tak dlouho, dokud podmínka b není splněna.
18
Cyklus s pevným počtem opakování zapisujeme v jazyce vývojových diagramů tak, jak je znázorněno na obrázku:
Vývojový diagram cyklu s pevným počtem opakování V jazyce založeném na češtině zapisujeme cyklus s pevným počtem opakování takto: opakuj a není-li konec cyklu Realizujeme následovně: Proměnná I je tzv. řídící proměnná cyklu. Na začátku má hodnotu 1, která se postupně zvyšuje o 1 při každém průběhu cyklu. Při každém průběhu cyklu se provede akce a. Provádění cyklu končí, když proměnná I nabude hodnotu N. V úlohách můžeme použít některé základní operace (matematika, fyzika, chemie), např.:
Součet Rozdíl Součin Mocnina Logický součet Logický součin Negace Podíl Odmocnina Celočíselné dělení
+ * SQR OR AND NOT / SQRT DIV
(jmenovatel různý od nuly) (odmocněnec kladný) (jmenovatel různý od nuly)
19
4. Užití algoritmů ve výuce a ukázky 4.1 Proč vývojový diagram Pokud je žák i vyučující seznámen se základními pojmy z oblasti tvorby algoritmů a vývojových diagramů, je poměrně snadné použít tento princip řešení úloh ve výuce. Takový návrh řešení je srozumitelný, logický a snadno pochopitelný. Formulace a použití algoritmů je svázáno s dovedností jasně a srozumitelně formulovat myšlenky a pravidla a přesně je dodržovat. V libovolné oblasti činnosti často vzniká potřeba sestavit určité instrukce, pravidla, předpisy (např. pravidla pro určení zadaného vzorku atd.). Ne každý dovede tyto instrukce, předpisy, pravidla (tj. algoritmy) vytvořit, ale přesně je dodržovat musí umět každý člověk, protože vlastně na každém kroku plníme jistá pravidla vyjadřující organizaci našeho života. Největší potíže činí většinou algoritmy větvených procesů, obsahující současně s matematickými operacemi i ověřování logických podmínek, na jejichž výsledku závisí další cesta řešení úlohy. Ve většině předmětů je možné použít ve vyučování názorný způsob zápisů algoritmů. Touto názornou formu zápisu je vývojový diagram algoritmu. Tento zápis použitý ve výuce umožní žákům správně a názorně pochopit a porozumět problematice daného problému. Výklad teorie však nemusí být tak důkladný a podrobný, jak je uvedeno v předchozí kapitole. Vývojovým diagramem určitého procesu je grafické znázornění jeho logické struktury a chronologické návaznosti jednotlivých činností (např. aritmetických nebo logických operací). Vývojový diagram se skládá ze značek, do nichž se vpisují slovně nebo symbolicky operace (skupiny operací). Základní značky a struktury potřebné pro správnou tvorbu vývojových diagramů byly uvedeny v předchozí kapitole. Zvláštní stránka algoritmizace, o které je třeba se zmínit, je algoritmizace ve vyučování, která spočívá v sestavení algoritmu samotného vyučování, tj. popisu samotné vyučovací činnosti učitele pomocí předpisů algoritmického typu. Proces vyučování žáka učitelem spočívá v určité posloupnosti „pedagogických činností“, pomocí kterých učitel řeší určité pedagogické úlohy. Takovými činnostmi jsou: kladení otázek, způsob objasnění, uvádění příkladů a protipříkladů, ukázka názorného materiálu, zadávání cvičení a úkolů. Pomocí analýzy tohoto procesu je možné vyčlenit činnosti, ze kterých se uvedený proces skládá. Často taková analýza reálných vyučovacích procesů ukáže neracionálnost jejich sestavení, bezdůvodnost pedagogických činností učitele a neúčelnost posloupností těchto činností. Vyučovací proces nějakého učiva si můžeme představit ve tvaru předpisů algoritmického typu čili „algoritmů vyučování“. Toto budeme samozřejmě respektovat, ale nebudeme se této problematice věnovat. Naším úkolem bude tvorba algoritmů úloh, příkladů nebo laboratorní práce v různých předmětech a jejich znázornění pomocí vývojových diagramů.
20
4.2 Nástroje pro tvorbu diagramů Pro vlastní tvorbu vývojových diagramů lze použít v nejjednodušším případě tabuli a vhodný nástroj na psaní. To však není příliš výhodné, protože takto vytvořený diagram se nedá dále použít a jeho tvorba je časově náročná. Využití tabule má však i své výhody. Žáci se mohou aktivně zapojit do tvorby diagramu a ovlivnit jeho podobu. Myslím si, že pro vlastní tvorbu diagramů je vhodnější použít některý z programů, které jsou nabízeny většinou jako free software a plně dostačují pro potřeby výuky. V této práci byly veškeré diagramy a značky vytvořeny pomocí programu Dia, což je free software pro kreslení strukturovaných diagramů (http://www.gnome.org/projects/dia).
4.3
Postup algoritmizace při řešení úloh
Dříve než začne vyučující nebo žák tvořit algoritmus nebo nakreslí vývojový diagram je určitě nutné znovu zdůraznit základní pravidla jak postupovat. Samozřejmě dodržujeme postupy a pravidla uvedená v minulých kapitolách, ale soustředíme se jen na nejpodstatnější:
-
zadání úlohy, formulace problému analýza problému a nástin řešení analýza vstupních a výstupních dat návrh algoritmu zápis algoritmu – vývojový diagram zkušební provoz algoritmu a testování vstupních dat
4.4 Jednoduché algoritmy bez použití cyklu a větvení Posloupnost (sekvence) je nejednodušším typem algoritmu. Příslušný problém je rozložen na dílčí problémy, které budou prováděny za sebou. Hlavním úkolem je dát jednotlivé činnosti do správného pořadí a tyto činnosti správně popsat. Dají se použít jednoduché úlohy z různých předmětů. Jako nejvhodnější se pro tuto strukturu se ukázali úlohy z matematicky, fyziky nebo chemie. Také v ostatních předmětech však můžeme použít postupné provádění činností. Matematika, některá témata - geometrie v rovině – obdélník, trojúhelník, Pythagorova věta, kružnice a kruh, mnohoúhelníky - geometrie v prostoru - objemy a povrchy těles - goniometrie – převody úhlů (míra oblouková a stupňová) - funkce – výpočet hodnot funkcí Fyzika, chemie, některá témata veškeré úlohy pro výpočty s užitím vzorců
21
Příklad – matematika, objemy a povrchy těles - ukázka sekvenčního algoritmu Algoritmus pro výpočet objemu a povrchu krychle, délky stěnové a tělesové úhlopříčky. Vstupná proměnná: A – hrana krychle Vstupní podmínka: A>0 Výstupní proměnné: V – objem krychle S – povrch krychle US – velikost stěnové úhlopříčky UT - velikost tělesové úhlopříčky Objem krychle: V = a 3 Povrch krychle: S = 6a 2 Stěnová úhlopříčka: Us = a 2 Tělesová úhlopříčka: Ut = a 3
22
Příklad – zeměpis, památky UNESCO - ukázka sekvenčního algoritmu
Památky UNESCO V roce 1972 byla pod patronací UNESCO uzavřena Úmluva o ochraně světového kulturního a přírodního dědictví. Na základě Úmluvy se vytváří Seznam světového dědictví, do něhož jsou zapisovány památky s mimořádnými hodnotami. V současné době Seznam světového dědictví obsahuje více než 750 kulturních a přírodních památek. V ČR do seznamu památek UNESCO byly postupně zapsány památky uvedené v následujícím algoritmu. Algoritmus pro přiřazeni lokality a historické památky do proměnných. Možnost využít v dalších úlohách. Vstupná proměnná: Vstupní podmínka: Výstupní proměnné:
ne ne ne
23
24
Poznámky a doporučení: -
sekvence se vyskytuje většinou v kombinaci s ostatními strukturami samotná sekvence se zdá být méně vhodná pro humanitní předměty
Pokud použijeme některé operace je třeba dávat pozor na:
-
podíl a celočíselné dělení můžeme provádět pouze v případě nenulového jmenovatele. Pokud bychom připustili nulovou hodnotu, musíme použít větvení výraz pod odmocninou musí být nezáporný. Pokud ne je opět nutné použít větvení. dělení proměnnou, resp. proměnná pod odmocninou musí být také ošetřeno větvením
4.5 Algoritmy s užitím větvení Větvení značně rozšíří možnosti algoritmizace úloh. Pomocí větvení můžeme také ošetřit nežádoucí důsledky v algoritmech, stanovit podmínky, kdy se daná část algoritmu bude provádět. V rozhodovacím bloku musí být však pouze takové podmínky, na které je možno odpovědět buď „ano“ nebo „ne“. Např. otázka „Jaké barvy je dům?“ nemůže být. Musíme se ptát „Je bílý?“ „Je černý?“ apod. Tato struktura se taká jevila jako snadno pochopitelná a logická pro většinu vyučujících a byli ochotni ji akceptovat a používat.
25
Příklad – informatika, ukázka algoritmu s podmínkou Algoritmus, který načte tři čísla a vypíše hodnotu toho, které je prostřední. Vstupná proměnné: Výstupní proměnné :
A, B, C – zadaná čísla S – druhé největší číslo
26
Příklad – chemie, ukázka algoritmu s podmínkou Škrob je produktem fotosyntézy rostlin. Ukládá se jako zásobní látka zejména v hlízách, semenech a plodech. Z těchto částí rostlin se také škrob získává. Škrob je makromolekulární látka složená z amylopektinu a z amylosy. Důkaz škrobu a neznámého sacharidu Algoritmus, který určí sacharid v zadaném vzorku Vstupná proměnné: Výstupní proměnné :
vzorek vzorek, určení cukru
27
Příklad – biologie, jednoduchý určovací klíč, ukázka algoritmu s podmínkou Třída hmyz je dále dělena na dvě podtřídy, do těchto dvou podtříd je zařazen vzorek Systém třídy Insecta - hmyz Podtřída: Thysanura - šupinušky (= Apterygota - bezkřídlí) Podtřída: Pterygota – křídlatí Algoritmus, který zadaný vzorek hmyzu zařadí do podtřídy. Vstupná proměnné: Výstupní proměnné:
vzorek hmyzu třída do které je vzorek přiřazen
28
Poznámky a doporučení: 4.6
užití podmínky je názorné pří určování různých vzorků biologie: klíče k určování živočišných nebo rostlinných druhů zeměpis: klíč k určování nerostů
Algoritmy s použitím cyklu
Cyklus je silným nástrojem při tvorbě algoritmů. Opakuje se celý algoritmus nebo jeho určitá část a to se stejnými nebo s jinými daty. Jednou ze základních vlastností algoritmu je konečnost. Proto musí být jednoznačně určeno, kdy nebo za jakých podmínek se bude cyklus opakovat a kdy musí být ukončen.
Poznámka – cyklus s podmínkou na začátku -
do cyklu se vstupuje, je-li splněna podmínka neplatí-li podmínka, z cyklu vystupujete a pokračujete dalšími příkazy není-li splněna podmínka na začátku, do cyklu nevstoupíte
Poznámka – cyklus s podmínkou na konci -
do cyklu se vstupuje vždy a cyklus proběhne minimálně jednou cyklus se opakuje, dokud nebude splněna podmínka na konci cyklu je-li podmínka na konci cyklu splněna, cyklus končí a algoritmus pokračuje dalšími příkazy
Poznámka – cyklus s určeným počtem opakování -
řídící proměnná cyklu má určenu počáteční hodnotu, koncovou hodnotu a krok o který se řídící proměnná zvětší nebo zmenší při každém průchodu cyklem cyklus končí, pokud řídící proměnná nabyla své koncové hodnoty
29
Příklad – informatika, ukázka algoritmu s užitím cyklu s určeným počtem opakování Vytvořte algoritmus který z N zadaných čísel vypočítá aritmetický průměr z kladných čísel a aritmetický průměr ze záporných čísel. Vstupná proměnné: Vstupní podmínky: Výstupní proměnné:
N – počet čísel X – načítané číslo N – přirozené číslo S1 – průměr ze záporných čísel S2 - průměr z kladných čísel
30
31
Příklad – biologie, ukázka algoritmu s užitím cyklu s podmínkou na konci Testujeme vstupní data Nemoc – hemofilie (krvácivosti) typu A. Chorobu způsobuje ztrátová mutace genu pro faktor krevní srážlivosti č. VIII. U mužů jsou dvě možnosti – muž má buď chromosom X s dominantní normální alelou H (píšeme to jako index u značky chromosomu, tedy XH ) a je zdráv, nebo mutovanou recesívní alelu h (Xh ) a je nemocen, protože tato alela je u muže jediná a vždy se projevuje. U žen jsou ovšem tři genotypy: XHXH (žena plně zdravá), XHXh (žena zdravá, ale přenašečka) a XhXh (žena nemocná, pro velkou vzácnost chorobné alely velmi vzácný případ). V praxi se můžeme setkat s následujícími případy (rodinami): 1.
2.
Rodiče: XHY x XHXh - zdravý muž si vezme přenašečku. Budou mít gamety XH, Y x XH, Xh. Polovina dcer zdravých, polovina přenašečky a polovina synů zdravých, polovina nemocných: XHXH ; XHXh ; HY ; Xh Y. Rodiče: Xh Y x XHXH - nemocný muž si vezme zdravou ženu. Budou mít gamety: Xh, Y x XH, XH. Všechny dcery přenašečky s jedním X od otce a všichni synové zdravý s X od matky a Y od otce: XHXh ; XHY. V třetím (vzácném) případě si vezme nemocný muž ženu přenašečku. Jen v takové rodině se může narodit postižená dcera.
Další možnosti jsou ukázány ve vývojovém diagramu
32
33
Příklad – chemie, ukázka algoritmu s užitím cyklu Důkaz škrobu a neznámého sacharidu Škrob je produktem fotosyntézy rostlin. Ukládá se jako zásobní látka zejména v hlízách, semenech a plodech. Z těchto částí rostlin se také škrob získává. Škrob je makromolekulární látka složená z amylopektinu a amylosy.
34
35
5. Závěr V závěrečné práci jsem se snažil ukázat jeden z možných postupů při výuce v různých předmětech. Algoritmizace úloh může propojit další předměty s informatikou. Zjistil jsem, že algoritmizace je důležitým, ale velmi náročným postupem. Zvláště pro humanitně zaměřené vyučující je tento způsob myšlení většinou obtížný a mnohdy i těžko realizovatelný. Chtěl jsem alespoň částečně nastínit možnost algoritmického zpracování úloh a to i v předmětech, kde to není obvyklé. Můj původní záměr, algoritmizace a programování na gymnáziu by svým rozsahem a náročností přesáhl obsah této závěrečné práce. Proto jsem problematiku zúžil na algoritmy a algoritmizaci se zaměřením na další předměty, mezipředmětové vztahy a ukázky užití v několika předmětech. V některých předmětech jako jsou matematika, fyzika, chemie nebo informatika se algoritmické myšlení (vstup – zpracování - výstup) podvědomě promítá do myšlení vyučujících i žáků. Také navrhované zpracování úloh pomocí vývojového diagramu se ukázalo jako vhodné, názorné a snadno pochopitelné pro vyučující i žáky. V ukázkách z dalších předmětů jsem narážel u většiny vyučujících na problém správně pochopit a následně algoritmicky danou úlohu a problém zpracovat. Všichni zúčastnění se však shodli na tom, že algoritmický zápis je velmi přehledný, názorný a v praxi použitelný. Ne všechny předměty a úlohy jsou pro algoritmizaci vhodné. Největší problémy pak mohou nastat v obsahově rozsáhlejších úlohách, úlohách, kde nelze přesně specifikovat vstup nebo výstup nebo v úlohách, které mohou mít složitější návrh řešení. Hlavními důvody, proč algoritmizovat a proč algoritmicky přemýšlet jsou podle mého názoru zejména: - nutnost správně pochopit řešení úlohy a problémů, které mohou nastat - potřeba podrobně analyzovat vstupní a výstupní data - logicky řešit a zpracovat problém - přehledně a srozumitelně zapsat řešení - možnost graficky znázornit řešení pomocí vývojového diagramu - možnost snadno modifikovat algoritmizované úlohy Pokusil jsem se ukázat jednu z cest, jak aplikovat do výuky mezipředmětové vztahy. Ukázky užití by pak mohly být návodem jak algoritmizovat úlohy v různých předmětech. Zvládnutí základů algoritmizace a tvorby vývojových diagramů by mělo být snadné a jednoduché, pokud bude mít vyučující snahu a chuť zkusit nové metody ve výuce. Zavádění nových metod do výuky je poměrně náročné a někdy i komplikované. Pokud se někdo rozhodne zkusit tento způsob řešení úloh, určitě obohatí o nový způsob myšlení nejenom sebe ale i své studenty.
36
6. Literatura GABČO, P. Informatika a výpočetní technika. Praha: SPN, 1989, ISBN 80-04-24821-4. HVORECKÝ, J., FRANEK, M. Algoritmy pro IV. ročník gymnázií. Praha: SPN, 1987. MOLNÁR, Ľ., FRANEK, M. Algoritmy pro III. ročník gymnázií. Praha: SPN, 1986. PŠENČÍKOVÁ, J., Algoritmizace. Kralice na Hané: Computer media, 2007, ISBN 80-86686-80-9. NOVÁK, J. Doporučení pro úpravu závěrečných prací (Diplomová práce). Brno: MZLU, 2006 WRÓBLEWSKI, P. Algoritmy : datové struktury a programovací techniky. Brno: Computer Press, 2004. ISBN 80-251-0343-9.
