Algoritmus

V stručnosti sa dá povedať, že algoritmus je presný návod k zvládnutiu určitej činnosti. S podobnými algoritmami sa stretávame v bežnom živote. Tieto algoritmy môžu byť recepty na varenie, návod k výmene oleja v prevodovke, postup zostavenia nábytku z jednotlivých dielov atď. Takýto presný návod však možno chápať rôzne. Rôzne návody sú prispôsobené znalostiam ľudí, pre ktorých sú tieto algoritmy určené. Algoritmus na opracovanie materiálu na sústruhu bude prispôsobený človeku, ktorý vie ako sústruh vyzerá a ktorý s ním už niekedy pracoval. Prispôsobenie algoritmu znalostiam a schopnostiam potenciálnych čitateľov je veľmi dôležitou súčasťou tvorby algoritmov. Rovnako, ako sa dá vychádzať zo schopností čitateľov, je nutné pri tvorbe algoritmov vedieť, čo všetko už je pripravené a odkiaľ môžeme začať. Druhú vec, ktorú si treba pri riešení úloh (na počítači) uvedomiť, sú údaje, resp. ich interpretácia a informácie. Úlohu ideme riešiť (nemusí to byť na počítači) vtedy, keď potrebujeme nové informácie. Slovo nové zdôrazňujeme z toho dôvodu, že informácie, ktoré získame riešením úlohy, nevznikajú z ničoho, ale že nejaké informácie už máme a na základe nich získavame ďalšie. Informácie, na základe ktorých úlohu riešime, nazývame vstupné, získané výstupné. Keďže z hľadiska riešenia úloh reprezentujeme informácie zvyčajne údajmi, hovoríme o vstupných a výstupných údajoch. Riešiť úlohu teda znamená transformovať vstupné údaje na výstupné, niekedy iba transformovať vstup na výstup. O tom, ako prebieha riešenie úlohy, ako prebieha transformácia vstupných údajov na výstupné, rozhoduje v prvom rade realizátor. Ak je realizátor z hľadiska danej úlohy dostatočne schopný, môže realizovať transformáciu priamo, v jednom kroku. Ide o úlohy, ktoré patria do základného repertoáru realizátora. Takými sú napr. úlohy malej násobilky pre žiakov základných škôl, úlohy zhodné s inštrukciami daného počítača, úlohy derivácie základných funkcií pre študentov niektorých vysokých škôl, atď. Väčšinou sa však transformácia nerealizuje priamo, ale je vhodnou kompozíciou primitívnych činností (operácií), ktoré je realizátor schopný vykonať. Ak je realizátorom počítač, sú primitívne činnosti dané jeho inštrukčnou sieťou. Kľúčovou otázkou riešenia úloh je teda nájdenie takej kompozície primitívnych činností realizátora, ktorá zabezpečí požadovanú transformáciu vstupných údajov na výstupné.

Netreba snáď zdôrazňovať, že výstupné údaje nie sú dané explicitne, ale implicitne, v tvare určitých podmienok, ktoré musia výstupné údaje spĺňať. Budeme im hovoriť výstupné podmienky. Rovnako musia spĺňať určité podmienky aj vstupné údaje. Tieto budeme nazývať vstupné podmienky. Často sa vstupné podmienky zhrňujú do jednej podmienky. Potom hovoríme o vstupnej podmienke a analogicky o výstupnej podmienke. Vstupnou a výstupnou podmienkou charakterizujeme daný problém , ktorý potrebujeme riešiť, špecifikujeme to, čo treba riešiť.

Na zápis vstupných a výstupných podmienok sa kladú určité požiadavky, ako je jasnosť, jednoznačnosť atď. Aj keby sme niekedy vystačili s prirodzeným jazykom, budeme častejšie používať formálnejší a presnejší jazyk výrokových foriem, ktorý poznáme zo strednej školy.

Pre algoritmus zvyčajne definujeme tri základné vlastnosti:

- Determinovanosť: znamená, že činnosť algoritmu je natoľko presná a pritom všeobecne pochopiteľná, že nepripúšťa v žiadnom kroku procesu subjektívnu možnosť voľby ďalšieho pokračovania. Činnosť algoritmu nesmie závisieť od ľubovôli osoby, ani na vlastnostiach zariadenia, ktoré ho realizuje. Je to proces, ktorý môže byť kedykoľvek a kýmkoľvek opakovaný s rovnakým výsledkom.

- Hromadnosť: znamená, že algoritmus neslúži na riešenie jednej konkrétnej úlohy, ale na riešenie celej triedy úloh. Vstupné údaje sa môžu v určitých medziach meniť. Tak napr. algoritmus na výpočet druhej odmocniny z daného čísla platí pre ľubovoľné konečné nezáporné reálne číslo a nie iba pre jednu konkrétnu hodnotu. Postup na riešenie jednej individuálnej úlohy sa nenazýva algoritmom. Ak nemáme algoritmus na riešenie všetkých úloh danej triedy, neznamená to, že jednotlivé úlohy danej triedy nemôžeme vedieť riešiť. Na vyriešenie jednotlivých prípadov však musíme vytvárať špeciálny postup, ktorý nemusí byť vhodný pre iný prípad.

- Rezultatívnosť: vyžaduje, aby sa postup, použitý na riešenie ľubovoľnej úlohy danej triedy, po konečnom počte krokov zastavil a aby po zastavení dával požadovaný výsledok. Z tejto vlastnosti automaticky vyplýva pojem oblasti použiteľnosti algoritmu. Je to taká najväčšia oblasť vstupných údajov, pre ktoré je algoritmus rezultatívny. To znamená, že ak za vstupné údaje zoberieme údaje z oblasti použiteľnosti, algoritmus sa zastaví po konečnom počte krokov s požadovaným riešením.

Ak údaje nie sú z tejto oblasti, algoritmus sa alebo nezastaví, alebo sa zastaví, ale nedostaneme požadované výsledky.

Po oboznámení sa so základnými pojmami môžeme algoritmus definovať ako postupná transformácia vstupných údajov na výstupné a naopak.

Pre zobrazenie algoritmu používame rôzne metódy; patrí k nim napr.:

- formalizovaný popis priebehu pracovného postupu vo forme textu členeného na odstavce (logické štruktúry z funkčného hľadiska)

- dátovo orientované diagramy HIPO (z angl. Hierarchy plus Input- Process- Output, tzn. hierarchický diagram a diagram vstupu, spracovania, výstupu), spojujúce v grafickom vyjadrení funkčné členenie problému, štruktúry dát a pracovných postupov pri rôznom stupni podrobnosti

- štruktúrne diagramy zamerané predovšetkým na zobrazenie postupností operácií v úlohe, avšak s využitím štandartných algoritmických štruktúr

- štruktúrne diagramy vo forme stromového diagramu, v ktorom sa procesy postupne členia až na najnižšiu úroveň, tzn. k operáciám so súčasnou charakteristikou algoritmickej štruktúry (vetvenie, opakovanie a pod.)

- vývojové diagramy toku dát a vývojové diagramy programu zobrazujúce predovšetkým postupnosť operácií v systéme a v jednotlivých úlohách

- rozhodovacie tabuľky využívané zvlášť pri zložitých rozhodovacích procesoch v algoritmoch programu

- slovný zápis v bežnej reči

Aj keď štruktúry algoritmov môžu byť rozmanité, môžeme ich rozdeliť na tri základné:

- lineárna jednoduchá štruktúra(sekvenčná): algoritmus prebieha lineárne bez opakovania a obsahuje v podstate vstupné, výpočtové a výstupné operácie

- lineárna rozvinutá štruktúra(rozhodovacia): algoritmus opäť prebieha lineárne bez opakovania, obsahuje však naviac operáciu výberu, keď určité operácie sa prevedú len za splnenia určitých podmienok. V opačnom prípade sa pokračuje ďalej vo výpočte alebo sa realizujú iné operácie. Dochádza teda k vetveniu v lineárnej sekvencii operácie programu. Vetvenie môže byť viacnásobné, závislé na hodnotách, ktoré obsahuje premenná nazývaná prepínač.

- cyklická štruktúra: algoritmus môže prebiehať dvojako. V prvom prípade prebieha cyklus tak dlho, pokiaľ podmienka má hodnotu ÁNO. V druhom prípade sa opakuje tak dlho, pokiaľ podmienka má hodnotu NIE; cyklus teda prebehne minimálne raz. Tieto druhy cyklov používame v tom prípade, keď môžeme predom stanoviť počet opakovaní cyklu. Vedľa týchto dvoch typov štruktúr ešte uveďme štruktúru cyklu, keď počet priechodov cyklom predom poznáme. V algoritme je buď počet opakovaní uvedený ako konštanta, alebo sa pred zahájením cyklu príslušnej riadiacej premennej priradí určitá hodnota. Opakované prevádzanie operácií pri platnosti podmienky sa bežne používa pre ukončenie algoritmu pri tzv. dotaze alebo teste na koniec spracovania.

- premenná: je to objekt, ktorý má určitý typ, má priradené meno a hodnotu, ktorú môže v priebehu operácie zmeniť.