Algoritmus

Termín "algoritmus" (anglicky: algorithm) je prý poměrně nedávného data - údajně vděčí za svůj vznik předvolební kampani současného amerického prezidenta. Alespoň tak to tvrdí někteří všímaví novináři, kteří si na jednom méně formálním předvolebním večírku s improvizovanými hudebními vložkami povšimli, že je to právě budoucí viceprezident Albert Gore, kdo umí nejlépe "tvrdit muziku". A tak si dali dvě a dvě dohromady a došlo jim, že asi má ten správný Al-Gore-rhytmus.

Ve skutečnosti se ale termín "algoritmus" zrodil přeci jen o něco dříve a za svůj tvar vděčí jménu arabského matematika Muhammada ibn Musy ibn Abdallaha al Chorezmího, který žil na přelomu osmého a devátého století našeho letopočtu na území dnešního Uzbekistánu. Al Chorezmí se zabýval tím, co se dnes označuje jako aritmetika, zasloužil se například o významné rozšíření postupů (algoritmů) aritmetických výpočtů v poziční soustavě a byl také prvním, kdo veřejně publikoval základy aritmetiky.

Ve středověku pak termín "algoritmus" prošel mnoha deformacemi svého významu, aby teprve ve dvacátém století doznal velké renesance. Za svůj vstup do novodobé terminologie vděčí především monografii ruského matematika Markova, která nesla příznačný název: "Teorie algoritmů".

Co si ale správně představovat pod pojmem "algoritmus"? Co je, a co naopak není algoritmem?

Pro poměrně přesnou odpověď by bylo třeba jít do oblasti teorie a využít takových věcí, jako je ekvivalence různých formálních výpočetních modelů (jakými jsou například Turingovy stroje, Markovovy algoritmy, lambda kalkulus apod.). Na neformální úrovni, na jaké se pohybujeme v tomto seriálu, je možné si obsah pojmu "algoritmus" přiblížit následujícím postupem:

• Nejprve je třeba mít nějaký problém, který chceme vyřešit. Od takovéhoto problému je vhodné očekávat, že je dostatečně přesně definován, aby mělo vůbec smysl začít uvažovat o jeho řešení. Dále je třeba požadovat, aby se problém v průběhu svého řešení významněji neměnil, a konečně to, abychom vůbec byli schopni jeho řešení rozpoznat - tedy říci, zda určitý výsledek je řešením problému či nikoli. Příkladem problému může být nalezení součtu dvou zadaných čísel, řešení diferenciální rovnice, výpočet odmocni ny čísla 2 s přesností na zadaný počet desetinných míst, odpověď na otázku, zda daný program je správný, odpověď na otázku, zda existuje vítězná strategie v šachu, apod.
• Dále je třeba mít k dispozici nějaký nástroj, který chceme k řešení problému použít. Tímto nástrojem může být něco nehmotného, například nějaký matematický aparát (např. běžná aritmetika, budeme-li řešit problém nalezení součinu dvou čísel), nebo naopak něco hmotného - například počítač (budeme-li počítat odmocninu z čísla 2 s přesností na požadovaný počet desetinných míst apod.).

Pak už je možné dospět i k představě samotného algoritmu jako přesného postupu při použití zvoleného nástroje k řešení daného problému. Pokud máme například za úkol vynásobit dvě čísla a jako nástroj k tomu můžeme využít matematický aparát běžné aritmetiky, pak algoritmem bude postup násobení dvou čísel. V případě, kdy k řešení využijeme jako nástroj počítač, bude konkrétním vyjádřením algoritmu program, který pro takovýto počítač sestavíme.

Na algoritmus jako takový se ovšem kladou i některé omezující podmínky. Například ta, že by měl být deterministický: na stejný vstup (resp. na stejné výchozí podmínky) by měl reagovat vždy stejně a v každém jeho kroku by měl být vždy jednoznačně definován i krok následující. U skutečného algoritmu tedy není možné, aby jeho další postup (další krok) závisel na náhodě, na subjektivním rozhodování člověka apod. Další podmínkou, která se na algoritmus obvykle klade, je, aby skončil v konečném čase, resp. po provedení konečného počtu kroků. Algoritmem v pravém slova smyslu tedy nejsou takové postupy, které neskončí v konečném čase - ani takové, u kterých nevíme, kdy je "utnout".

Například kdybychom chtěli zjistit, zda se v desetinném rozvoji (tj. v desetinné části) druhé odmocniny čísla 2 vyskytují tři po sobě jdoucí číslice 7, nejspíše bychom využili program, který odmocninu ze dvou počítá na počítači. Takovýto program je schopen spočítat tuto odmocninu s přesností na tolik desetinných míst, kolik si jich zadáme, a to v konečném čase. V našem případě bychom jej ale museli nechat puštěný trvale a čekat, dokud v průběžně vypočítávaném desetinném rozvoji "nevylezou" tři po sobě jd oucí číslice 7. Ale jak dlouho bychom měli čekat? Pokud hledané trojčíslí nalezneme, můžeme program zastavit a odpovědět na původní problém kladně. Ale když budeme čekat například celý den, a tří toužebně očekávaných číslic se nedočkáme? Máme potom právo program zastavit? Vždyť by to mohlo být například jen několik sekund předtím, než by nám hledané číslice našel! Ovšem v přesně stejné situaci bychom byli i v případě, kdybychom program nechali běžet týden, rok či ještě déle. Nikdy bychom nevěděli, zda prog ram, hledající řešení, můžeme zastavit, či nikoli. Takovýto postup řešení proto není algoritmem.