Algoritem
From Wikipedia, the free encyclopedia
Algoritem je v matematiki in računalništvu končno zaporedje natančno določenih, računalniško izvedljivih navodil, običajno namenjenih reševanju težav ali za izvajanje izračuna.[1] [2] Kako podrobno se razdelajo koraki navodila, je odvisno od tega, kdo izvaja algoritem (človek, računalnik). Če algoritem izvaja računalnik, potem se govori o računalniškem programu. Algoritmi so vedno nedvoumni in se uporabljajo kot specifikacije za izvajanje izračunov, obdelave podatkov, avtomatiziranega sklepanja in drugih nalog.
Učinkovita metoda za izračun funkcije[3] je, da algoritem lahko izrazimo v končni količini prostora in časa[4] in v natančno določenem formalnem jeziku.[5] Navodila opisujejo izračun, ki se začne od začetnega stanja in začetnega vnosa (ki je morda prazen),[6] ki se potem izvaja skozi končno število natančno določenih zaporednih stanj, sčasoma proizvede "izhod"[7] in se zaključi v končnem stanju. Prehod iz enega stanja v naslednje ni nujno deterministično; nekateri algoritmi, znani kot naključni algoritmi, vključujejo naključne vnose.[8]
Koncept algoritma je obstajal že v antiki. Aritmetične algoritme, kot je algoritem deljenja, so uporabljali starodavni babilonski matematiki c. 2500 pred našim štetjem in egipčanski matematiki c. 1550 pr. n. št.[9] Grški matematiki so pozneje uporabili algoritme v Eratostenovem situ za iskanje praštevil[10] ter Evklidov algoritem za iskanje največjega skupnega delitelja dveh števil.[11] Arabski matematiki, kot je al-Kindi v 9. stoletju, so uporabljali kriptografske algoritme za razbijanje kod na podlagi frekvenčne analize.[12]
Sama beseda algoritem izhaja iz imena matematika iz 9. stoletja Al-Hvarizmija, katerega nisba (ki ga označuje kot Hvarizmi) je bila latinizirana v Algoritmi.[13] V 9. stoletju je napisal algoritme za osnovne matematične operacije. Njegova najbolj pomembna knjiga, Kitab al-Džabr val-Mukabala (Pravila reintegracije in redukcije), je bila osnova za standardizacijo arabskih številk v evropski matematiki. Del njegovega imena, Al-Džabr, je bilo kasneje interpretirano kot beseda algebra.
Delna formalizacija tega, kar bi postalo sodoben koncept algoritma, se je začela s poskusi reševanja problema Entscheidungsproblem (problem odločanja), ki ga je leta 1928 postavil David Hilbert. Kasnejše formalizacije so bile oblikovane kot poskusi definiranja "učinkovite izračunljivosti"[14] ali "učinkovite metode".[15] Te formalizacije so vključevale rekurzivne funkcije Gödel - Herbrand - Kleene iz leta 1930, 1934 in 1935, lambda račun Alonza Church iz leta 1936, Formulacija 1 Emila Posta iz 1936 in Turingove stroje Alana Turinga v letih 1936–37 in 1939.