Ji°φ Peterka

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.