Algoritmus

Algoritmus, vlastnosti algoritmu, história programovacích jazykov

Tento článok som nenapísal z vlastnej hlavy... Všetko čo sa týka teórie si hľadám na internete, takže pôvodný článok (trochu som ho upravil) nájdete na tomto odkaze. Je to dobrá stránka, kde nájdete veľa (skôr teoretických, než praktických) informácií.

Al-Chvarízmí (okolo 800), arabský matematik napísal dielo Alghoritmi de numero Indorum o indickej pozičnej sústave počítania. Je to kniha o pravidlách, podľa ktorých možno v desiatkovej sústave základné počtové úkony. Podľa názvu latinského prekladu knihy vzniklo slovo algoritmus, čiže návod, postup, pravidlo. Podľa oficiálnej definície je algoritmus vlastne  elementárny pojem informatiky (podobne ako v geometrii bod), či postup, ktorého realizáciou získame zo zadaných vstupných údajov po konečnom počte činností v konečnom čase správne výsledky.

Príklady každodenných postupov (objavovania postupov): zaviazanie šnúrok na topánkach, varenie, programujeme práčku alebo mikrovlnú rúru, zariaďujeme izbu nábytkom, vybavujeme si úradné doklady... atď.

Vlastnosti algoritmu

• elementárnosť - postup je zložený z činností, ktoré sú pre realizátora elementárne, zrozumiteľné (Napr. počítač nevie urobiť 4. mocninu, treba mu povedať aby urobil dvakrát druhú mocninu)
• 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 postup už skončil
• rezultatívnosť - postup dáva pre rovnaké vstupné údaje vždy rovnaké výsledky (ak skončí).
• konečnosť - Postup skončí vždy v konečnom čase a po vykonaní konečného počtu operácií (Niektoré metódy sú teoreticky konečné a algoritmicky správne, môžu však trvať tak dlho, že sú prakticky nerealizovateľné).
• hromadnosť - postup je aplikovateľný pre celú triedu prípustných vstupných údajov (Program na výpočet priemeru z n čísel pracuje nad množinou čísel, ne nad konkrétnymi číslami.)
• efektívnosť - postup sa uskutočňuje v čo najkratšom čase a s využitím čo najmenšieho počtu prostriedkov

Čo je to správny algoritmus?

• 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ý, t.j. pre každý vstup skončí a dá správny výsledok.

Algoritmus a program

Pod programom chápeme algoritmus napísaný v programovacom jazyku. Oproti algoritmu obsahuje navyše ďalšie inštrukcie pre počítač, predovšetkým vzťahujúce sa k určeniu typov spracovávaných údajov, využívaniu hardware, prípadne ďalšiemu softvéru počítača. Veľa programov spolupracuje s rôznymi doplnkovými súbormi, ktoré obsahujú pomocné údaje pre činnosť programu, napr. obrázky, hudbu, tabuľky výsledkov.

Tvorbou programov sa zaoberá softvérové inžinierstvo. Prebieha v 4 etapách:

• rozbor problému - treba presne odpovedať, čo treba riešiť. Pozorne sformulovať zadanie problému a požiadavky na vznikajúci program (softvér).
• Pozostáva z 3 častí:
• špecifikácia vstupných dát (štruktúra, formát, množina prípustných hodnôt)
• špecifikácia výstupných dát (štruktúra, formát, funkčná závislosť od vstupných dát)
• špecifikácia výnimočných situácií (napr. reakcia na chybné vstupné dáta)

• návrh riešenia - preskúmame, ako sa dá daný problém riešiť. Pri hľadaní riešenia vychádzame z toho, čo v danej oblasti vieme, aké máme k dispozícii prostriedky na riešenie úlohy, zvážime vhodný spôsob organizácie údajov. Celý problém rozdelíme na menšie pod-problémy. Výsledkom tejto práce bude algoritmus, čiže postupnosť krokov vedúcich k splneniu úlohy.

• realizácia - prepis navrhnutého algoritmu do niektorého programovacieho jazyka, ktorému počítač rozumie. Súčasťou tejto etapy napr. aj príprava obrázkov na úpravu vzhľadu programu, príprava zvukových efektov, hudby do pozadia a pod.

• údržba - odhaľovanie a oprava skrytých chýb, prispôsobovanie softvér meniacim sa požiadavkám používateľov, vývoj novších verzií programov a pod.

Typy jazykov

• strojovo orientované jazyky - program napísaný v strojovom jazyku je postupnosť elementárnych príkazov, ktoré nazývame inštrukcie a ktoré môže počítač priamo vykonávať (inštrukcia zodpovedá príkazu jazyka)
• vyššie programovacie jazyky - snažia sa odstrániť neštrukturovanosť, zvyšujú zrozumiteľnosť programu a zjednodušujú programovanie
• prekladače - umožňujú vykonávanie programov zapísaných v programovacom jazyku

Niektoré jazyky sú navrhnuté na ľubovoľné problémy, iné sú špecializované na problémy nejakej oblasti alebo len pre istý typ používateľov.

História programovacích jazykov

1950  - Assembler (Nižší programovací jazyk) - symbolické pomenovanie strojových inštrukcií a adries
1957 - Fortran (Formula Translation) - jazyk na technické výpočty
1958 - Algol (Algorithmic language) - základ pre štruktúrované jazyky
1958 - Lisp (List Processing) - jazyk pre vedcov pracujúcich v oblasti umelej inteli­gencie a symbolických výpočtov
1964 - Basic (Beginers All Purpose Instruction Code) - úvodný jazyk inžinierov ako príprava na Fortran
1967 - Logo (Jazyk pre deti) - korytnačia grafika, práca so zoznamami
1970 - Pascal (pomenovaný na počesť B. Pascala) - určený ako úvodný jazyk na vyu­čovanie programovania
1972 - C - Jazyk systémových programátorov
1980 - Smalltalk 80 - Čisto objektovo orientovaný jazyk - idea okien, práca s myšou
1983 - Pascal (Štandard jazyka Pascal) - neskôr sa rozšíril skoro na všetky univerzity sveta ako základný jazyk informatiky
1985 - C++ Objektovo orientovaný jazyk založený na C. Momentálne najrozšírenej­ším jazykom systémových programátorov.
1991 - Visual Basic - ("windovskovský") Basic. Je vhodný na tvorbu aplikácií pod Windows. Programy sú pomalé a preto je nevhodný pre náročné oblasti.
1992 - Comenius Logo - korytnačia geometria
1994 - Java  - Jazyk Internetu. Je spoľahlivý a prenositeľný pod rôzne typy operačných systémov
1995 - Delphi - ("windowsovský" Pascal ) - Vizuálny objektovo orientovaný Pascal
2001 - Imagine - ("windowsovké") Objektové Logo - riadené udalosťami