Vývojové diagramy

Z Základy informatiky pro střední školy
Přejít na: navigace, hledání

Co je to algoritmus


ikona boxu
Co se naučíš:
  • Číst hotový vývojový diagram a pracovat podle něj.
  • Vědět, k čemu je vývojový diagram dobrý a v odpovídající situaci ho použít.
  • Vytvořit či upravit vývojový diagram.
ikona boxu
Návrh průběhu hodiny a metodické poznámky

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.

ikona boxu
UML Activity diagramy

Většina z vás nebude vývojové diagramy používat natolik intenzivně, aby bylo potřeba se učit přesné technické podrobnosti. Zde se seznamujeme s principem. Kdo se ale o informatiku zajímá vážnějí, může se místo vývojových diagramů pustit rovnou do UML Activity diagramů. Ty „umí“ několik užitečných věcí navíc (např. paralelismus), a také jsou skutečně používané v praxi. Jestli budete používat nějaký editor diagramů na počítači, můžete místo šablony flowchart volit právě UML Activity (jsou i další typy UML diagramů, ty ale nepopisují postupy).

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

Rozhodovaci strom priklad jazyky.svg

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

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

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. Možnosti vývojových diagramů jsou o něco bohatší.


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

Tento diagram ukazuje už dříve uvedený postup přípravy míchaných vajec. Srovnej oba popisy — dělají totéž?

Všimni si rozdílných tvarů bloků. Mají nám usnadnit čtení vývojových diagramů a tím pádem i porozumění samotným algoritmům.

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 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 práce s tabulkami v souvislosti s funkcí If, případně KDYŽ, IF nebo IF).

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

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


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?


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

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?

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



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

Shrnutí

ikona boxu
  • K přehlednému popisu postupů můžeme využít vývojové diagramy.
  • Podle vývojového diagramu se postupuje snadno, když je v každém místě jasné, kudy přesně pokračovat dál a co dělat. Dbáme proto na správné napojení čar, jednoznačné popisky, šipky určující směr postupu atp.
  • Pro tvorbu diagramů existují specializované aplikace.
  • Ke zkoumání neznámého postupu (nejen ve formě VD) můžeme využít systematické zkoušení různých vstupů, hledání pravidelností mezi výsledky a postupné zpřesňování hypotéz o vztahu vstupů a výstupů.

Další úlohy

Vylepšení vývojového diagramu

ikona boxu
Úloha: Status žáka o prázdninách 2020

Prohlédni si následující diagram:

Decision tree MSMT 2020.jpg

Najdi, co by na něm šlo vylepšit, a uprav jej. Jestli usoudíš, že se úpravy nevyplatí, můžeš také vytvořit diagram zcela nový.

Možná se ukáže, že diagram pro tento případ není nejvhodnější. Jakými jinými způsoby bychom mohli pomoci rozhodování znázornit?

ikona boxu
Nápověda
  • Zkus si diagram několikrát různě projít. Zaznamenávej si potíže, které se přitom objeví.
  • Postupně prober všechny možnosti, které připadají v úvahu. Zkus je uspořádat podle sebe, a z toho potom vytvořit lepší diagram.

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.