GeminiSkin
powered by PmWiki

Co je a není algoritmus

Pavel Drbal

V praxi slovem algoritmus označujeme předpis, který má tyto vlastnosti:

• Je chytrý, tj. usnadňuje práci.
• Týká se opakované činnosti.

Vytvoření algoritmu je určitá, obvykle dost náročná duševní práce. Nemá smysl jí plýtvat na věci jedinečné, které se nebudou opakovat a které nikdo nepotřebuje. Užitečnost algoritmu spočívá v tom, že očividné řešení je příliš pracné, než aby bylo rozumně realisovatelné, ale algoritmus nabízí jiné řešení, většinou méně průhledné, kterým lze rychleji dosáhnout cíle. Samotné slovo algoritmus je zkomolené jméno arabského učence al-Chvárizmího, který v osmém století napsal knihu o algebře. Mimochodem, i slova algebra, Algol a alkohol jsou zkomoleniny arabštiny.

Školní příklady:

Největší společný dělitel

Máme dvě čísla, cílem je nalézt jejich největšího společného dělitele.

Selský přístup: Rozložíme obě čísla na prvočinitele. Největší společný dělitel je společnou částí těchto rozkladů.

Euklidův algoritmus: Rozdílem obou čísel nahradíme to větší. Opakujeme tak dlouho, až jsou obě čísla stejná - to je největší společný dělitel.

Vidíme, že Euklidův algoritmus je velmi neprůhledný, nahrazuje však násobení a dělení jednoduchým odčítáním.

Nalezení prvočísel

Selský přístup: Zkoumané číslo dělíme přirozenými čísly. Pokud není dělitelné, je to prvočíslo. Dělení omezujeme na čísla do poloviny zkoumaného čísla, lépe do druhé odmocniny zkoumaného čísla.

Erastenovo síto: Napíšeme si řadu všech přirozených čísel, ve které jsou obsažena nás zajímající čísla. Číslo 1 necháme. Číslo 2 necháme a vyškrtneme každé druhé číslo. Každé další nevyškrtnuté číslo necháme a vyškrtneme jeho násobky - tj. necháme 3 a škrtáme jeho násobky, necháme 5 a škrtáme jeho násobky a tak dále.

Vidíme, že Erastenovo síto nahrazuje dělení a případné odmocňování pouhým odpočítáváním.

Algoritmus je abstraktní pojem

Nemůžeme říci Toto je algoritmus! a to druhé není algoritmus. Je to jako s jinými pojmy, třeba s pojmem práce. Práce jako konkrétní činnost neexistuje. Existuje kladení cihel, psaní textů, kopání příkopů, studium, prodávání zboží, vymýšlení příběhů, rýsování výkresu.

Algoritmus jako takový neexistuje, existují však různé zápisy a realisace algoritmu. Například slovní, počítačové, grafické nebo mechanické.

Příklad slovního vyjádření algoritmu je uveden výše.

Grafickému vyjádření algoritmu se říká nomogram. Příkladem nomogramu je třeba logaritmické pravítko, nebo známá tabulka, podle které může řidič zjistit, za jak dlouho po vypití piva může řídit.

Příkladem mechanické realisace algoritmu je třeba termostat z bimetalického plátku, který řídí přívod proudu do etaviry nebo plynu do karmy.

Elektronickou (mikroprogramovou) realisací algoritmu je třeba termostat pro chaty, který si můžete nařídit tak, že v sobotu a neděli udržuje teplotu 18°C a ostatní dny 12°C.

Každý program je realisací jednoho nebo několika algoritmů.

Obvykle rozlišujeme mezi realisací algoritmu a jeho popisem. Rozdíl je v úrovni podrobností. V popisu algoritmu je obecně řečeno „číslo”, například Rozložíme obě čísla na prvočinitele, kdežto v programu je buď Integer anebo longint.

Příklad vzniku algoritmu

Zaujala mě jedna hádanka v Českém rozhlase. Znáte to, když pošlete do týdne řešení, tak se účastníte losování o tričko (dříve o knihu).

Jeden kupec se vždy mazlil se svými zlaťáky, než je uložil do truhly. Počítal je, přehraboval se v nich, skládal je do sloupků. Jednou je naskládal do sloupků po dvou a jeden mu zbyl. Naskládal je do sloupků po třech a zbyly mu dva. To ho zaujalo. U sloupků po čtyřech mu zbyly tři, u sloupků po pěti mu zbyly čtyři, u sloupků po šesti mu zbylo pět zlatek. Teprve u sloupků po sedmi mu nezbylo nic.

Jak velkou měl tržbu?

Vyřešil jsem si tu hádanku a zaujalo mě na ní to, že lze na jedné jednoduché úloze ukázat několik různých algoritmů.

Ukážeme si, jak by to řešil

• “silový” programátor,
• pilný posluchač rozhlasu,
• líný posluchač rozhlasu,
• “správný” programátor,
• normální programátor.
• Zmíním se i o odrůdě “mlamoj”.

„Silový” programátor

„Silový” programátor naprogramuje úlohu tak jak ji slyší a příliš nad ní nepřemýšlí. „Silového”

programátora bezpečně poznáme podle toho, že když si stěžujete na jeho program, tak vám odpoví:
„No jo, to si musíš pořídit lepší počítač!”

Siloví programátoři jsou hodně produktivní, programy udělají brzy a udělají jich hodně, jejich programy ale nejdou používat v extrémních podmínkách. Možná že silovým programátorům ubližuji, asi i oni by přišli na to, že první dva testy jsou zbytečné.
První test na lichost je zahrnut v testu „mod 4 = 3″ i v testu „mod 6 = 5″.
Druhý test je zahrnut v testu „mod 6 = 5″.

Pilný posluchač rozhlasu

Pilný posluchač rozhlasu si do sloupečku napíše násobky sedmi a vedle nich zbytky po dělení. Není to příliš pracné, protože ve zbytcích je určitá pravidelnost, takže se ani moc nepočítá, celá práce je hodně mechanická. Takovou tabulku o stu řádků vidíte níže. Všimněte si, že jsem na sto řádcích objevil dvě řešení úlohy.

Líný posluchač rozhlasu

Líný posluchač dříve přemýšlí, než něco začne dělat. Všimne si, že násobky sedmi se zbytkem 3 po dělení čtyřmi může vyjádřit vzorečkem (1+4*j)*7. Podobné vzorečky si udělá i pro ostatní zbytky.

Řešením úlohy je číslo, které lze současně vyjádřit těmito třemi vzorečky. Tabulku podle těchto vzorečků vidíte níže. Obzvláště líný člověk ani tu tabulku nepíše a udělá si ji v některém tabulkovém procesoru. Tak jsem řešil úlohu já.

U této tabulky je pozoruhodná ještě jedna věc. Pilný člověk potřeboval sto řádků na dvě řešení, líný potřeboval padesát řádků na čtyři řešení, čili v tomto případě má líný člověk čtyřikrát větší produktivitu než pilný.

„Správný” programátor

správného” programátora KUPEC2.CPP”

Správného programátora poznáte podle toho, že odmítá opravovat své programy. Není divu, podívejte se na jeho řešení naší úlohy.

(„Správný” programátor vždy programuje v Céčku). Nic si nedělejte z toho, že tomuto programu nerozumíte. Každý správný programátor přestane rozumět svému programu nejpozději do tří hodin po jeho dokončení.

Abych o tom programu vůbec mohl mluvit, tak jsem ho převedl do Pascalu. Vidíte, že je daleko lépe promyšlen než program silového programátora. Zajímá se pouze o liché násobky sedmi, čímž ušetřil velké množství počítačového času, počet cyklů je čtrnáctkrát menší. Také je změněno pořadí testů tak, aby více testů za sebou bylo méně často. Správní programátoři dělají dobré programy, je však s nimi jiná potíž. Odmítají programy opravovat. Programy opravují pouze ze dvou důvodů:

• Přímý příkaz nadřízeného alespoň o dva stupně výše.
• Bez opravy je program nepoužitelný.

V každém případě po opravě jedné chyby vzniknou dvě další.

Normální programátor

Normální programátor si nejdříve sežene slušný algoritmus. Shání ho těmito způsoby:

• zeptá se kolegů,
• najde ho v literatuře,
• vymyslí ho.

V našem případě je správným algoritmem vzoreček (17+60*i)*7 kde i může být jakékoliv přirozené číslo. Programátor si sežene algoritmus a udělá podle něj svůj program - vidíte ho na obrázku.

Mlamoj

Nakonec vysvětlím, proč se určití lidé mezi programátory nevyskytují. Slovo „mlamoj” je zkratka ze slov „mladý moderní jinoch”. Mlamoj se vyznačuje tím, že má vlasy sepnuty do ohonu, na sobě má brčálově zelené nebo červené sako a v ruce drží mobilní telefon. Jeho určující vlastností je to, že vás při každém jednání podvede. Nejsou rozhodující jednotlivé vlastnosti, ale jejich komplex. (I někteří slušní programátoři nosili v určité etapě svého života ohon na hlavě.) Mlamoj jako programátor neexistuje. Po prvním přičichnutí k programování volí raději jiné předměty. Pokud dodělá úvodní programovací kurs, tak jen proto, že programy od někoho koupil. Mluvit však o nich umí krásně, takže někdy i oblafne examinátora.

Zhodnocení

Nejprve si uvědomme, že výše je uvedeno pět různých algoritmů a každý má svou realisaci (algoritmus „správného” programátora má uvedeny dvě realisace, jednu v Céčku, druhou v Pascalu).

Když se podíváme na výše uvedené případy, vidíme zásadní rozdíl mezi algoritmem a realizací. Způsob vybírání čísel ze sloupečků nebo třeba vzoreček (17+60*i)*7 definují všechna řešení úlohy, jsou to algoritmy v pravém smyslu slova. Jednotlivá řešení jsou nějakým způsobem omezená. Například délkou papíru nebo typem proměnné (do proměnné typu „integer” se vejdou jen čísla menší než asi 32000). Můžeme si vzít druhý papír nebo použít proměnnou typu „longint”, tím se mez oddálí, ale nezruší. U realisace vždy existuje nějaké omezení dané technikou realisace. Na rozdíl od jednotlivých realisací, algoritmus popisuje skutečně všechna řešení. Jedna z charakteristik algoritmu je tato:

Algoritmus je obecný, realisace je z technických důvodů omezená

Algoritmus se vždy tváří, že má nekonečný pruh papíru nebo proměnné, do kterých mohu dát čísla s libovolným počtem míst. Když porovnáváme výše uvedené algoritmy, zjistíme, že se rozpadají do dvou skupin. Jednu skupinu tvoří algoritmy pilného a líného posluchače rozhlasu, druhá skupina je z algoritmů s programovou realisací. Jsou to typy

• výběr z výčtu (síta),
• generativní algoritmy.

Neliší se tím, že první skupina používá pro řešení papír, kdežto druhá počítač. I ony „papírové” algoritmy lze realisovat pomocí tabulkového procesoru (tak jsem vytvořil obě tabulky, protože jsem líný počítat tolik čísel), Na druhé straně je pravda, že generativní algoritmy jsou pro programování vhodnější. Algoritmus výběru z výčtu (síto) obvykle probíhá ve dvou etapách:

• Vytvoří se množina (posloupnost), ve které jsou i hledané hodnoty, nevíme však které. Někdy se nejedná o vytvoření posloupnosti ale o její zpřístupnění.
• V této množině se hledá podle druhé části algoritmu.

Algoritmus líného posluchače je z tohoto hlediska typický. Nejdříve se vytvoří tři sloupce násobků sedmi žádaných vlastností a pak se hledá číslo, které se vyskytuje ve všech třech sloupcích. Algoritmy výběru z výčtu jsou časté a jsou obtížné tím, že jejich realisace spotřebovávají mnoho strojového času. Příklady: hledání extrému (maxima, minima), výpočet průměru nebo sumy, třídění ap.

Generativní algoritmy lze charakterisovat jednou z následujících vlastností:

• Z jedné žádané hodnoty lze vypočíst další.
• Žádané hodnoty závisí na nějakém parametru (parametrech) a algoritmus ukazuje způsob, jak získat žádanou hodnotu transformací parametru.

V našem příkladě lze ukázat obě vlastnosti:

• Znám-li jednu možnou tržbu kupce, získám z ní druhou přičtením čísla 420.
• Vzoreček (17+60*i)*7 ukazuje způsob odvození tržby z přirozených čísel.

Generativní algoritmy jsou velmi výhodné pro programování. Mnoho programátorských obratů a triků je vlastně připodobnění výběrového algoritmu generativnímu algoritmu.

Tvorba algoritmu

S tvorbou algoritmů to je jako s Kolumbovým vejcem. Většina algoritmů je lehce pochopitelná, ale přijít na něj není procházka růžovým sadem.

Algoritmy se většinou nevymýšlejí, algoritmy se objevují, podobně jako přírodní zákony. Jako Galileo objevil zákony pro tíži, Newton pro pohyb a Einštein pro pohyb rychlostmi blízkými světlu, tak jednotliví lidé objevili třídící algoritmy, vyhledávací algoritmy ap.

Objevování se týká chytrých (optimálních) algoritmů, jednoduché (pomalé) algoritmy vymyslí kde kdo. Každý z nás si vymyslí bublinové třídění, algoritmus QUICK se ale naučíme z knížek. Tisíc položek setřídíme bublinovým algoritmem pomocí 500 000 (půl miliónu) testů, kdežto algoritmem QUICK pouze pomocí 10000 (deseti tisíc) testů (rychlost algoritmu se obvykle měří počtem spotřebovaných testů - rozhodování). QUICK je pro tisíc položek padesátkrát rychlejší.

1. Osmé století je to mezi Sámovou a Velkomoravskou říší, kdy způsob života ve střední Evropě určovali Avaři, kdy Karel Veliký vyhnal Langobardy z Itálie a Arabové dobyli Pyrenejský poloostrov.
2. Abyste rozuměli mé starší češtině, kupec je seilmenežer.
3. Zlaťák (zlatka, florin, rýnský, gulden) bylo platidlo v Čechách do státního bankrotu v roce 1892, kdy byly nahrazeny korunami v poměru 1:2. Proto se desetikoruně říká pětka, odpovídala minci o hodnotě pěti zlatých. Současný kurs je asi 210 Kč za jeden zlaťák.
4. Truhla je předchůdce trezoru.
5. Když se Kolumbus vrátil po objevení Ameriky (kterou pokládal za Indii) uspořádal král s královnou na jeho počest slavnostní oběd. Jeden z dvořanů se nechal slyšet, že to nic není, objevit nový kontinent. Stačí vzít pár lodí a plout. Kolumba se to dotklo, vzal z ošatky na stole uvařené vejce, dal ho kolovat kolem stolu s tím, jestli ho někdo dokáže postavit na špičku. Dvořané se jeden po druhém pokoušeli vybalancovat vejce, nikomu se to však nepodařilo. Kolumbus lehce ťukl vejcem o stůl a vejce stálo. Teď už každý z dvořanů uměl postavit vejce, ale sami na to nepřišli.

• komentovat
• tisk

Stránku naposledy upravoval Lubos Pavlicek, 16.06.2005, 19:04