Algoritem

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.

1. ↑ »The Definitive Glossary of Higher Mathematical Jargon — Algorithm«. Math Vault (v ameriški angleščini). 1. avgust 2019. Arhivirano iz prvotnega spletišča dne 28. februarja 2020. Pridobljeno 14. novembra 2019.
2. ↑ »Definition of ALGORITHM«. Merriam-Webster Online Dictionary (v angleščini). Arhivirano iz prvotnega spletišča dne 14. februarja 2020. Pridobljeno 14. novembra 2019.
3. ↑ "an algorithm is a procedure for computing a function (with respect to some chosen notation for integers) ... this limitation (to numerical functions) results in no loss of generality", (Rogers 1987:1).
4. ↑ "Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2).
5. ↑ Well defined with respect to the agent that executes the algorithm: "There is a computing agent, usually human, which can react to the instructions and carry out the computations" (Rogers 1987:2).
6. ↑ "An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5).
7. ↑ "An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5).
8. ↑ Whether or not a process with random interior processes (not including the input) is an algorithm is debatable. Rogers opines that: "a computation is carried out in a discrete stepwise fashion, without the use of continuous methods or analogue devices ... carried forward deterministically, without resort to random methods or devices, e.g., dice" (Rogers 1987:2).
9. ↑ Chabert, Jean-Luc (2012). A History of Algorithms: From the Pebble to the Microchip. Springer Science & Business Media. str. 7–8. ISBN 9783642181924.
10. ↑ »Hellenistic Mathematics«. The Story of Mathematics. Arhivirano iz prvotnega spletišča dne 11. septembra 2019. Pridobljeno 14. novembra 2019.
11. ↑ Cooke, Roger L. (2005). The History of Mathematics: A Brief Course. John Wiley & Sons. ISBN 978-1-118-46029-0.
12. ↑ Dooley, John F. (2013). A Brief History of Cryptology and Cryptographic Algorithms. Springer Science & Business Media. str. 12–3. ISBN 9783319016283.
13. ↑ »Al-Khwarizmi - Islamic Mathematics«. The Story of Mathematics. Arhivirano iz prvotnega spletišča dne 25. julija 2019. Pridobljeno 14. novembra 2019.
14. ↑ Kleene 1943 in Davis 1965:274
15. ↑ Rosser 1939 in Davis 1965:225