Algoritmy

Počítač je neiniciativní, vše co chceme aby provedl, mu musíme nařídit. Práci počítači nařizujeme programem, tj.:

Vytvoříme posloupnost, která v každém okamžiku říká, jak pokračovat dále.

Nazýváme ji algoritmus.

Příklady algoritmů známe i z běžného denního života, aniž bychom si to uvědomovali.

Příklady takových algoritmů:

Postupy pro:

o zavěšení obrazu na stěnu,

o sečtení nebo násobení dvou čísel.

o použití hasicího přístroje,

o vyhledání knihy v knihovně.

Úkol „uvař čaj“:

o vezmi konvici na vaření vody

o přistav konvici pod vodovodní kohoutek

o není-li konvice plná, nech přitékat vodu

o jestliže je konvice plná, zastav vodu

o postav konvici s vodou na oheň

o nasyp do šálku čajové lístky

o nevaří-li se voda, nech konvici na ohni

o pokud se voda vaří, přelij čajové lístky v šálku vařící vodou

o nech čajové lístky vyluhovat

o nasyp do šálku cukr a zamíchej

Eukleidův algoritmus

Autor jej používal ve 3. století před naším letopočtem ke zjišťování největšího společného dělitele dvou přirozených čísel A, B (v dalším použijeme NSD(A,B) pro stručnější zápis).

Máme např. dvě čísla A = 42 a B = 28. Máme nalézt největší takové celé číslo, které beze zbytku dělí jak 42 tak 28 - NSD(42,28). Číslo 42 má dělitele 1, 2, 3, 4, 6, 7, 14, 21. Projdeme-li je od největšího, pak 14 dělí i č. 28. Číslo 14 je tudíž NSD(42,28). Ale zkusme tímto postupem najít NSD čísel 5418 a 2365. Asi bychom si pořádně zahřáli tužky. Neméně pracné by bylo i hledání NSD pomocí rozkladu na prvočinitele, jak známe (možná) z matematiky.

Euklides popsal způsob, podle kterého může najít NSD libovolných dvou čísel každý, kdo umí odečítat a porovnávat čísla. Nemusí umět dělit, ani nemusí vědět, co je to dělitel. Pouze postupuje podle návodu (algoritmu ):

Vyjděme od dvojice čísel A, B. Vždy, když máme dvojici tvořenou různými čísly, vytvoříme dvojici novou tak, že vezmeme menší z čísel staré dvojice a rozdíl těchto čísel. Opakujeme tak dlouho, až budou obě čísla stejná. Toto stejné číslo je NSD(A,B).

Např. (42, 28), (28, 14), (14, 14) NSD(42, 28) = 14

nebo (5418, 2365), (2365, 3053), (2365, 688), (688, 1677), (688, 989), (688, 301), (301, 387), (301,86), (86, 215), (86, 129), ( 86, 43), ( 43, 43)

NSD(5418, 2365) = 43

Našli bychom určitě mnohé další. Všimněme si, že je můžeme rozdělit do dvou skupin:

numerické a nenumerické

Ze školy jsou nám bližší spíš numerické.

Základní prvky, z nichž se algoritmus skládá:

proměnné – symbolicky pojmenované údaje, které se při zpracování nahradí konkrétními hodnotami, což mohou být texty, čísla, obrázky, schémata, počítačové soubory dat atd. Proměnné mohou být vstupní, pracovní a výstupní.

začátek algoritmu – počáteční bod, od nějž začíná zpracování

konec algoritmu – konečný bod, na němž po vytvoření výsledků zpracování dále nepokračuje, ukončuje algoritmus

kroky algoritmu – jednotlivé přesně vymezené a oddělené operace, které předepisují úkony, prováděné s proměnnými

podprogramy – předem definované části algoritmu, které figurují v algoritmu jako jeden krok, ale mají svou vlastní strukturu

podmínka – binární relace, případně zřetězení více relací pomocí logických spojek. Výsledkem vyhodnocení podmínky je hodnota TRUE (pravda) = podmínka je splněna nebo FALSE (nepravda) = podmínka není splněna.

rozhodování – postup, kdy na se základě vyhodnocení podmínky provádí větvení algoritmu. Při splněné podmínce se provádí jedna sekvence kroků, při nesplněné podmínce jiná sekvence kroků.

sekvence – posloupnost kroků po sobě jdoucích v uvedeném pořadí

cyklus – opakování kroku nebo sekvence kroků nul-krát až n-krát, dokud je (nebo není) splněna podmínka cyklu.

skok – přerušení přirozené posloupnosti průchodu algoritmem a přenesení zpracování na jiné místo označené návěštím.

Prostředky pro zápis algoritmu

Pro zápis algoritmů se používá mnoha technik. Nejpoužívanějším z nich věnujme nyní pozornost.

Slovní zápis

S algoritmy zachycenými slovním zápisem se setkáváme v běžném životě. Je to nejjednodušší způsob zápisu algoritmu. Příkladem takových algoritmů mohou být zákony, vyhlášky, normy, návody k použití spotřebních předmětů a podobně. Je třeba stylizovat text přesně a srozumitelně, používat přesné a jednotné terminologie, názorně vysvětlovat, případně text doplnit grafickými schématy, obrázky a podobně.

Slovní popisy jsou často nepřesné a nepřehledné. Neumožňují automatický převod do formy počítačového programu.

Symbolický jazyk

Je to prostředek, který připomíná programovací jazyk. Má přesně stanovenou syntaxi – způsob zápisu operací, formulace podmínek atd. i sémantiku – repertoár a význam operací, které lze použít.

Vzhledem k tomu, že tyto prostředky jsou silně formalizované, lze takto zapsaný algoritmus snadno převést do programovacího jazyka. Často se jako symbolický jazyk používá existující programovací jazyk, např. Pascal, doplněný slovním popisem.

Vývojový diagram

ČSN 36 9011 ISO 5807 „Dokumentační symboly a konvence pro vývojové diagramy toku dat, programu a systému, síťové diagramy programu a diagramy zdrojů systému“.

Typy symbolů vývojových diagramů

Spojnice

svislé nebo vodorovné čáry,

mohou se křížit nebo spojovat,

směr dolů a doprava je prioritní. V tomto případě není nutné použít šipky.

Šipky se používají jenom v případě, že tento směr je jiný, nebo když je třeba směr toku informace zvýraznit.