Back Algoritme Afrikaans Algorithmus ALS አልጎሪዝም Amharic Algorismo AN خوارزمية Arabic الجوريزم ARZ এলগৰিথম আৰু ডেইটা ষ্ট্ৰাকচাৰ Assamese Algoritmu AST Alqoritm Azerbaijani القوریتم AZB

Algoritem

Diagram poteka algoritma (Evklidov algoritem) za izračun največjega skupnega delitelja dveh števil a in b na lokacijah imenovanih A and B. Algoritem uporabi dve zaporedni odštevanji v dveh zankah: IF test B ≥ A vrne "yes" ali "true" (natančneje, število b na lokaciji B je večje ali enako številu a na lokaciji A) THEN, algoritem priredi B ← B − A (kar pomeni število b − a nadomesti stari b). Podobno, IF A > B, THEN A ← A − B. Proces se zaključi, ko je (vsebina) B enaka 0 in vrne največjega skupnega delitelja iz A.
Diagram Ada Lovelace iz "note G", ki je prvi objavljen računalniški 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
From Wikipedia, the free encyclopedia · View on Wikipedia

Developed by Nelliwinne