Začněme obecným citátem z B. Kurase
"Bez jasně vymezeného kontextu můžeme být zaplavováni nekonečným bohatstvím informací, ale nebudeme rozumět žádné, protože si ji nedokážeme zařadit, aby nám dávala smysl.".
Tato myšlenka nabývá na důležitosti pro oblast počítačů a programování, což jsou nástroje umožňující záplavu informací a přirozeně takto slouží i sami sobě. Jaký je tedy kontext "Počítačů a programování" ? Zůstaňme v obecné rovině lidského bytí a zeptejme se jak vzniká poznání následně šířené ve formě informací. Možné vysvětlení lze nalézt v Encyclopedia Britanica:
"Humans incessantly explore, experiment, create, and examine the world. The active process by which physical, biological, and social phenomena are studied is known as science. Individuals involved in science, called scientists, often spend their entire lives in pursuit of answers to probing questions."
Jde tedy o kladení si otázek o světě a hledání odpovědí. Zkoumané otázky mají v uvedeném širokém kontextu různý charakter. Některé z nich vyžadují nalezení řešení nebo rozhodnutí, například jestli mají řešení. Takové otázky se obecně nazývají problémy. Slovník spisovné češtiny skutečně pod heslem problém uvádí:
problém, sporná nebo složitější otázka, kterou třeba řešit: vědecký, výrobní problém;
Jedním ze způsobů řešení problémů je použití algoritmů. Algoritmy byly na světě pravděpodobně odjakživa a určitě předtím než bylo na jejich označení použito zvláštní slovo.
Algoritmus je konečná množina příkazů, které vedou k nalezení řešení určitého problému.
Obecně lze jako algoritmy chápat také recepty na přípravu pokrmů nebo návody na pletení.
Příkaz vede k vykonání množiny operací (žádné, jedné nebo obecně několika), které jsou vykonatelné mechanicky, tj. bez potřeby dalšího přemýšlení pokud jsou vykonávány člověkem, a tedy mohou být vykonávány strojem. Příkaz může obsahovat výběr z několika možností, rozhodnutí jakou další operací pokračovat, opakování operací ap. Řešení problému pak získáme vykonáním posloupnosti odpovídajících kroků (operace, výběr, ... ). V současnosti pod pojmem algoritmus rozumíme konečnou množinu příkazů, která vede k nalezení řešení určitého problému, přičemž má další vlastnosti.
Konečnost. Algoritmus musí vždycky skončit po vykonání konečného (možná velice velikého) počtu kroků.
Pokud nemá jenom tuto vlastnost, je takový předpis nazýván výpočetní metoda. Příkladem jsou reaktivní systémy, které opakovaně reagují se svým okolím, tedy automat na kávu, řídící programy ap.
Jednoznačnost. Každý krok algoritmu musí být jednoznačně určen.
Vstup. Žádný nebo více.
Jde o algoritmy, které nemají explicitní vstup a generují posloupnosti hodnot požadovaných vlastností, například náhodná čísla.
Výstup. Jeden nebo více.
Pro zobrazení reálného světa, jeho model v naší mysli, si lidé odedávna vytvořili abstrakce, kterými jsou matematické struktury jako jsou čísla, geometrické útvary, funkce, ap., a pomocí kterých umíme problémy vyjádřit formálně, na rozdíl od vyjádření v přirozeném jazyce
Na vyjádření algoritmu, naproti tomu lidé původně používali přirozený jazyk, jak dokumentuje dílo Al Kwharizmího, obr. . Činíme tak dodnes, protože slovní vyjádření myšlenky algoritmu je často srozumitelnější Text na obr.
je následující:
Když čtverec a kořeny se rovnají číslu, je to jako když řeknete toto: čtverec a deset jeho kořenů se rovnají třicetidevíti dirhamům.¨
Jeho význam je, že čtverec, když k němu přičtete desetinásobek jeho kořenu, stane se třicetdevět. Jeho metoda je dělit kořeny dvěma a to je pět v tomto problému. Násobíš to sebou samým a to bude 25. To přičteš k třiceti devíti. To dá šedesátčtyři. Vezmeš odmocninu co je osm a od ní odečteš polovinu kořenů co je pět. Zůstanou tři a to je kořen který hledáš a jeho čtverec je devět.
Jde o algoritmus pro řešení rovnice tvaru x2 + px = q, který je současně vykonán pro p = 10 a q = 39. Od jména autora uvedeného spisu je odvozeno slovo algoritmus a od názvu díla slovo algebra.
Výpočty, podle algoritmů řešících nějaký problém, vykonával člověk buď vlastní myslí nebo použitím pomůcek na vykonávání matematických operací. Neformální používání algoritmů trvalo až do třicátých let dvacátého století, kdy problémy týkající se základů matematické logiky vedli k exaktnímu probádání pojmu algoritmus a otázek algoritmické řešitelnosti problémů.
Po vzniku počítače ve čtyřicátých létech minulého století bylo nutno algoritmus zapsat tak, aby jeho příkazy odpovídaly operacím počítače. Takový zápis, tedy na úrovni instrukcí počítače, byl pro člověka velice těžko srozumitelný a pro zápis algoritmů a výpočetních metod byly formálně definovány (vyšší) programovací jazyky, které umožňují vyjadřovat se na úrovni abstrakcí použitých v algoritmech.
Zápis, který vyhovuje pravidlům programovacího jazyka nazýváme program, přičemž obecně jde o výpočetní metodu a pokud splňuje podmínku konečnosti jde o algoritmus. Následně byly rozvinuty matematické přístupy ke zkoumání vlastností algoritmů a programů.
V tomto kurzu se budeme zabývat některými základními algoritmy a jejich vlastnostmi. Pro zápis algoritmů budeme používat oba způsoby, neformální opis v přirozeném jazyce i zápis v programovacím jazyce.
V následujícím textu si ilustrujeme pojmy problém, algoritmus, program a výpočetní metoda.
Na polici ve studovně se nachází jeden nebo více exemplářů knížky s námi požadovaným názvem a ve studovně jsme sami. Kolikátá zleva je první knížka s požadovaným názvem?
Vezmi knížku z levého kraje police. Když nemáš knížku s požadovaným názvem, ber postupně další ( jinak máš knížku s požadovaným názvem).
Uvedený postup lze formalizovat jako problém nalezení prvního prvku dané hodnoty v posloupnosti prvků. Posloupnost prvků reprezentujeme polem a celých čísel a hledanou hodnotu proměnnou x. Uvedenému verbálnímu vyjádření věrně odpovídá program LS v Javě na obr. s tím, že na proměnné i získáme první pozici knížky 6 na polici.
Uvedený algoritmus by z pohledu čitelnosti a srozumitelnosti, možná i jisté elegance mohl být zapsán v Javě ve tvaru na obr. . Je tedy možno vyjádřit tentýž algoritmus v jednom programovacím jazyce více způsoby. I když pro hodnocení programů jsou určitá hlediska, jako čitelnost a srozumitelnost, obecně není vyjádření algoritmu v programovacím jazyce jednoznačné ani při jejich uplatnění. Navíc, stejně jako v životě můžeme tutéž myšlenku vyjádřit v různých jazycích, je tomu tak i v případě algoritmů. Program pro algoritmus hledání prvku v poli by mohl mít v jazyce Pascal tvar uvedený na obr.
. Poznamenejme, že pro jeden problém můžeme znát několik různých algoritmů pro jeho řešení, jak již známe například pro problém řazení.
Kromě zápisu algoritmu, program může být i zápisem výpočetní metody. Základem programu pro reaktivní systémy je nekonečná smyčka, která je uvedena v programu Cyklus na obr. .