Co je to algoritmus

Co se naučíš:

• Jmenovat výhody algoritmů.
• Umět vysvětlit význam vlastností algoritmů (co znamenají a proč jsou důležité).

Návrh průběhu hodiny a metodické poznámky

• Stručný průběh a poznámky
• Podrobný plán (příprava do hodiny)

Definice algoritmu

Z předchozích aktivit nám vyplynuly některé podmínky, které musí pracovní postup splňovat, abychom ho prohlásili za algoritmus:

1. Musí být popsaný. Jinak se nemáme o čem bavit.
2. Musí nám dávat nějaký výsledek. Jinak se vlastně nemáme proč o něm bavit.
3. Musí být složen z instrukcí tak základních, že je vykonavatel umí provést bez dalších otázek či přemýšlení. Nejde říct „slož čepici“, to by mohlo dopadnout všelijak. Pokud vykonavatel rozumí pojmům jako „na výšku“ či „vodorovná osa“, lze možná říct „otoč papír na výšku a přelož podle vodorovné osy“. Možná je ale nutné říct dokonce „otoč papír kratší stranou k sobě, vezmi nejvzdálenější okraj, přilož na nejbližší okraj a papír přitiskni ke stolu.“ A to pořád něco předpokládá, např. že vykonavatel pozná kratší stranu papíru (a samotný papír).
4. V každém okamžiku musí být postupem dané, kterou instrukcí se bude pokračovat. Nesmí to záviset na svobodném rozhodnutí vykonavatele. Postup se také nesmí „zaseknout“ kvůli neočekávaným okolnostem. Vždy musí být jasné, co dělat dál (nebo že je konec).

K tomuhle maličko přidáme, a dostaneme definici algoritmu:

Pamatuj si: Definice algoritmu

Algoritmus je pracovní postup, který má tyto povinné vlastnosti:

1. Rezultativnost. To znamená, že vždy vydá nějaký výsledek.
2. Finitnost (konečnost). To znamená, že někdy skončí. Jinými slovy, skončí po konečném počtu provedených kroků.
3. Elementárnost (jednoduchost) popisu. Algoritmus je popsán konečným počtem základních instrukcí. Tedy takových, o kterých je jasné, jak se provedou (a tedy neumožňují žádný osobitý výklad některého vykonavatele).
4. Determinovanost (jednoznačnost). Postup práce je jasně daný a vždy závisí pouze na popisu algoritmu a na vstupu („pracovní materiál“, ať už jde o vejce, nebo o informace, tedy nějaká čísla). Na průběh algoritmu nemá žádný vliv náhoda nebo svobodná vůle vykonavateleJaký je mezi tím vlastně rozdíl?.

Různá pojetí pojmu algoritmus

V běžné řeči a v různých učebnicích se setkáte s různě přísným pojetím pojmu algoritmus. Někdo požaduje splnění více z uvedených vlastností, někdo méně. Základní myšlenka je nicméně shodná. Algoritmus je lidsky (a tedy nepřesně) řečeno strojově proveditelný, spolehlivý a užitečný pracovní postup.

Determinovanost (jednoznačnost) algoritmů má zcela zásadní důsledek: Pro stejný vstup algoritmus vždy vydá stejný výstup. Nezáleží na denní době, počasí či náladě. Výsledkem sčítání dvou stejných čísel bude vždy stejný součet, výsledkem hledání cesty mezi dvěma body v mapě bude vždy stejná cesta. Uvedené vlastnosti tak společně zaručují právě tu hlavní a skvělou výhodu algoritmů, totiž že mohou být prováděny automatizovaně, bez dozoru, a přitom se můžeme spolehnout na výsledek. Uživatelé nemusí ani vědět, jak přesně fungují a co se v průběhu práce děje. Používají je jako tzv. černé skříňky (black box). Do skříňky vloží povolený vstup a na druhé straně vypadne odpovídající výstup s danými vlastnostmi. Co se děje uvnitř skříňky nemusíme vědět, což je často značné ulehčení situace.

Úloha: Rezultativnost vs. finitnost

Ty vlastnosti jsou si dost podobné. Neplyne konečnost z rezultativnosti? Nebo rezultativnost z konečnosti? Kdyby tomu tak bylo, mohli bychom definici algoritmu o jednu vlastnost zkrátit, což by všichni informatici a i studenti informatiky velmi ocenili. Plyne tedy některá z vlastností z té druhé?

Nápověda

Když se takhle ptáme, tak to asi nepůjde. Abychom nabyli jistoty, je potřeba najít protipříklady. Tedy postup, který je konečný a (aspoň někdy) nedá žádný výsledek, a (jiný) postup, který sice nějaké výsledky dává, ale nekončí.

Úloha: Různé pohledy na jednoznačnost

Řekli jsme, že z jednoznačnosti postupuPostup práce je jasně daný vždy závisí pouze na popisu algoritmu a na vstupu. plyne jednoznačnost výstupuPro stejný vstup algoritmus vždy vydá stejný výstup.. Dává to smysl: Kdyby se lišil výsledek jednoznačného postupu, musel by se postup v nějakém kroku lišit. To ale nemůže, protože je jednoznačný. Jednoznačný tedy musí být i výsledek.

Někdy se v definici algoritmu vyžaduje právě jednoznačnost výstupu (namísto jednoznačnosti postupu). Je to opravdu totéž? Jsou jednoznačné postupy právě ty, které dávají vždy stejný výsledek?

Nápověda

Z předchozího už víme, že jednoznačný postup dává jednoznačné výstupy. Zbývá určit, jestli také postupy, které pro stejný vstup dají vždy stejný výstup, mají také jednoznačný postup práce. Zkus najít protipříklad, tedy postup, který pro stejný vstup může probíhat několika způsoby, ale přesto dá vždy správný výsledek.

Úloha: Algoritmus přátelství

Která vlastnost nebo vlastnosti chyběly první verzi postupu v následujícím videu?

Ze seriálu The Big Bang Theory, 13. epizoda 2. série. V případě potřeby se podívej na dabovanou verzi.

Další vlastnosti algoritmů

Kromě těch, které algoritmy definují, sledujeme i další zajímavé vlastnosti. Možná se divíš, proč není součástí definice korektnost (správnost). Je to proto, že definicí chceme vystihnout „spolehlivou bezmyšlenkovitou proveditelnost“, třeba i strojem. Správnost je ovšem vždy otázka konkrétního zadání. Sled instrukcí není správný sám o sobě, to nedává smysl.

O správnosti můžeme rozhodnout až se znalostí problému, který má postup řešit. Přitom to, že postup neřeší správně nějaký problém, neznamená, že nemůže řešit správně jiný problém, a už vůbec ne, že nelze vykonávat automatizovaně. Takže: musí být pracovní postup správně, aby byl algoritmem? Ne. Chceme se zabývat především správnými algoritmy? Samozřejmě ano.

Další zajímavou vlastností je univerzálnost (obecnost, hromadnost). Obvykle je žádoucí, aby algoritmus řešil ne jeden konkrétní problém, ale celou škálu podobných problémů. Neskládáme vlaštovku formátu A4, ale libovolného obdélníku přiměřených proporcí. Nepřevádíme z dvojkové soustavy číslo 1101, ale libovolné číslo. Když už trávíme čas tvorbou algoritmu, tak ať to stojí za to.

Někdy je hromadnost dokonce řazena mezi nutné vlastnosti algoritmu. Potíž je, že se v mezních případech těžko rozhoduje. Kolik problémů je už dostatečná hromada, aby byl algoritmus dost hromadný? Když uberu zrnko z hromady písku, asi to pořád bude hromada. Asi i když uberu další… kdy to tedy přestane být hromada? Kde je hranice? Proto hromadnost není vhodný pojem pro použití v definici. Přesto samozřejmě obvykle upřednostňujeme co možná nejobecnější pracovní postupy.

Speciální algoritmy

Je dobré nezapomínat, že se v některých případech hodí i zcela speciální jednoúčelové postupy. Přitom mohou být automatizovatelné, tedy algoritmické. Jako příklad nám poslouží postup co nejpřesnějšího výpočtu čísla π, tedy zcela konkrétního čísla. Jiným příkladem je výpočet dráhy konkrétní komety, nebo řízení přistání konkrétní sondy na konkrétní planetu. Taková sonda se typicky použije právě jednou.

Poslední podstatnou a žádoucí vlastností, kterou zde zmíníme, je efektivita (úspornost). Samozřejmě hledáme algoritmy, které vedou k výsledku nejrychleji, nejsnáze, nejlevněji, nejbezpečněji atd. Jistě si pamatuješ naši snahu o rychlé uhodnutí čísla (tedy nikoliv tipováním). K posuzování efektivity algoritmů a ke způsobům zvyšování jejich efektivity se později ještě vrátíme, je to jedna z nejdůležitějších oblastí informatiky. I neúsporný algoritmus je ale algoritmus. Opět by se nám poměrně těžko hledala ostrá hranice.