Algoritmus - vlastnosti algoritmov
1. Algoritmus, algoritmizácia
S algoritmami sa bežne stretávame v každodennom živote. V podstate je algoritmus presný
návod na zvládnutie určitej činnosti. Môže ísť o recept v našom obľúbenom časopise, o návod na skonštruovanie modelu autíčka alebo aj
o jednoduchý príkaz, keď musíme ísť do obchodu. Ide však o zjednodušený model, pretože algoritmus závisí na znalostiach toho, komu je
určený. Napríklad, cudzinec, ktorý nepozná našu reč, ťažko pochopí aj najjednoduchším príkazom, formulovaných v nej. Počítačom
musíme tiež preložiť postup do ich reči, do série príkazov. Algoritmus v informatike charakterizujeme ako postup, ktorým získame zo
vstupných údajov v konečnom počte krokov, a teda v určitom čase odpovedajúce (správne) výstupne údaje (výsledky). Schopnosť vytvárať
algoritmy pre nemysliace zariadenia, ako počítač sa nazýva algoritmizácia a je nevyhnutná pre každého, kto pracuje s
počítačom. Programátori musia poznať jazyk, zrozumiteľný počítaču, čiže programovací jazyk.
2. Vlastnosti
algoritmov
Každý správny programátor by mal poznať nielen programovací jazyk, ale aj zásady pre tvorbu algoritmov. Tie by mali
spĺňať šesť základných vlastností:
2.1. Elementárnosť
Každý postup pozostáva z viacerých krokov,
ktoré musia byť pre adresáta jednoduché a zrozumiteľné, teda elementárne. Elementárnosť závisí na znalostiach konečného užívateľa,
ak je ním počítač, potom mu musíme vložiť celý postup v príkazoch, ktoré pozná. Jednoducho demoštrujem elementárnosť na príklade :
Ak deťom na základnej škole prikážeme, aby vypočítali 3! , asi nepochopia, čo od nich žiadame. Elementárnou činnosťou pre nich by
bol výpočet súčinu 1*2*3.
Tiež si treba dávať pozor na prípadnú dvojznačnosť, napr. príkaz „Meľ dva dni staré
rožky!“ sa dá vysvetliť aj tým, že budem dva dni neustále mlieť staré rožky.
2.2. Determinovanosť
Determinizovaný algoritmus je taký, keď v každom kroku jeho vykonávanie vieme, ako sa bude uberať ďalej, resp. či už neskončí.
Narozdiel od človeka, pre počítač musí byť postupnosť krokov jednoznačne určená.
Pr. Ak riešime príklad (1+2) * 3, potom
musíme jednoznačne určiť, že najprv vypočítame zátvorku, a až potom násobíme. Ak by algoritmus nebol determinovaný, mohli by sme dostať
výsledok 1 + 2*3, čo je výrazný rozdiel.
2.3. Rezultatívnosť
Postup dáva pre rovnaké vstupy
tie isté výsledky.
V bežnom živote sa nám často stáva, že túto podmienku sa nám nepodarí splniť. Ako príklad nám môžu
slúžiť jedlá pripravené podľa toho istého receptu alebo večné debaty po písomkách z matematiky, keď pri zhodnom zadaní každému vyjde
iný výsledok.
2.4. Konečnosť
Touto podmienkou je zabezpečené, že algoritmus skončí po vykonaní
konečného počtu krokov, teda v konečnom čase. Narozdiel od človeka, ktorý dokáže využívať skúsenosti, v prípade nemysliaceho
zariadenia musíme postup formulovať tak, aby bol určite ukončený.
Častokrát sa nám stáva, že vytvoríme nekonečný algoritmus,
napr. pri nesprávnej podmienke v cykle. Iným prípadom je vytvorenie algoritmu, ktorý je konečný, ale doba jeho realizácie je taká dlhá, že
potom stráca zmysel (šifrovacie algoritmy).
2.5. Hromadnosť
Táto vlastnosť je pre
nás výhodou, pretože postup, ktorý spĺňa túto podmienku dokáže riešiť viac problémov naraz, resp. dokáže aplikovať riešenie na
množinu rozdielnych vstupných hodnôt.
Riešenie príkladov pomocou vzorcov je príkladom na hromadný algoritmus. Napr. postup
nevypočíta 1+2 alebo 2+3, ale dokáže vypočítať a+b.
2.6. Efektívnosť
Aj algorimus,
ktorý nie je efektívny môže fungovať správne. Efektívnosť je preto skôr rozširujúcou vlastnosťou, ako podmienkou pre nevyhnutne správny
postup. Efektívny algoritmus je taký, ktorý s použitím minimálneho počtu prostriedkov v čo najkratšom čase vyrieši daný problém.
Pr. Vypočítajte súčet čísel od 1 do 100. Neefektívnym algoritmom by bolo postupné sčítavanie 1+2+…+99+100. Omnoho
efektívnejším spôsobom by bol výpočet (1+100)*50.
3. Aký je správny algoritmus
Algoritmus vytvárame za účelom správneho riešenia problému. Rozlišujeme tri druhy správnosti algoritmov:
Algoritmus je
čiastočne správny, ak v prípade, že skončí dáva vždy správne výsledky.
Algoritmus je konečný, ak
skončí v konečnom čase pre ľubovoľné vstupné údaje.
Algoritmus je správny, ak spĺňa obidve podmienky, čiže je
zároveň čiastočne správny a konečný.
Zones.sk – Zóny pre každého študenta