Vývojové diagramy a algoritmy

Historie

Algoritmy vznikaly už dávno před zkonstruováním prvních počítačů. Samotné slovo "algoritmus" vzniklo ze jména perského matematika, který žil v 9. století a jmenoval se Mohammed al-Khowarizmí (v latinském přepise Algoritmus). Zabýval se především pravidly pro aritmetické operace s čísly. Například Eukleidův algoritmus pro výpočet největšího společného dělitele dvou přirozených čísel pochází už z 4. až 3. století před naším letopočtem.

Úvod

Algoritmus

• jednoznačně stanovená posloupnost operací, které řeší daný problém

Použití:

• při konstrukci či analýze algoritmů
• pro dokumentaci, pro zachycení myšlenky

Účel:

• názornost a přehlednost pro pochopení při algoritmizaci
• jednoznačný převod z textu programu do vývojového diagramu
• spíše nevhodné při návrhu celého (složitějšího) programu

Vstupní údaje

• informace, ze kterých při řešení úlohy vycházíme, musí splňovat vstupní podmínku

Výstupní údaje

• nově získané informace, které jsou výsledkem realizace algoritmu, musí splňovat výstupní údaje

Vlastnosti algoritmu

• správnost: výsledek vydaný algoritmem musí být správný
• resultativnost: po konečném počtu kroků dospěje k řešení (vrátí třeba jen chybové hlášení)
• konečnost:algoritmus se nezacyklí
• determinovanost: v každém kroku je jednoznačně určen způsob pokračování práce algoritmu
• hromadnost: znamená, že algoritmus lze použít pro řešení obecné úlohy, tj. že nepopisujeme postup jedné úlohy, ale poslouží k řešení libovolné úlohy, která patří do jisté třídy úloh
• opakovatelnost: algoritmus vede vždy ke stejným výsledkům, jsou-li zadána stejná data

Algoritmus nemusí nutně vyžadovat vstupní údaje a vracet výstupní

Algoritmus lze vyjádřit:

• slovně: jednotlivé kroky postupu jsou vyjádřeny větami v přirozeném jazyce
• graficky: jednotlivé kroky jsou popsány grafickími značkami se slovním popisem
• matematicky: soustavou rovnic, vztahem mezi veličinami
• programem: jednotlivé kroky jsou popsány instrukcemi určitého procesoru

Programování = zakódování algoritmu do zvoleného programovacího jazyka

Algoritmizace = proces vytváření a sestavování algoritmů

Efektivnost algoritmu:

danou úlohu řeší více algoritmů, vybíráme efektivnějsší podle určitých kritérií:

• časové: úloha vyřešena v kratším čase
• paměťové: spotřeba paměti
• přehlednost, srozumitelnost: (důležité pro další vývoj a Úpravy)

Programovací jazyk = umělý jazyk jenž se používá pro definování sekvence programových příkazů, které lze zpracovat na počítači. Algoritmus má obecnou povahu, zatímco implementace algoritmu v určitém programovacím jazyku je ryze konkrétní.

Zdrojový kód Strojový kód = Soubor číslicových instrukcí, které je procesor počítače schopen rozpoznat a uskutečnit.

Dělení programovacích jazyků

Nižší programovací jazyky

jsou jazyky primitivní, jejichž instrukce odpovídají příkazům procesoru. To znamená, že procesor bude vykonávat ty instrukce, které programátor napíše. Jsou závislé na svém procesoru a nepřenositelné na jiný procesor.
V praxi to vypadá tak, že programátor musí vypisovat vše. Pak i jednoduchý program má neúměrně složitý zdrojový kód. Výhodou je, že programátor má takto přístup i k funkcím počítače, které by měl ve vyšším programovacím jazyce nedosažitelné. Lépe tedy využije jeho schopnosti.

Patří sem:

• strojový kód (to, co uvidíte, když otevřete obsah „exe“ souboru v textovém editoru)
• jazyk symbolických adres (Assembler) – je velice blízký strojovému kódu

Vyšší programovací jazyky

jsou podstatně srozumitelnější, jejich struktura je logická, nejsou závislé na strojových principech počítače. Do strojového kódu se převádějí kompilátorem (případně se rovnou spouštějí interpretrem). V praxi je vyšší programovací jazyk vše, co není Assembler (například jazyk C++, Pascal, Basic, Delphi..)

Programovací jazyky dále dělíme na :

• kompilované
• interpretované

Kompilované jazyky

jsou nejdříve celé přeloženy a až potom mohou být spuštěny. Jsou rychlejší, mají vyšší nároky na formální správnost kódu. Překládají se kompilátorem, výsledkem překladu je (většinou) .exe soubor. Patří sem většina klasických programovacích jazyků.
Teoreticky může mít jeden programovací jazyk verzi jak  interpretovanou, tak i kompilovanou.

Interpretované jazyky

jsou překládány až za běhu programu. Jsou pomalejší, ale nemají tak velké požadavky. Překládají se interpretrem, ten instrukce zároveň při překladu provádí. Hlavní nevýhodou těchto jazyků je, že se musejí vždy spouštět v interpretru. Do této skupiny patří například Basic, skriptovací jazyky (PHP, Python,Perl ...).

Další způsoby dělení programovacích jazyků

Programovací jazyky můžeme dále dělit na jazyky, které podporují:

• programování strukturované (např. Pascal)
• objektově orientované programování (OOP) – např. Visual Basic, Delphi

Etapy programátorské páce

1. Nápad - Nadšení, velké plány, představení problému
2. Analýza - Problém se ukazuje jako složitější, vystřízlivění, porobení problému důkladné analýze, vypracování základního algoritmu řešení, vybrání programovacího jazyka
3. Kódování - Programátoři zapisují algoritmy v programovacím jazyce
4. Ladění - Nalezení a oprava chyb v programu
5. Používání - Vlastní využívání programu
6. Modifikace - Úprava, vylepšení a rozšíření verze programu
7. Archivace - Vyřazení, nahrazení novými zásady pro návrh algoritmu (programu)

Základní pojmy

Syntaxe příkazu vždy popisuje, jak tento příkaz správně bez chyby vytvořit.
Sémantika popisuje význam tohoto příkazu.

Proměnná (variable) je objekt, který má pevně stanovené označení a nese určitou hodnotu. Tato hodnota se může v průběhu programu měnit. Pro označení proměnných se používají jména složená z písmen a číslic, první však musí být písmeno.
Konstanta (constant) je také pojmenovaný objekt určité hodnoty, na rozdíl od proměnné se hodnota konstanty nemůže měnit. Konstanta pi například může obsahovat hodnotu 3.14.
Proměnná může získávat hodnotu dvěma způsoby: načtením vstupní hodnoty pomocí vstupního bloku nebo přiřazovacím příkazem

Proměnná, která dosud nezískala žádnou hodnotu, má nedefinovaný obsah.

Přiřazovací příkaz je základem všech algoritmů zapsaných jak pomocí diagramů, tak i v libovolném programovacím jazyce. Syntaxe přiřazovacího příkazu je proměnná:=výraz. Symbol přiřazení se nachází uprostřed, často se bude jednat o znak :=. Výrazy mohou obsahovat konstanty i proměnné, aritmetické operátory, kulaté závorky. Základní aritmetické operátory jsou +,-,*,/.

Sémantika přiřazovacího příkazu je následující:
Nejprve se vyhodnotí hodnota výrazu na pravé straně přiřazovacího příkazu. Tato hodnota je pak přiřazena proměnné uvedené na levé straně příkazu. Předchozí hodnota této proměnné je nenávratně ztracena.

Příklad několika přiřazení (: a:=0 b:=a+5 c:=2*(b+4) a:=a+1 vysvětlení: do proměnné a je vložena hodnota nula, do b se přiřadí hodnota o 5 větší, tedy 5, v c bude 2*(5+4)=18 a nakonec do a bude přiřazena hodnota o jedničku větší, než má teď, tedy 1

Podmínka (condition) je logický výraz, jehož hodnotou je pravda nebo nepravda. Říkáme, že podmínka platí nebo neplatí.

Základní relační operátory jsou <,>,=,<=,>=,<>.
Ve výrazu lze použít proměnné, konstanty i kulaté závorky. Obecně v podmínce může být výraz vlevo i vpravo, navíc se dají sestavovat složené podmínky pomocí logických spojek. Toho si ale užijete až v konkrétním programovacím jazyce.
Sémantika je následující:
Nejprve se vyhodnotí podmínka. Pokud platí, provede se příkaz (nebo více příkazů) uvedený ve větvi označené symbolem +. Pokud podmínka neplatí, provede se příkaz (nebo více příkazů) uvedený ve větvi označené symbolem -. Příkazem uvnitř může být přiřazovací příkaz, vstup nebo výstup dat i další podmíněný příkaz. V posledním případě mluvíme o složeném podmíněném příkazu nebo prostě o podmínce v podmínce. Jedna z větví v rozhodovacím bloku může být prázdná, neobsahuje žádný příkaz. Obvykle se jedná o větev označenou -. Takový podmíněný příkaz nazýváme neúplný. Úplný podmíněný příkaz má v každé větvi alespoň jeden příkaz.

Příklad několika podmínek:
a=0
b>0
i=10
n<100
s>2*(i+j)
j<>0

Grafický zápis algoritmů

Pro znázornění algoritmů se používají grafické značky spojené orientovanými spojnicemi. Tvary a významy některých značek, které budeme při kreslení vývojových diagramů používat, jsou na následujícím obrázku.

Značky jsou spojeny šipkou. Značka začátku vývojového diagramu je vždy uvedena jako první. Dále následují další prvky podle řešeného problému. Vývojový diagram se prochází směrem shora dolů, ve směru spojovacích šipek. Posledním prvkem je značka konce vývojového diagramu. Většina diagramů obsahuje alespoň jeden blok pro vstup i výstup dat.

První diagram:

Příklady:
Sestavte algoritmus, který přečte čtveřici čísel a vytiskne číslo, které se rovná součinu součtu prvých dvou čísel a rozdílu druhých dvou čísel (např. pro vstupní data 4,2,3,7 bude výsledek -24)
Sestavte vývojový diagram pro výpočet obvodu a obsahu čtverce
Sestavte vývojový diagram pro výpočet průměru ze dvou čísel.

Větvení

I v poměrně jednoduchých případech jsou zapotřebí řídící struktury, které předepisují různé alternativy dalšího postupu vázané na splnění určité podmínky (tzv. větvení)
Větvení budeme předepisovat řídící struktorou, kterou nazveme podmíněný příkaz a jejíž vyjádření je na následujících obrázcích:



Řešený příklad: Sestavte algoritmus, který přečte dvě zadaného čísla a vytiskne větší z nich. V případě rovnosti vytiskne číslo jednou.
Příklady:
Sestrojte algoritmus, který vymění obsah dvou číselných proměnných.
Sestrojte algoritmus, který vymění obsah dvou číselných proměnných bez použití další proměnné. Řešení
Sestrojte algoritmus, kteý vytiskne absolutní hodnotu zadaného čísla. Udělej podle definice absolutní hodnoty
Sestrojte algoritmus, který načte tři čísla a vytiskne největší znich.
Je dáno přirozené číslo. Rozhodněte, zda je jednociferné, dvouciferné či víceciferné
Sestavte vývojový diagram, který pozdraví podle zadané denní doby vyjádřené v hodinách. Dopoledne do 12 hodin pozdraví Dobré dopoledne, do 18 hodin Dobré odpoledne, později Dobrý večer.
Sestavte vývojový diagram, který vypíše, kolik minut uplnynulo mezi dvěma časovými údaji, např. mezi 9:30 a 11:15 uplynulo 105 minut.

Cykly:

Pro výpočty realizované na počítačích je typické opakované provádění příkazů. Předepisujeme je řídícími strukturami, které nazýváme cykly.

Cyklus While (s podmínkou na začátku)

Základní řídící strukturu tohoto cyklu můžeme obecně vyjádřit příkazem
kde B je podmínka, při jejímž splnění se příkaz P opakuje (tento příkaz nazýváme tělem cyklu).
Cyklus končí (resp. se neprovede ani jednou), když podmínka B není splněna.

Řešený příklad: Sestavte algoritmus pro výpočet zbytku po dělení dvou přirozených čísel. (Využijte cyklus while.)

*Příklad: Určete počet cifer daného přirozeného čísla. (Určete i ciferný součet.)

Cyklus Repeat (s podmínkou na konci)  
Další často používanou řídící strukturou pro cyklus je příkaz


Řešený příklad:
Načítej čísla tak dlouho, dokud nebude zadána nula. Zadaná čísla sečti a vytiskni výsledek.


Příklad: Je dána posloupnost kladných celých čísel zakončená nulou. Určete, kolik je v ní lichých čísel dělitelných třemi.

Cyklus For (se známým počtem opakování)
Tento cyklus se používá pro daný konečný počet opakování určitého příkazu nebo sekvence příkazů. Počet opakování je dán tzv. řídící proměnnou ( I ).