Algoritmus

Pojem algoritmu je s informatikou spojen už od počátku. Co to ale algoritmus je? Pojďme si nejdřív s pomocí příkladů, které všichni známe, vybudovat nějakou základní intuici.

Jedním z příkladů algoritmu je recept, který jsme snad alespoň jednou viděli všichni. Recepty (pracovní postupy), které nám říkají, jak vstup (suroviny) pomocí přesných kroků přetvořit do výstupu (dobrého jídla). Podobným příkladem algoritmu může být třeba LEGO. Každá stavebnice přijde rozložená na jednotlivé dílky (vstup), které pak podle jednotlivých kroků návodu skládáme dohromady (výstup).

Není však nutné, aby výsledkem algoritmu byla nějaká složenina, algoritmus lze použít i k reprodukci. Možná na první pohled ne úplně typickým příkladem je notový záznam. Ten je vždy určený nějakému hlasu nebo jinému hudebnímu nástroji, s jehož pomocí následně noty hrajeme, abychom slyšeli výstup/výsledek, danou skladbu.

U všech příkladů, které jsme si právě ukázali, najdeme společné znaky. Vždycky pracujeme s nějakým vstupem, ať už jsou to suroviny, dílky stavebnice nebo hudební nástroj, a ke každému algoritmu máme nějaký předem definovaný výstup, ať už jídlo, složenou stavebnici či krásnou skladbu. Samotným algoritmem pak myslíme danou posloupnost kroků, které musíme vykonat, abychom ze vstupu dostali výstup.

Vlastnosti algoritmu

Teď, když jsme si několik příkladů algoritmu ukázali, se nad nimi pojďme zamyslet trošku hlouběji. Řekli jsme si, že takový kuchyňský recept může být příkladem algoritmu, protože s takovým receptem jsme se snad každý setkali, někteří podle něj dokonce i nějaké to jídlo více či méně úspěšně připravovali. Ve skutečnosti jsi ale byl svědkem redukce, jak v informatice (matematice) říkáme převedení jednoho problému na jiný. Naše chápání algoritmu je teď úzce závislé na pojmu receptu, tudíž logicky vyvstává otázka, co je to recept?

Pečeme chleba

Kdybychom chtěli upéct chleba podle receptu, který má v seznamu surovin uvedeno mouka, tak nám existence receptu práci moc neulehčí. Kolik mouky do chleba přijde? A jaký typ mouky máme použít? To z jednoho slovíčka nezjistíme a chleba tak těžko upečeme. Naopak pokud by náš recept vyžadoval konkrétní značku mouky koupenou v konkrétním obchodě v jediném městě na druhém konci republiky ve čtyři hodiny ráno, budou naše vstupy zase (zbytečně) příliš svazující. Od receptu tudíž požadujeme jasně definované vstupy, tedy v případě mouky typicky hmotnost a druh, při zachování jisté obecnosti. To se projeví tak, že náš nutně nezajímá značka mouky, ani to, kdy a ve kterém obchodě jsme ji koupili.

Neméně důležitý je samotný pracovní postup, který ze surovin (vstupu) vytvoří chleba (výstup). Jak jsme si řekli, tento postup se skládá z jednotlivých kroků, které musí být při jistém stupni volnosti jasně definovány. V přípravě námi pečeného chleba dojde k momentu, kdy budeme muset smíchat všechny suroviny dohromady. Smíchat má jasný význam, ale zároveň nám dává dost prostoru, abychom se rozhodli, zdali použijeme vlastní ruce nebo vařečku. Naproti tomu se při přípravě chleba nevyhneme použití kvásku, ale takové zadělání kvásku je pojem, který nemusí být především začínajícím pekařům jasný, a je proto potřeba mít předem jasno v tom, jaké kroky máme v receptu k dispozici. Jednoznačná musí být i posloupnost jednotlivých kroků, nemůže se nám stát, že bychom uprostřed provádění algoritmu nevěděli, jak pokračovat dále. Koneckonců většinu algoritmů dnes provádějí počítače a ty přemýšlet neumí, naopak příkazy umí provádět velice rychle.

Pokud použijeme předepsané suroviny a provedeme všechny kroky receptu, měli bychom skončit s hotovým chlebem.

Algoritmus podruhé, tentokrát teoreticky

Shrňme si všechno, co jsme si řekli výše ještě jednou, tentokrát bez kuchařské omáčky kolem.

Algoritmus je posloupnost kroků, které nám ze vstupu udělají výstup a která splpňuje několik dalších podmínek. Algoritmus musí být obecný, musí být konečný, jednoznačný a korektní. Pojďme si tyto čtyři vlastnosti rozebrat.

První podmínkou, kterou na algorimus klademe, je obecnost. Ta nám říká, že algoritmus by měl být schopen řešit nějaký problém, ne nějakou jednu konkrétní podobu. Tedy pokud budeme mít algorimus pro hledání kořenů kvadratických rovnic (tj. ax² + bx + c), chtěli bychom, aby fungoval pro libovolnou volbu koeficientů a, b, c, a nikoliv jen pro případy, kdy se první dva rovnají jedné a c nule.

Druhou vlastností je konečnost. Tuto podmínku klademe na posloupnost kroků, abychom zajistili, že při správném vykonávání kroků dostaneme nakonec výsledek. V případě, že by posloupnost kroků byla nekonečná, nemá smysl se o výstupu vůbec bavit, protože se k němu nikdy nedostaneme.

Další podmínkou je jednoznačnost. Ta požaduje, aby v každém kroku bylo jasně určeno, jak bude výpočet pokračovat, respektive jaký krok bude následovat. Zároveň nám z této vlastnosti plyne, že i význam / akce odpovídající krokům musí být jasně daná. Kdyby postup nebyl jednoznačný, dostali bychom se do podobné situace, jako kdyby někdo vytrhl několik stránek návodu pro LEGO. Z těch následujících bychom se asi dozveděli, k čemu máme dojít, ale nevěděli bychom jak.

Poslední vlastností je korektnost. Ta požaduje, aby algoritmus, který dostane validní vstup, vyprodukoval správný (korektní) výsledek, tedy odpovídající výstup. Důvod, proč po algoritmu tuto vlastnost vyžadujeme, je snad nasnadě.

Teď když jsme si popsali algoritmus a jeho vlastnosti, pojďme se podívat na několik různých druhů zápisů algoritmů, se kterými se můžeme setkat.

Zápisy algoritmu

V úvodu textu jsme už o několika podobách zápisu algoritmů zmínili; mluvili jsme o receptech, o notách a LEGO návodech. Všechny tři příklady jsou shodou náhod zapsány úplně jiným způsobem. Zatímco recept máme popsaný běžným jazykem a je alespoň teoreticky obecně srozumitelný, notový zápis bude pro mnohé oříšek. Naopak návod k LEGO je tak plný obrázků, že snad ani nevyžaduje gramotnost. Neměli bychom zapomenout na programy, které tvoří kategorii samy o sobě. Pojďme se u každé kategorie na chvíli zastavit.

Slovní zápis

Slovní zápis algoritmu je jedním z nejpřístupnějších, protože používá běžnou řeč, kterou se lidé dorozumívají mezi sebou. To s sebou nese i jistá rizika, především co se jednoznačnosti týče. Oproti jiným způsobům zápisu může být tento zápis mnohem delší.

Obrázky a diagramy

Ne nadarmo se říká, že obraz někdy vydá za tisíc slov. I algoritmy můžeme zapisovat graficky; obrázkové návody už jsme si zmínili, ale můžeme sem zařadit i diagramy.

Doménově specifické

Jak jsme si již řekli, notový zápis je způsobem zápisu algoritmu, který je poněkud specifický. Stejně doménově specifickým zápisem je třeba matematický zápis (i když u něj by jeden doufal, že mu bude rozumět o trošku více lidí).

Pseudokód a programy

Poslední kategorií, které jsme se doposud vyhýbali, jsou programy a různé pseudokódy. Teoreticky bychom tuto kategorii mohli schovat pod doménově specifické zápisy, na stranu druhou už jen programovací jazyky jsou tak širokým tématem, že mi přijde vlastní kategorie zaslouženou.

Programem se typicky myslí nějaký algoritmus zapsaný v konkrétním programovacím jazyce. Program se skládá ze sekvence příkazů daného programovacího jazyka, přičemž je jasně specifikováno, co má počítač při kterém příkazu vykonat. Takto zapsaný algoritmus jsme pak schopni spustit na patřičně vybaveném počítači.

Pseudokódem pak myslíme zápis, který připomíná způsob, jakým píšeme programy v programovacích jazycích, ale oproti nim si dovolujeme odhlédnout od nedůležitých detailů. Například pokud mám algoritmus skládající se z mnoha kroků, přičemž jedním z nich je seřazení nějaké číselné frekvence, při popisu algoritmu pseudokódem v odpovídajícím kroku uvedeme, že sekvenci setřídíme. V běžném programovacím jazyce bychom museli použít konkrétní třídící algoritmus/funkci. Z toho plyne i trošku jiný účel využití těchto dvou zápisů; pseudokód typicky použijeme tam, kde chceme demonstrovat myšlenku algoritmu, program pak když chceme, aby jej počítač provedl.