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


Vývojové diagramy

Z Informatika pro každého
Přejít na: navigace, hledání
Co je to algoritmus · Programování

TODO: HODNĚ tady uber matematiky, resp. přidej jiných příkladů

ikona boxu
Co se naučíš:
  • Vědět, k čemu je vývojový diagram dobrý a v odpovídající situaci ho použít.
  • Číst hotový vývojový diagram a pracovat podle něj.
  • Vytvořit či upravit vývojový diagram.
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/Algoritmus/Vývojové diagramy/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

Výstupy podle RVP:
  • Po...

V této hodině se žáci podrobněji seznámí s vývojovými diagramy. Jejich použití je intuitivní, při jejich vytváření ale většina žáků ze začátku chybuje.

Vývojové diagramy jsou způsobem zápisu algoritmu. Zároveň je využijeme jako záminku k rozvoji pokročilejších dovedností jako např. zjistit, co vůbec daný postup dělá a co je jeho smyslem.


Tato hodina je velmi přímočará: učitel představí diagramy. Žáci potom podrobně zkoumají jeden konkrétní příklad, jeden sami vytvoří (na počítači), vyzkouší hodnotit jiné diagramy a na závěr ještě jeden drobný diagram vytvoří.

Přirozený jazyk mnohdy není ideálním nástrojem pro popis pracovního postupu. Jeho interpretace je obtížná a jazyk sám často umožňuje nepřesné vyjadřování. To je v životě mnohdy praktické, ale pro algoritmy se to vůbec nehodí. Podíváme se proto na dva jiné způsoby popisu pracovního postupu: vývojové diagramy a potom na programování.

S vývojovými diagramy se běžně setkáš kdykoliv, kdy je třeba popsat postup, ve kterém bychom se při ručním provádění snadno ztratili.

Vývojový diagram vyřízení žádosti o informace, © Otevřená společnost o.p.s.

Vývojový diagram vyřízení žádosti o informace.gif

Toto schéma nepředstavuje algoritmus. Vidíš proč?

Schéma písně Hey Jude.jpeg

Jednoduchým příkladem vývojového diagramu může být rozhodovací strom.

Rozhodovaci strom priklad jazyky.svg

Příklad rozhodovacího stromu pro připomenutí

Rozhodovací strom je zjednodušeným případem vývojového diagramu. Princip ale zůstává stejný: Plníme instrukce v jednotlivých blocích a postupujeme po spojovacích čarách, dokud nedojdeme do konce. V rozhodovacím stromu jsme začali nahoře a bloky vždy obsahovaly otázku, na základě které jsme se rozhodli o dalším postupu. Vývojový diagram je o něco bohatší.

TODO: přináší tenhle kousek něco?: Vývojové diagramy jsou tedy další možností popisu pracovního postupu. Soustředí se na samotnou posloupnost kroků, nikoliv na metainformace (co to dělá, s čím, jak to funguje…). Tyto části zde někdy pro stručnost vynecháme, pokud to nebude bránit srozumitelnosti.

Vývojový diagram míchaná vajíčka.svg

Tento diagram ukazuje už dříve uvedenýTODO: odkaz.... WTF, KDE TO JE ?!?!?!?!?!?!?!? postup přípravy míchaných vajec. Srovnej oba popisy — dělají totéž? Vidíme nové tvary bloků, které nám usnadní čtení vývojových diagramů a tím pádem i porozumění samotným algoritmům.

  • Začátek a konec jsou označeny obdélníkem se zaoblenými rohy.
  • Do obdélníku píšeme příkazy neboli instrukce.
  • Kosodélník označuje příkazy vstupu a výstupu, tedy místa, kde postup přijímá či vydává informace nebo jiný materiál.
  • V kosočtverci jsou podmínky k rozhodnutí, kudy pokračovat. Rozhodovací podmínky znáš z tabulkového procesoru v souvislosti s funkcí [KDYŽ (případně IF).

Vývojové diagramy musí splňovat zásady, které asi očekáváš, např.:

ikona boxu
K čemu jsou ty tvary

Studenti by měli pochopit, že smyslem přiměřeně správného použití tvarů bloků v diagramech není tyranie učitele, ale nástroj k jejich lepší přehlednosti a tím i použitelnosti.

  • Začátek je v diagramu vždy právě jeden.
  • Z každého bloku (kromě rozhodovacího) vede jen jediná spojnice, aby bylo jasné, kudy pokračovat.TODO: jsem lajdák, tady není, kolik treda spojnic z podmínky, a co když je podmínka otázka, ha! ha?!
  • Spojnice vedoucí z rozhodovacího bloku musí být označeny (typicky ano-ne, pravda-nepravda, P-N, true-false, T-F, 1-0…), aby bylo jasné, kterou vybrat v jakém případě.
  • Spojnice nesmí začínat či končit „ve vzduchu“. Vždy vede z bloku do bloku, nebo se připojí na jinou spojnici.
  • U každé spojnice musí být jasný směr postupu.

Tato (a další podobná) pravidla usnadňují dodržení vlastností algoritmů, především jednoznačnosti postupu.

VD xkcd flowchart trap.png

Spojnice ve vývojovém diagramu mohou (na rozdíl od spojnic rozhodovacího stromu) vést i zpět na místa, kde už jsme byli. To nám dává možnost několikrát zopakovat stejné kroky, např. pravidelně míchat vejce, dokud nejsou hotová. Takové konstrukci říkáme cyklus. Je samozřejmě potřeba dát pozor na to, aby cyklus někdy skončil. Pokud se postup tzv. zacyklí, nikdy neskončí a není to algoritmus.

ikona boxu
Úloha: Korektura

Vyber si některý diagram z této stránky, najdi jeho nedostatky a uveď, jak ty nedostatky brání snadnému provedení postupu podle diagramu. Zkus daný diagram samostatně vylepšit (především co do formy, ale třeba tě napadne i obsahové vylepšení).

Řešení

Mezi typické chyby patří nerozlišování tvarů bloků, chybějící šipky a křížení čar, označení odpovědí „ano“ a „ne“ někde daleko od otázky (nejasný směr postupu), neoznačený začátek a konec…

I přes všechny tyto chyby jsou ovšem vývojové diagramy přehlednější, než textové popisy!

Postupy podle vývojového diagramu provádí zpravidla člověk, nikoliv počítač. Pravidla proto nejsou dodržována zcela striktně (i když technické normy pro vývojové diagramy existují). Především samotný obsah bloků závisí na oblasti použití postupu. Někde můžeme použít matematické zápisy, někde zdrojový kód jako v programování, někde ale musíme použít přirozený jazyk. Vývojové diagramy tedy pomáhají zajišťovat přehlednost a jednoznačnost postupu, ovšem elementárnost, konečnost a další podobné otázky musí ohlídat autor.

TODO: XXX srov: img vejce na tvrdo: jsou už dost tuhá? No, já to teda nepoznám :-)

Analýza existujícího diagramu

Příklad: Záhadný diagram

Podívej se na následující vývojový diagram.

VD Záhadný vývojový diagram.svg

ikona boxu
 

Rozlišovat přiřazení a porovnání v samotných vývojových diagramech by nebylo zcela nutné. Zmatek by ovšem nastal při pokusu něco skutečně naprogramovat. Proto pokládáme za lepší pro pořádek obě možnosti rozlišovat rovnou.

V informatice rozlišujeme různé významy „rovná se“. To dvojité (==) v podmínce (v kosočtverci) znamená porovnání, lze ho číst jako „Hodnota proměnné x je rovna hodnotě proměnné y.“ Z rozhodovacího bloku pokračujeme podle toho, jestli podmínka platí, nebo neplatí. Samo o sobě dvojité rovnítko nic nedělá.

Jednoduché rovnítko v příkazech dole znamená přiřazení. Čteme jej tedy např. jako „Do proměnné y přiřaď rozdíl y-x.“ Pokud bylo před provedením příkazu y==5 a x==2, platí po provedení příkazu y==3. Hodnota x se nijak nezmění. Mimo popisy postupů v diagramech či v programování na tomhle rozlišování tolik nezáleží, takže taky rovnítka nerozlišujeme.

Černý kroužek je spojka. Nedělá nic, jen spojuje přicházející čáry, pokračuje se z něj tou třetí.

ikona boxu
Úloha: Krokování

Co udělá daný vývojový diagram, pokud na začátku vložíme hodnoty x=12 a y=9?

TODO:

ikona boxu
Poznámky pro učitele

klidně to odkrokuj sám pro jeden příklad - máš tam děti, které jsou najednou mimo

proto taky není řečeno, co je ten postup zač
ikona boxu
Nápověda

Pokud o daném postupu dosud nic nevíme, nezbyde, než jej provést, neboli tzv. odkrokovat. Začni v počátečním bloku a krok za krokem postupuj podle diagramu s danými vstupními hodnotami. Neustále sleduj, ve kterém jsi bloku, a jaké jsou hodnoty jednotlivých proměnných. Vyplatí se zapisovat si jednotlivé kroky, nebo aspoň postupně hodnoty proměnných.

x y
12 9
3 9
3 6
  1. Začátek
  2. Načtení hodnot x=12 a y=9
  3. x==y neplatí
  4. x>y platí
  5. nová hodnota x: 3 (12-9)
  6. x==y neplatí
  7. x>y neplatí
  8. nová hodnota y: 6 (9-3)
  9. x==y neplatí
  10. x>y neplatí
  11. atd.

Řešení

Postup vytiskne hodnotu 3.

ikona boxu
Úloha: Smysluplné vstupy

Pro jaké vstupní hodnoty je postup algoritmem?

ikona boxu
Nápověda

TODO: bonus: v podstatě se ptáme na definiční obor funkce Proměnné x a y jsou patrně číselné. Pro vstupní hodnoty 12 a 9 jsme v konečném čase úspěšně dostali jednoznačný výsledek 3. Takže přinejmenším pro tyto vstupy postup algoritmem je. Jak to bude pro jiné vstupy? To je potřeba otestovat. Postupem času si vyvineš cit pro to, které hodnoty jsou podezřelé a vyplatí se na ně zaměřit. Jak pochodíme se dvěma stejnými čísly? Co když bude jedno z nich nula, co když jedna? Co záporná čísla? TODO: bonusová otázka:Co kdyby postup umožňoval i neceločíselné vstupy?

Zkontroluj samozřejmě všechny vlastnosti algoritmu. Brzy zjistíš, že jediný problém je pro některé vstupy s konečností.

Řešení

Postup skončí, pokud jsou obě vstupní hodnoty stejné, nebo pokud jsou obě kladné.

Pokud je aspoň jedno ze vstupních čísel záporné, bude se větší ze vstupů do nekonečna zvětšovat.

Pokud je menším ze dvou čísel nula, bude se donekonečna odečítat od většího čísla (jenže je to nula, takže bez efektu).

ikona boxu
Úloha: Účel algoritmu

Co ten algoritmusTedy daný postup s takovými vstupy, které nevedou k zacyklení. vlastně dělá?

ikona boxu
Nápověda

To je téměř detektivní otázka. Štěstí je, že už máš za sebou množství pokusů, takže máš dobrou představu, jak algoritmus pracuje. Pečlivě si uspořádej výsledky do tabulky, např.

x 12 13 14 15 9 12 12 12
y 9 9 9 9 12 10 11 12
Výstup 3 1 1 3 3 2 1 12

Formuluj hypotézy o vztahu vstupu a výstupu a systematicky je ověřuj. Když se z výsledků zdá, že by nějaká hypotéza mohla být pravdivá, podívej se na vývojový diagram, jestli dává hypotéza smysl i obecně.

Leccos mohou napovědět speciální případy. Co když jsou vstupní hodnoty stejné? Co když se liší o 1, 2, 3, …? Co když je jedna z nich 1, 2, 3, …?

Levý horní roh ještě systematičtější tabulky by vypadal takto:

  x
1 2 3 4 5 6
y 1 1 1 1 1 1 1
2 1 2 1 2 1 2
3 1 1 3 1 1 3
4 1 2 1 4 1 2

Všímej si: Co se opakuje? Co mají které hodnoty společného? Jak často se objevují nové hodnoty? Které hodnoty jsou nejčastější, které naopak nejvzácnější? Vidíš nějaké vzory? Dokážeš bez provedení algoritmu předvídat výsledek pro nějaký vstup? Jak? Při hledání pravidelností může pomoct barevné odlišování hodnot. Dost práce si ušetří ti, kdo ovládají podmíněné formátování.

TODO: bonus? Všimni si, že algoritmus skrytě využívá rekurzivního pravidla: A(x,y) je x, pokud x==y. Jinak platí, že A(x,y)=A( x-y,y) pro x>y, atd... (přehledněji !!) - Čili buď řešení hned vidí, nebo si úlohu převedu na menší a snazší


Řešení

Vývojový diagram zachycuje Eukleidův algoritmus pro hledání největšího společného dělitele dvou přirozených čísel.

Tvorba vývojového diagramu

ikona boxu
Úloha: Kořeny kvadratické rovnice

Vytvoř vývojový diagram pro výpočet kořenů kvadratické rovnice.

ikona boxu
Nápověda

V první řadě si práci rozděl na menší kousky. Je třeba vymyslet samotný postup a následně ho zapsat pomocí vývojového diagramu. Výhoda je, že postup na řešení kvadratické rovnice už ovládáš. Musíš si ho jen trochu promyslet — umět něco udělat ještě neznamená umět to dobře popsat.

  1. Ujasni si: co všechno je vstupem hledaného algoritmu? Co je výstupem?
V našem případě se jedná koeficienty rovnice, tedy o reálná čísla tradičně označená jako a, b a c, z nichž a je nenulové.
  1. Postup znáš. Zkus ho na nějakém příkladu a zapisuj jednotlivé kroky. Zvol si způsob, který ti nejlépe vyhovuje: slovní popis, vývojový diagram na papír či v počítači, nějaká varianta zdrojového kódu…
  2. Zápis rozšiřuj o jednotlivá rozhodnutí. Musíš pokrýt všechny možnosti, všemožné kombinace vstupních hodnot.
  3. Pokud je zápis hotový, otestuj ho. Podobně, jako jsme v předchozí úloze zjišťovali, co vlastně algoritmus dělá, teď zjištujeme, jestli to dělá správně.
  4. Pro tvorbu výsledného vývojového diagramu se dobře hodí např. Lucidchart. TODO: odkaž na nějaký návod co s lucidem, resp co obecně s jakýmkoliv SW