Preštudujte si: Algoritmus

Či sa nám to páči alebo nie, informatickej definícii algoritmu sa nevyhneme. Skôr ako však pristúpime vysvetlime si, čo je vlastne motivačným prvkom tvorby algoritmov. Vysvetlíme si, čo je to pojem problém.

Prvotným dôvodom vytvárania počítačového programu alebo všeobecnejšie algoritmu, je existencia problému, ktorý potrebujeme riešiť.

Problémov je okolo nás obrovské množstvo a mnohé z nich si v každodennom kolobehu už ani neuvedomujeme. Keď sa však pozastavíme a zamyslíme, zistíme, že  život je plný problémov a problémových situácií, ktoré sa človek už od malička snaží riešiť. Spočiatku (prvých desať rokov života) mu na vyriešenie problému stačí začať plakať (jemnejší výraz pre slovné spojenie „vrešťať ako pavián“), pričom túto formu aplikuje dovtedy, kým dospelí neurobia to, čo chce. Tento spôsob je najjednoduchší, relatívne najmenej namáhavý, ale bohužiaľ nedá sa používať stále, pretože v určitom veku už rodičia nereagujú na náš plač poslušne, ale vytiahnú remeň (príp. varechu).

Vezmime si jednoduchý problém: chceme piť kakao. Predtým ako sa pustíme do riešenia, je vhodné naplánovať si postup. (Plánovanie robíme zvyčajne len zo začiatku, neskôr takéto problémy riešime automaticky – bez rozmýšľania).

Ako prvé zrejme musíme overiť, či máme mlieko, cukor a kakao – tieto suroviny pre nás predstavujú vstupné podmienky. Pokiaľ ich nemáme a nechce sa nám ísť na nákup (ďalší problém zložený z mnohých menších), postup sa skončil.

Ak sú všetky suroviny k dispozícii, môžeme pristúpiť k samotnej operácii.

1. do hrnčeka nalejeme mlieko,
2. dáme ho zohriať,
3. do prázdnej šálky zmiešame cukor a kakao (môže byť aj granko),
4. skontrolujeme mlieko,
5. ak nie je dosť teplé, vrátime sa do bodu 4.,
6. zalejeme zmes v šálke,
7. necháme vychladnúť,
8. vypijeme

... a je po probléme.

Pozrime sa teraz na našu činnosť zo stránky informatickej.

Na počiatku bol problém.

Problém je stav, v ktorom jestvuje rozdiel medzi tým, čo v danom momente máme a tým, čo chceme dosiahnuť (nemáme nič a chceme kakao). Problém je vždy viazaný na svojho majiteľa (pre iného to nemusí byť problém, ale nezmysel) a na problémové prostredie (okrem prostredia, v ktorom chceme piť kakao môže ísť napr. finančné, školské, citové).

Riešenie problému chápeme ako odstraňovanie rozdielu medzi pôvodným stavom a tým, čo chceme dosiahnuť. Postup, ktorým sa pri tejto činnosti riadime, nazývame aj algoritmus. Keď sa nám podarí dosiahnuť pôvodný cieľ, hovoríme o vyriešení problému. Nie každý problém je však riešiteľný a nie vždy sa dopracujeme k požadovanému výsledku.

1. Popíšte postup pri prechode cez križovatku bez semaforov.
2. Popíšte postup pri nákupe topánok.
3. Vymyslite algoritmus pre nastupovanie päťčlennej rodiny do dvojdverového automobilu. Popíšte aj vystupovanie.

Riešiť pomocou algoritmu problémy reálneho života je dosť náročné, pretože správny algoritmus vždy berie do úvahy všetky možnosti, detaily, náhody alebo zriedkavé situácie. Napr. pri našom postupe s varením kakaa by sme mali vziať do úvahy, že vypnú prúd (zastavia plyn), príde návšteva a mlieko vykypí, susedov kocúr rozbije šálku a pod. Takéto algoritmy potom možno navrhnúť len približne a za obmedzených podmienok.
O algoritmoch má zmysel hovoriť vtedy, keď máme k dispozícii určitú obmedzenú množinu príkazov (môže byť aj veľmi veľká), pomocou ktorých dokážeme navrhnúť postup pri riešení.

Vzhľadom na to, že ide o elementárny (základný) pojem, ako napr. v geometrii bod, dokážeme ho len opísať:

Algoritmus je presná postupnosť krokov a inštrukcií, ktorá nás od (meniteľných) vstupných údajov privedie v konečnom čase k výsledku.

Niektoré postupy nie sú algoritmy. Na to, aby bol postup algoritmom, musí spĺňať nasledovné kritériá (doplňujúce vlastnosti):

• elementárnosť: postup je zložený z jednoduchých krokov, ktoré sú pre vykonávateľa (počítač, nemysliace zariadenie, človek) zrozumiteľné,
• determinovanosť: postup je zostavený tak, že v každom momente jeho vykonávania je jednoznačne určené, aká činnosť má nasledovať, alebo či sa už postup skončil,
• rezultatívnosť: postup dáva pre rovnaké vstupné údaje vždy rovnaké výsledky,
• konečnosť: postup vždy skončí po vykonaní konečného počtu krokov,
• hromadnosť: postup je použiteľný na celú triedu prípustných vstupných údajov,
• efektívnosť: postup sa uskutočňuje v čo najkratšom čase a s využitím čo najmenšieho množstva prostriedkov (časových i pamäťových).

Splnenie týchto vlastností je dôležité, pretože algoritmy v informatike zvyčajne vykonáva nemysliace (jemnejší výraz pre hlúpe) zariadenie, ktoré si nedokáže uvedomiť, že postup sa vykonáva podozrivo dlho, nevie experimentovať, nemá žiadne skúsenosti a neučí sa z chýb.

Pokúsme sa teraz vysvetliť si jednotlivé vlastnosti podrobnejšie.

Každý postup môže byť zapísaný viacerými spôsobmi. Pri jeho navrhovaní treba dbať na to, aby jednotlivé inštrukcie boli pre adresáta zrozumiteľné, jednoduché a jednoznačné.

Vezmime si napr. zohrievanie mlieka v mikrovlnej rúre z predchádzajúceho príkladu. Ak sme majiteľmi tohoto novodobého zariadenia dlhší čas, nerobí nám príkaz „zohrej mlieko v mikrovlnej rúre“ problémy. Ak sme ju kúpili nedávno, alebo sme od prírody imúnni voči používaniu technických zariadení, nedokážeme túto činnosť vykonať, pretože pre nás nepredstavuje elementárnu operáciu (skôr ďalší problém).

Rovnako to môže dopadnúť v škole. Už deti na prvom stupni základnej školy vedia násobiť. Ak im však prikážeme: „Zistite šiestu mocninu čísla 2!“, zrejme nebudú vedieť reagovať. No keď im zadáme úlohu v tvare: „Zistite výsledok súčinu 2.2.2.2.2.2!“, bude to pre nich hračkou. Zistenie mocniny pre nich totiž nie je elementárnou činnosťou.

Pri formulácii si treba dávať pozor aj na jednoznačnosť.

Napr. príkaz: „Meľ dva dni staré rožky!“ alebo „Krájaj týždeň starú kapustu!“ sa dá vysvetliť všelijako. Výraz „Pridaj lyžicu cukru!“ alebo „Rozbi dve vajcia!“ môže pri nesprávnom vysvetlení spôsobiť v prvom prípade presladenie a v druhom fľaky na koberci alebo na stene.

Pokiaľ je algoritmus určený pre človeka, máme veľkú výhodu – človek sa dokáže učiť a na základe predchádzajúcich skúseností je schopný riešiť stále zložitejšie a zložitejšie situácie ako elementárne (napr. pre vodiča začiatočníka je odbočenie na križovatke nekonečným peklom, zatiaľ čo skúsenejší ho považujú za jednoduchú záležitosť). Počítačom, pre ktoré budeme väčšinu algoritmov vytvárať táto schopnosť chýba, no dokážeme ich ju naučiť my...

Splnenie tejto vlastnosti má zabezpečiť, aby sa algoritmus vždy skončil. Človek, pracujúci s problémom na základe skúseností dokáže určiť, či jeho postup dá alebo nedá správny výsledok (resp. či skončí alebo nie). Počítač bez skúseností sa na takejto úrovni rozhodnúť nedokáže.

Nahliadnime zasa do kuchyne: ak má počítač postupovať podľa nasledovných príkazov:

1. polož hrniec s jedlom na varič,
2. pusti plyn,
3. miešaj, kým nezačne vrieť.

môže sa stať, že v prípade vypnutia plynu sa bude touto činnosťou zamestnávať najbližších 50 rokov.

Rovnako príkaz: „Kop, kým nenarazíš na poklad!“ môže v prípade nesprávneho miesta znamenať prekopávanie sa do Austrálie.

Podobne matematický postup: „Kým je zadané číslo menšie ako jedna, vynásob ho dvoma!“ nás v prípade zadania nuly alebo záporného čísla môže priviesť až do pokojnej staroby.

Predchádzajúce príklady boli určite nekonečné, no okrem nich existujú aj problémy, ktorých riešenie je síce konečné, ale nájdenie výsledku trvá veľmi dlho. Typickým príkladom sú šifrovacie algoritmy, keď síce teoreticky dokážeme rozšifrovať každú správu, no doba realizácie je taká dlhá, že obsah správy po rozšifrovaní (po 10 rokoch) stráca zmysel.
Podobné je to s počítaním buniek v ľudskom tele, molekúl v litri vzduchu alebo zrniek piesku na púšti.

Ak od postupu vyžadujeme, aby bol hromadný, zvyčajne doň vkladáme nejaké vstupné hodnoty – parametre. Nie každý algoritmus však vie byť hromadný. Niektoré algoritmy sú šité presne na konkrétny problém a nie je možné vstupné parametre meniť, lebo sú zložité alebo jednoducho iné neexistujú. Preto túto vlastnosť považujeme skôr za užitočnú ako nutnú.

Typickým praktickým príkladom využitia hromadnosti je výpočet brzdnej dráhy automobilu pri zadanej rýchlosti, povrchu vozovky a prevážanej hmotnosti. Výsledok dokážeme určiť bez zmien v algoritme, postačí zadať iné vstupné údaje.
Pri vytváraní všeobecných algoritmov nejde o vyriešenie konkrétneho problému, ale skôr o popísanie postupu, podľa ktorého sa výsledok získava.

Zasa jeden matematický príklad: Ak chceme algoritmicky zapísať výpočet objemu kvádra, nemôžeme do algoritmu napísať 3 x 8 x 11, ale a x b x c, pričom ako vstupné hodnoty budeme zadávať práve hodnoty a, b a c.

Vytvoriť efektívny algoritmus znamená navrhnúť taký postup, ktorý s použitím minimálnych prostriedkov v čo najkratšom čase vyrieši náš problém. Aj algoritmus, ktorý nie je efektívny, je algoritmom, ale ak si zadávateľ, ktorý za vytvorenie algoritmu dokonca platí môže vybrať, zvolí si určite ten najefektívnejší. Efektívnosť je veľmi dôležitá najmä pri spracúvaní veľkého množstva údajov, kde je rozdiel či pri spracúvaní 2.000 údajov trvá jedna operácia sekundu alebo dve (rozdiel predstavuje viac ako polhodinu).
Pri zložitých problémoch je prvotným cieľom zvyčajne aspoň vytvorenie algoritmu a až po jeho otestovaní a v prípade potreby vylepšovanie a zrýchľovanie.

Riešme úlohu:
Pri prehliadke veliteľ potreboval zistiť počet nastúpených vojakov. Vojaci stáli v 32 radoch po 17. Úlohou poveril dvoch zástupcov. Prvý postupoval nasledovne: 17+17+17+17+....+17, druhý to skúsil ako 17 x 32. Čo myslíte, ktorý sa dopracoval k výsledku skôr?

Populárny je aj problém sčítavania čísel 1 až 100. Prvý spôsob, ktorému všetci rozumieme je postupovať 1+2+3+4+...+100. K výsledku sa síce dostaneme, ale ak vezmeme dvojice čísel 1+100, 2+99, 3+98... 50+51 (spolu ich je 50), vyriešime problém podstatne rýchlejšie: dvojíc je 50, ich súčet je 101, teda 101 x 50 = 5 050.

Či chceme alebo nie, či si to uvedomujeme alebo nie, celý náš život pozostáva z  algoritmov – postupov (napr. ranné vstávanie vždy vyzerá rovnako: zazvoní budík, otvorím pravé oko, udriem ho (budík), zatvorím pravé oko, o dvadsať minút sa strhnem, v zhone zhltnem raňajky a bežím na autobus). Tým, že sa ich snažíme zapísať, sledujeme zvyčajne dva ciele:

• vďaka popisu dokážeme vykonávaním algoritmu poveriť iného človeka alebo počítač,
• v ďaka vyjadreniu myšlienok sa nám problém stáva zrozumiteľnejším a sme schopní lepšie mu porozumieť.

Proces, ktorý pri zápise algoritmu vykonávame, sa nazýva algoritmizácia. Na jej začiatku vždy potrebujeme určiť vstupné (napr. rozsah hodnôt, ktoré môžu do algoritmu vstupovať) a výstupné podmienky (vlastnosti výsledku). Zadanie algoritmu potom zapisujeme takto:

{VST: vstupné podmienky}
?
{VÝS: výstupné podmienky}

napr. pre výpočet objemu hranola bude zápis vyzerať nasledovne:

{VST: a, b, c : reálne čísla rôzne od 0}
?
{VÝS: V – reálne číslo predstavujúce objem}

Algoritmy vytvárame na to, aby sme získali správny výsledok. K tejto požiadavke sa viažu nasledovné pojmy:

• algoritmus nazývame čiastočne správny, ak v prípade, že skončí, dáva vždy správne výsledky,
• algoritmus naz ývame konečný, ak skončí v konečnom čase pre ľubovoľné vstupné údaje,
• algoritmus naz ývame správny, ak je čiastočne správny a konečný.

Na to, aby sme mohli s niekým alebo niečím komunikovať, potrebujeme dorozumievací prostriedok – jazyk. Jazyk sám osebe však zvyčajne nestačí. Darmo ovládate deväť cudzích jazykov, keď osoba, s ktorou sa potrebujete dohovoriť je Eskimák a jazyk, ktorý používa, sa k tým vašim svojimi výrazovými prostriedkami nepribližuje ani zďaleka.
Na komunikáciu s iným objektom (človekom, strojom) je potrebné používať jazyk, ktorému rozumie. Pôvodne bol jazyk iba prostriedkom komunikácie medzi ľuďmi, dnes je už aj prostriedkom komunikácie medzi človekom a strojom. Jazyk, pomocou ktorého sa komunikuje so strojom, má však oproti klasickému jazyku určité špecifiká:

• ľudský jazyk obsahuje množstvo slov (napr. slovenčina pozná vyše 110.000 slov, angličtina takmer 800.000), pričom je v neustálom vývoji, slová do jazyka pribúdajú a zanikajú. Jazyk na komunikáciu so strojom vyžaduje stabilný a nemenný zoznam umožňujúci presnú špecifikáciu príkazov, ktoré výrobca do zariadenia napr. implementuje pri jeho výrobe,
• zatiaľ čo ľudské jazyky obsahujú množstvo výnimiek, „umeleckých obratov“ (frazeologizmy, príslovia a porekadlá, zdrobneniny a pod.), synoným (slová s rovnakým významom), homoným (rovnaké slová s odlišným významom, napr. hlava, list, koreň) a tvarov (pády, časovanie slovies, časy a neurčitok), v strojových jazykoch je vyžadovaná presnosť, konkrétnosť a adresnosť,
• prirodzený ľudský jazyk navyše obsahuje množstvo prvkov a konštrukcií, ktoré sú pri špecifikovaní postupov zbytočné.

Nemožnosť využitia prirodzeného jazyka v komunikácii so strojom viedla k potrebe úpravy prirodzeného jazyka a redukcii jeho obsahu na úzku skupinu slov, pomocou ktorých je možné popísať požadovanú činnosť a špecifikovať jej parametre.
Podobne ako sa nepodarilo ľudstvu dohovoriť na jednotnom jazyku (známym pokusom je napr. esperanto), ani pri algoritmických jazykoch nedošlo k dohode a vo všeobecnosti sa používa viacero z nich. Najčastejšie sú:

• vývojové diagramy kde je postupnosť činností popisovaná prostredníctvom grafických značiek a textu v nich,
  
• štruktúrogramy predstavujú zhutnenú obdobu vývojových diagramov, ktorá však oproti vývojovým diagramom nie je definovaná normou,
• obrázkové jazyky umožňujú programovať prostredníctvom spájania obrázkov, hlavným reprezentantom sú detské programovacie jazyky napr. programovanie kocky RoboLabu v legu,
• rozhodovacie tabuľky popisujú zložitejšie problémy pozostávajú zo zoznamu podmienok, kombinácie podmienok, zoznamu činností a kombinácie činností (pre našu prácu nie sú vhodné),
  slovný zápis algoritmu v národnom jazyku umožňujú formalizované jazyky, ktoré sa od programovacích jazykov odlišujú použitím slov národného jazyka namiesto príkazov programovacieho jazyka a voľnejším zápisom ostatných štruktúr,
• programovacie jazyky sú v oblasti algoritmizácie najpoužívanejším prostriedkom a predstavujú formalizované algoritmické jazyky založené na redukcii slov obvykle anglického jazyka.

Na to, aby sme dokázali komunikovať prostredníctvom algoritmického jazyka, potrebujeme mať stanovené príkazy, na základe ktorých dokážeme prikázať procesoru vykonať presne stanovené činnosti. Štandardne predstavuje príkaz elementárnu činnosť, ktorú je schopný vykonávateľ algoritmu realizovať.
Vykonávaniu príkazov v takom poradí, v akom sú zapísané, hovoríme sekvencia.V niektorých prípadoch je potrebné zabezpečiť vykonanie príkazu len pri splnení definovaných podmienok. Možnosť rozhodnúť sa a vykonať príkazy na základe pravdivosti skúmaného znaku sa označuje ako vetvenie. Skladá sa z podmienky a z príkazov, ktoré sa vykonajú v prípade kladného a záporného výsledku.
Veľmi často potrebujeme časť algoritmu opakovať. Zápis umožňujúci opakovanie označujeme ako cyklus. Pri každom opakovaní je dôležité čo (telo cyklu) sa má opakovať a dokedy (podmienka cyklu) sa má opakovať.
Sekvenciu, vetvenie a cyklus označujeme ako algoritmické konštrukcie a platí, že každý algoritmus dokážeme zapísať ich vhodnou kombináciou.

Každý algoritmický jazyk má dve zložky:

operačná zložka – obsahuje sadu prostriedkov, ktoré umožňujú spracovávať údaje t.j. elementárne činnosti, ktoré dokáže procesor vykonávať. Základnými činnosťami sú príkazy a podmienky

príkazy – sú vety jazyka, ktoré prikazujú procesoru vykonať isté, presne stanovené činnosti (napr. príkaz vstupu, výstupu, priradenia). Tieto príkazy musia spracúvať nejaké objekty. V programovaní sú nimi premenné, konštanty a výrazy.

riadiaca zložka – prostriedky pre riadenie postupnosti vykonávania jednotlivých činností algoritmu (základné algoritmické konštrukcie)