Rozpoznávání algoritmů

Co se naučíš:

• Rozhodnout, jestli je daný postup algoritmem, tedy ověřit splnění jednotlivých nutných vlastností.
• Rozhodnout a posoudit, jestli je daný algoritmus také správný a obecný.
• Identifikovat a podle možnosti odstranit problémová místa (a tím udělat z pracovního postupu algoritmus).

Elementárnost

Každý algoritmus je napsán pro někoho nebo pro něco: pro automatickou pračku, pro čtvrťáka, pro automechanika atd. Elementárnost s tím úzce souvisí. Co je elementární pro Sherlocka, není elementární pro Watsona. Abychom mohli kontrolovat elementárnost, musíme vědět, kdo má algoritmus provádět.

Postupně probereme všechny úkony v popisu algoritmu a sledujeme, jestli jsou pro daného realizátora dost jednoduché na to, aby si s nimi věděl rady a to za všech myslitelných okolností (např. při různých hodnotách proměnných, i hodně vysokých, záporných…). Nejtěžší na kontrole elementarity instrukcí tak je ujasnit si, co všechno vlastně realizátor zvládá a co ne.

Proto je výhodné pracovat v ustáleném kontextu nějaké vymezené oblasti. I uzlování a skládání papíru má známé základní kroky a jejich pojmenování a z těch základních kroků jsou pak sestaveny složitější postupy. Také v případě programovacích jazyků jsou základní instrukce dobře známé. Jsou definovány tak jasně, že lze elementárnost zkontrolovat automaticky.

Pokud nějaká instrukce v návodu není elementární, je nutno ji podrobněji vysvětlit pomocí jednodušších (základnějších) instrukcí. Místo mocnění je třeba použít postupné násobení, pokud je násobení stále příliš složité, je třeba jej popsat pomocí sčítání. Pokud není jasné, jak hledat střed úsečky, je nutno vysvětlit jednotlivé kroky konstrukce, pokud není jasné, jak se dělá kruhový oblouk, je třeba vysvětlit i to.

Jednoznačnost

Jednoznačnost kontrolujeme také po jednotlivých instrukcích, je ale také potřeba zkontrolovat jejich návaznost. Každá instrukce musí být jednoznačná sama o sobě. Ve stejné situaci (při stejných hodnotách proměnných) musí vždy vést k témuž výsledku. To by nemělo být těžké ověřit, pokud jsou instrukce elementární. Poněkud záludná může být kontrola u popisů přirozeným jazykem, do kterého se snadno vloudí nejednoznačnost. Nestačí ověřit, že instrukci rozumíme a je nám jasné, co přesně znamená. Musí to být jasné i komukoliv jinému, kdo bude návod provádět, a navíc jeho interpretace musí být stejná jako naše.

Kromě samotných kroků algoritmu sledujeme i jejich návaznost. Musí být jasné kde začínáme, kam po jednotlivých krocích pokračujeme a kde končíme. Pokračování přitom musí být jednoznačné pro všechny možnosti (např. všechna ohodnocení proměnných). Nestačí říct, že když je diskriminant kladný, dostaneme dva reálné kořeny, je také třeba říct, co všechno se může stát, když kladný nebude.

Pokud narazíme na místo, které je nejednoznačné, musíme ho opravit. Je třeba se rozhodnout pro správný výklad (vzhledem k tomu, co má postup vůbec dělat), a podle toho návod přeformulovat, doplnit nebo jinak zpřesnit.

Víceznačnost dělá největší potíže při komunikaci přirozeným jazykem. Programovací jazyky a další způsoby komunikace informatiků proto bývají přímo navrženy tak, aby nejednoznačnosti ani obsahovat nemohly. V takovém případě opět ani není co kontrolovat.

Konečnost

Kontrola konečnosti je často nejtěžší. V jednoduchých případech není příliš co řešit, pro ty složitější si ukážeme jeden postup, který informatici rádi používají. Automaticky totiž konečnost ověřovat nelze.

Pokud algoritmus neobsahuje cykly ani rekurzi, jde o provedení konečného počtu instrukcí. Tím je ověření hotovo. Tak je to např. s hledáním kořenů kvadratické rovnice, s rozhodovacími stromy, s výdejem lístků z automatu.

Pokud mají případné cykly přesně omezený počet opakování, taktéž není co řešit. Máme nakapat 5 kapek proti kašli, přeplavat 40 bazénů, přehrát všechny tóny dané stupnice, sečíst všechny cifry přirozeného čísla, koupit letenky pro všechny účastníky výletu? To jistě nepotrvá nekonečně dlouho.

Přesnější podmínky

Abychom si mohli být výsledkem jisti, je třeba trochu opatrnosti. Hledáme veličinu, kterou budeme sledovat v nějakých definovaných uzlových bodech, které se po celou dobu běhu postupu opakují (např. na začátku každého opakování cyklu, před každou otázkou na myšlené číslo atp.). Veličina musí mít v těchto bodech vždy nižší hodnotu než minule. Navíc musí existovat mez, pod kterou už logicky klesat nelze (obvykle je to 0 nebo 1).

V matematice proberete přesnější podmínky takového „nárazu“. Například posloupnost 1, 1/2, 1/4, 1/8… svědomitě klesá a jistě nemůže klesnout pod nulu. Jenže konečná zjevně není. Jak to? Co ještě musí klesající veličina splňovat, aby nám posloužila pro ověření konečnosti pracovního postupu?

Řešení

Potíž je, že se neustále zmenšuje krok, o který veličina klesá. Klesání se sice nikdy nezastaví, ale stále zpomaluje. Tomu potřebujeme zabránit. Musíme např. požadovat, aby veličina klesla vždy aspoň o nějaký minimální krok. Takovou podmínku jednoduše splní veličina celočíselná, která musí klesnout vždy minimálně o 1.

Co když předchozí předpoklady neplatí? Typicky jde o případy cyklů, které končí splněním nějaké podmínky. Když cyklus začne, není jasné, kolikrát vlastně proběhne. Druhá možnost je rekurzivní volání. V takových případech musíme být důmyslnější. Hledáme nějakou klesající veličinuInformatici jí říkají „klesající míra“., tedy „něco, co se v průběhu algoritmu zmenšuje, až to jednou narazí na nějakou mez“. Když máme štěstí, je veličina zřejmá — např. když algoritmus postupně zpracovává nějaké informace, k jednou zpracovaným informacím už se nevrací.

• Hádání čísel: Možných čísel je omezený počet a každou otázkou z nich nějaké ubereme (i když není vždy jasné, kolik přesně). Jednou nutně dojdou, takže algoritmus musí skončit.

Uvedené příklady jsou poměrně jednoduché a konečnost těch algoritmů se zdá leckomu jasná. Existují ale i složitější případy:

Příklad: Collatzova domněnka

1. Vezmi přirozené číslo.
2. Pokud je číslo jedna, skonči.
3. Pokud je číslo sudé, vyděl ho dvěma,

   jinak ho vynásob třemi a přičti jedna.

4. Pokračuj krokem 2.

Např. pro úvodní volbu 3 dostaneme postupně hodnoty 10 → 5 → 16 → 8 → 4 → 2 → 1.

Je uvedený postup konečný pro libovolné přirozené číslo? Mnoho matematiků a informatiků se spolu s Lotharem Collatzem domnívá, že ano. Odpověď ale nikdo nezná. Jedná se o tzv. otevřený problém, tedy problém, jehož řešení neznáme. Fascinující přitom je, jak jednoduše je zadaný.

Kdo ví, třeba se ti povede ho vyřešit — buď dokázat, že vždy skončí, nebo naopak, třeba najít takové přirozené číslo, pro které neskončí. Najít tady nějakou klesající veličinu ale snad ani nezkoušej, zatím se to nikomu nepovedlo. Spíš pomůže, když přijdeš se zcela jinou myšlenkou.

Utěšující zpráva je, že problém nemá žádné přímé praktické využití.

Uvědom si, že nestačí fakt, že zkoumaný proces zatím ve všech pokusech opravdu skončil. Má-li být postup algoritmem, musí skončit pro každý povolený vstup. Kontrola pouze omezeného počtu případů se může snadno vymstít.

Úloha: Naivkova domněnka

Naivka si všimnul, že když začne s číslem 11 a přičte k němu dvojnásobek jeho pořadového čísla (tedy 2⋅1=2), dostane 13, z toho dostane 13+2⋅2=17, potom 17+2⋅3=23 — to jsou samá prvočísla!

Platí domněnka, že popsaným způsobem získaná čísla budou vždy prvočísla?

Nápověda

Vypadá to na matematický problém. Informatik ale nejdřív zkusí „hrubou sílu“ a spočte několik prvních čísel, aby se podíval, jestli to jsou opravdu prvočísla. Samozřejmě se mu nechce doopravdy počítat. Využij třeba tabulkový procesor nebo Python. Když už jsou čísla vysoká a prvočíselnost nepoznáš od oka, nech ji kontrolovat automaticky.

Řešení

Jedenáctý prvek posloupnosti je 121, což není prvočíslo. Domněnka tedy neplatí.

Rezultativnost

Rezultativnost úzce souvisí s konečností. Předně tedy zjistíme, jestli je postup konečný, a jestli ano, tak jestli před ukončením něco vrátí. Je ale třeba trocha pozornosti. Při zjišťování konečnosti se obvykle soustředíme na situace, kdy se postup ke skončení příliš nemá. Rezultativnost ale znamená vydání výstupu vždy, takže i při nějak předčasném ukončení.

Zajímavé je najít i neplánovaná ukončení. K těm dojde tehdy, kdy nějakou instrukci nelze provést. Robot těžko popojede o √(-1) nebo 42/0 metrů vpřed. Takový příkaz jej nejspíš zmate natolik, že přestane poslouchat úplně. Při takovém ukončení postupu často žádný výsledek nedostaneme. Takto ukončený postup není rezultativní, není tedy algoritmem a potřebuje opravit.

Správnost

Prokázat, že je algoritmus správný (tedy že odpovídá zadání) není vždy jednoduché. Jedna ze schůdných cest spočívá v prokázání správnosti mezivýsledků. Druhý krok úvahy potom správnost mezivýsledku zkombinuje s konečností: Jestliže je mezivýsledek v každém okamžiku správný, a algoritmus je zároveň konečný, musí algoritmus vydat správný výsledek.