S ohledem na obecnost algoritmu, jako popisu libovolné běžné každodenní činnosti, sahá počátek vzniku algoritmu až ke vzniku lidstva samotného. Vždyť i činnosti pravěkých lidí měly přesně daný postup, řád, konečnost a výsledek. Postupy, které dnes splňují podmínky algoritmu, se ve vědních oborech objevily již v období starého Řecka, ačkoli v této době pojem algoritmus ještě nebyl vůbec znám. Podstatu a použití algoritmu v období cca 300 let p.n.l. dokládá např. známý Euklidův algoritmus pro výpočet NSD, tj. největšího společného dělitele, nebo v 1 století n.l. Herón z Alexandrie který algoritmicky podal důkaz vzorce pro obsah trojůhelníku, či algoritmus pro hledání odmocniny z čísla.

Samotný pojem algoritmus vzniknul zhruba o tisíc let později v 9. století našeho letopočtu, a je spojován se jménem perského matematika Abú Abd Alláh Muhammad ibn Músá al-Chwárizmí, který vytvořil systém arabských číslic. Prvním významem slova algoritmus tak bylo „provádění aritmetiky pomocí arabských čislic“ a používal se k vyjádření zejména matematických postupů. Pojem algoritmus ve smyslu dnešního významu se používá zhruba od 20. století.

Využití známých algoritmů

Algoritmy se dnes využívají ve všech vědních oborech. Nejčastěji se s nimi ale setkáme v matematice a v programování, kde jsou nástrojem k sestavení teoretickému principu řešení daného problému. Vytváření algoritmů je v dnešní době předmětem intenzivního zkoumání a stává se i samostatným vědním oborem, při kterém se v nemalé míře využívají a dále rozvíjejí již vytvořené algoritmy, kterých existuje velmi mnoho, např.:

Eratosthenovo síto je algoritmus pro nalezení všech prvočísel menších než zadaná horní mez.
Dijkstrův algoritmus slouží k nalezení nejkratší cesty v grafu.
Ballman-Fordovův algoritmus nám umožní spočítat nejkratší cestu od uzlu k uzlu v ohodnoceném grafu.
Algoritmus de Casteljau pro výpočet bodu na Beziérově křivce.

Turingův stroj

Díky objevu Alana Turinga (1912-1954), který navrhl abstraktní matematický model počítače - Turingův stroj (1936/37), můžeme algoritmus definovat jako proceduru implementovatelnou pomocí Turingova stroje. TS se skládá z procesorové jednotky, tvořené konečným automatem, programu ve tvaru pravidel přechodové funkce a potenciálně nekonečné pásky pro zápis mezivýsledků. Existuje více obecných definicí Turingových strojů (jednopáskové / vícepáskové deterministické TS, nedeterministické TS, univerzální).

V jednom kroku výpočtu stroj v závislosti od aktuálního stavu a od symbolu (resp. k symbolů u k-páskových TS) snímaných hlavami:

změní svůj stav,
zapíše symbol na každé políčko snímané hlavou (čímž přepíše symbol, který tam byl zapsaný předtím ),
posune každou hlavu o jedno políčko doprava nebo doleva.

Způsob, kterým se má změnit stav, přepsat políčka a posunout hlavy, předepisuje přechodová funkce δ. Výpočet končí když stroj přejde do jednoho ze speciálních stop stav, na některých vstupech může výpočet stroje být nekonečný.

Další zdroje:

http://alan.sourceforge.net - projekt emulátoru TS

http://www.warthman.com/ex-turing.htm - projekt animace činnosti TS

vytvořil Institut biostatistiky a analýz Lékařské fakulty Masarykovy univerzity