Algoritmizace 1. Úvod V dnešní době již počítače pronikly snad do všech oblastí lidské činnosti, využívají se k řešení nejrůznějších úkolů. Postup, který je v počítači prováděn nějakým programem se nazývá algoritmus a jeho tvorba algoritmizace.
Algoritmus Algoritmus je přesný popis, definující jistý proces, který vede od měnitelných vstupních údajů k žádaným výsledkům. Jinak řečeno - algoritmus je jednoznačný a přesný popis řešení problému. Algoritmus si lze představit jako sekvenci jednoduchých kroků, kdy v každém kroku víme, který krok bude následovat (nebo algoritmus již končí). Navíc je po konečném počtu kroků (a tedy do určité doby) získán výsledek. Každý algoritmus musí mít tyto vlastnosti: •
Determinovanost algoritmus musí být přesný, srozumitelný a jednoznačný, tj. v každém místě je jednoznačně určen další krok a pro stejná vstupní data musí poskytovat stále stejné výsledky. (Činnost algoritmu nesmí záviset na libovůli osoby ani na vlastnostech zařízení, které ho realizují).
•
Hromadnost algoritmus neslouží k řešení jen jedné úlohy, ale je řešením celé skupiny úloh, které se od sebe liší jen vstupními údaji. Vstupní údaje se mohou měnit v určitých mezích.
•
Resultativnost hledané výsledky musíme získat po konečném počtu kroků, algoritmus musí po konečném počtu kroků skončit.
Algoritmus by měl být také korektní (správný) – velmi obtížně dokazatelná vlastnost, která by měla prokázat, že pro všechna přístupná data vede postup ke správnému cíli. Některé problémy lze řešit více způsoby - různými algoritmy, které se mohou svým postupem značně lišit. Naší snahou je vybrat pro řešení problému co nejefektivnější algoritmus, který řeší problém v co nejkratším čase, je přehledný a srozumitelný. Algoritmy můžeme zapisovat slovně nebo graficky, například pomocí tzv. vývojových diagramů.
1
2. Algoritmizace Algoritmizace je při tvorbě programu postup pro počítač, kterým lze prostřednictvím algoritmu řešit nějaký problém.
Algoritmizaci lze rozdělit do několika etap: 1. 2. 3. 4. 5.
Definice problému Analýza úlohy Vytvoření algoritmu Sestavení programu Odladění programu
Definice problému V této etapě je třeba přesně formulovat požadavky, určit výchozí hodnoty, požadované výsledky, jejich formu a přesnost řešení. Analýza úlohy Při analýze úlohy si ověříme, zda je úloha řešitelná a uděláme si první představu o jejím řešení. Dále zjistíme, zda výchozí hodnoty jsou k řešení postačující a zda má úloha více řešení. Podle charakteru úlohy vybereme nejvhodnější řešení. Vytvoření algoritmu Sestavíme jednoznačný sled jednotlivých operací, které je třeba provést, aby byla úloha správně vyřešena. Algoritmus přesně popisuje postup zpracování daného úkolu, nedává však odpověď na daný problém, ale pouze postup, jak ji získat. Sestavení programu Na základě algoritmu řešené úlohy sestavíme program (zdrojový text) v konkrétním programovacím jazyce. Ze zdrojového textu se pomocí překladače do strojového kódu vytvoří spustitelný program. Dá se tedy říci, že dobře provedená analýza úlohy a algoritmizace daného problému je základním předpokladem sestavení programu pro počítač. Odladění programu Cílem odladění je odstranění chyb z programu. Nejčastější chyby jsou chyby v zápise, tzv. syntaktické - ty odhalí překladač. Závažnější jsou logické chyby, vyplývající z nesprávně navrženého algoritmu, nebo chyby, vzniklé špatným předpokladem v etapě formulace nebo analýzy úlohy - ty se projeví nesprávnou činností programu nebo špatnými výsledky - při odstraňování těchto chyb může pomoci ladící program (debugger) umožňující sledování aktuálního stavu proměnných a krokování. Teprve po odstranění všech druhů chyb můžeme program použít k praktickému řešení úloh. Algoritmus přepsaný do programovacího jazyku se nazývá počítačový program. Algoritmus by neměl být závislý na programovacím jazyku. Počítačový program je pak zápis algoritmu takovým způsobem, kterému rozumí počítač. Počítač sám má pouze omezenou skupinu příkazů, které umí vykonávat. Zápis z těchto příkazů tvořící program se nazývá strojový kód. Protože strojový kód je velmi složitý a vzdálený „lidskému chápání“, existují programovací jazyky. Ty obsahují takové příkazy, které je člověk tvořící program schopen snadno zadat, a zápis v těchto jazycích je pak převeden (přeložen) do jazyka počítače (strojového kódu). 2
3. Příklady slovního zápisu algoritmů Příklad 1: Algoritmus přípravy banánové bowle • •
•
Formulace problému Připrav banánovou bowli. Analýza úlohy Vstupní údaje: 60 dkg banánů, 20 dkg práškového cukru, 4 dcl vína, 0,25 l sifonu, 2 lžíce rumu Výstupní údaje: banánová bowle Analýza: aplikovat správný postup Sestavení algoritmu Slovní popis: 1. Oloupej banány 2. Rozkrájej je na tenká kolečka 3. Dej banány do mísy a zasyp cukrem 4. Přidej víno a nechej zchladit 5. Před podáním přidej rum a sifon
Příklad 2: Algoritmus zatloukání hřebíků • •
•
Formulace problému Zatluč hřebík do desky. Analýza úlohy Vstupní údaje: kladivo, hřebík, deska Výstupní údaje: hřebík zatlučen do desky Analýza: tlouct tak dlouho, dokud není hřebík zatlučen až po hlavičku Sestavení algoritmu Slovní popis: 1. Vezmi kladivo a hřebík 2. Přilož hřebík k desce 3. Uhoď kladivem na hlavičku 4. Je hřebík zatlučen? ANO - pokračuj bodem 5 NE - vrať se na bod 3 5. Ukonči činnost a odlož kladivo
Příklad 3: Algoritmus přechodu křižovatky, řízené semaforem • •
•
Formulace problému Přejdi na druhou stranu ulice. Analýza úlohy Vstupní údaje: přechod, semafor Výstupní údaje: pozice na druhé straně ulice Analýza: přes přechod se nechodí na červenou Sestavení algoritmu Slovní popis: 1. Dojdi až k semaforu 2. Svítí na semaforu červená? ANO - čekej, vrať se na bod 2 NE - pokračuj bodem 3 3. Přejdi přes přechod 3
4. Vývojové diagramy Jedním z mnoha způsobů znázornění algoritmů jsou vývojové diagramy. Je to grafické znázornění logické struktury řešeného úkolu. Ve vývojových diagramech se používá několik typů značek, z nichž každé je přiřazen určitý význam. Do těchto značek se vpisují operace nebo skupiny operací, které se mají provést.
Používané značky: začátek algoritmu (S – start, begin)
konec algoritmu (K – konec, end)
blok zpracování (do bloku zapisujeme akce, které se mají provést – např.: c:=a+b )
blok rozhodování (do bloku zapisujeme podmínku)
blok vstupu nebo výstupu (výstup na obrazovku nebo tisk)
blok pro cyklus se známým počtem průchodů
spojka (pro rozsáhlé diagramy, rozdělené do několika částí) 4
5. Vývojové diagramy k slovně zapsaným algoritmům Příklad 2: Algoritmus zatloukání hřebíků Slovní popis: 1. Vezmi kladivo a hřebík 2. Přilož hřebík k desce 3. Uhoď kladivem na hlavičku 4. Je hřebík zatlučen? ANO - pokračuj bodem 5 NE - vrať se na bod 3 5. Ukonči činnost a odlož kladivo
Vývojový diagram:
Příklad 3: Algoritmus přechodu křižovatky, řízené semaforem Slovní popis: 1. Dojdi až k semaforu 2. Svítí na semaforu červená? ANO - čekej, vrať se na bod 2 NE - pokračuj bodem 3 3. Přejdi ulici přes přechod
Vývojový diagram:
5
6. Základní algoritmické konstrukce Algoritmy lze teoreticky sestavovat libovolně, ale vzhledem k přehlednosti a úmyslně omezeným možnostem programovacích jazyků se musí dodržovat několik zásad: Algoritmus • •
má mít jeden začátek a jeden konec musí být složen pouze ze základních algoritmických konstrukcí Název popis
Diagram
Slovní vyjádření
Zápis v Pascalu
Sekvence je posloupnost příkazů, které se postupně provedou
Proveď příkazy P1, P2, P3.
begin P1; P2; P3; end;
Větvení umožňuje rozdělit program do 2 větví podle toho, zda je nebo není splněna podmínka
Jestliže platí podmínka P, proveď příkaz P1, jinak proveď příkaz P2.
if P then P1 else P2;
Větvení s prázdnou akcí umožňuje provést příkaz jenom tehdy, když je splněna podmínka
Jestliže platí podmínka P, proveď příkaz P1.
if P then P1;
6
Cyklus s podmínkou na začátku Když podmínka není na počátku splněna, cyklus nemusí proběhnout ani jednou.
Dokud platí podmínka P, prováděj příkaz P1.
while P do P1;
Cyklus s podmínkou na konci Tento cyklus musí proběhnout aspoň jednou.
Opakuj příkaz P1, až do splnění podmínky P.
repeat P1; until P;
Cyklus se známým počtem průchodů Cyklus proběhne n krát v obecném případě (pro i od m do n) proběhne (n-m+1) krát pokud m>n tak neproběhne ani jednou.
Pro i od 1 do n prováděj příkaz P1. for i:=1 během provádění cyklu řídící to n do P1; proměnná cyklu i postupně nabývá hodnot 1, 2, 3,...,n.
Pozn.: Vývojové diagramy cyklů mají jako jediné zpětnou větev. Standartní chybou u opakování s podmínkou bývá cyklus "s podmínkou uprostřed". Zpětná větev musí buď začínat hned za podmínkou, nebo se musí vracet těsně před podmínku.
7
