Definícia
Pod pojmom algoritmus rozumieme presne definovanú konečnú postupnosť pravidiel, ktorých realizácia
nám pre vstupné dáta umožní
po konečnom počte krokov získať zodpovedajúce výstupné dáta.
Možno ho špecifikovať ako počítačový program, formulovať ho v nejakom prirodzenom jazyku, alebo realizovať ako hardvérový dizajn.
Mal by byť ale formulovaný natoľko precízne, že ho môže realizovať mechanické alebo elektronické zariadenie.
Algoritmus udáva, ako sa vstupné dáta postupne transformujú na výstupné dáta. Opisuje teda zobrazenie
f: V –> W z množiny prípustných vstupných dát V do množiny výstupných dát
W.
Reprezentovať ho môžeme aj tak, že udáme matematicky presne definovaný stroj, ktorý ho realizuje krok za krokom. Jednoduchým
modelom je napríklad Turingov stroj.
Vlastnosti
- Správnosť
- Algoritmus je správny, ak pre každý zmysluplný vstup sa jeho vykonávanie zastaví v konečnom čase, pričom vráti správny výsledok. O čiastočnej správnosti hovoríme, ak sa algoritmus nezastaví na všetky zmysluplné vstupy. Nekorektný algoritmus sa buď nezastaví na všetky zmysluplné vstupy, alebo sa zastaví a ponúkne inú ako očakávanú hodnotu.
- Elementárnosť
- Jednotlivé činnosti postupu musia byť pre realizátora elementárne, teda také, ktoré vie zrealizovať. Napríklad pre žiaka prvého ročníka nie je elementárna činnosť vypočítať tretiu mocninu čísla.
- Rezultatívnosť
- Pre rovnaké vstupné dáta a pri rovnakých podmienkach dáva realizácia postupu vždy rovnaké výstupné dáta.
- Determinizmus
- Každý krok algoritmu musí byť jednoznačne a presne definovaný a je presne určené poradie krokov. V každom bode výpočtu musí byť jasné, ako má vykonávanie algoritmu pokračovať. Pre takýto presný zápis algoritmov boli navrhnuté programovacie jazyky, v ktorých má každý príkaz jasne definovaný význam. Vyjadrenie algoritmu v programovacom jazyku sa nazýva program.
- Všeobecnosť
- Algoritmus nerieši len jeden konkrétny problém (napr. vypočítať súčin 2x2 ), ale rieši všeobecnú triedu problémov rovnakého typu (napr. súčin dvoch čísel).
- Konečnosť
- Každý algoritmus musí skončiť po vykonaní konečného počtu krokov. Tento počet krokov môže byť ľubovoľne veľký (podľa rozsahu a hodnôt vstupných údajov), ale pre každý jednotlivý vstup musí byť konečný. Postupy, ktoré túto podmienku nespĺňajú, sa môžu nazývať výpočtové metódy. Špeciálnym príkladom nekonečnej výpočtovej metódy je reaktívny proces, ktorý priebežne reaguje s okolitým prostredím.
- Efektivita
- Aby algoritmus bol efektívny, musí realizovať úlohu v čo najkratšom čase a s použitím čo najmenšieho počtu prostriedkov.
- Vstup
- Algoritmus zvyčajne pracuje s nejakými vstupmi, veličinami, ktoré sú mu odovzdané pred začatím jeho vykonávania, alebo v priebehu jeho činnosti. Vstupy majú definované množiny hodnôt, ktoré môžu nadobúdať.
- Výstup
- Algoritmus má aspoň jeden výstup, veličinu, ktorá je v požadovanom vzťahu k zadaným vstupom, a tým tvorí odpoveď na problém, ktorý algoritmus rieši.