Vývojové diagramy
- Čí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.
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ě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).
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ší.
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.
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.
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.
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.
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í.
Co udělá daný vývojový diagram, pokud na začátku vložíme hodnoty x=12 a y=9?
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 |
| … | |
- Začátek
- Načtení hodnot x=12 a y=9
- x==y neplatí
- x>y platí
- nová hodnota x: 3 (12-9)
- x==y neplatí
- x>y neplatí
- nová hodnota y: 6 (9-3)
- x==y neplatí
- x>y neplatí
- atd.
Řešení
Postup vytiskne hodnotu 3.
Pro jaké vstupní hodnoty je postup algoritmem?
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).
Co ten algoritmusTedy daný postup s takovými vstupy, které nevedou k zacyklení. vlastně dělá?
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í
- 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
Prohlédni si následující diagram:
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?
- 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
Vytvoř vývojový diagram pro výpočet kořenů kvadratické rovnice.
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.
- 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é.
- 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…
- Zápis rozšiřuj o jednotlivá rozhodnutí. Musíš pokrýt všechny možnosti, všemožné kombinace vstupních hodnot.
- 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ě.
- Pro tvorbu výsledného vývojového diagramu se dobře hodí např. Lucidchart.
