sličica| 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. sličica| 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. 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"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). je, da algoritem lahko izrazimo v končni količini prostora in časa"Any classical mathematical algorithm, for example, can be described in a finite number of English words" (Rogers 1987:2). in v natančno določenem formalnem jeziku.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). Navodila opisujejo izračun, ki se začne od začetnega stanja in začetnega vnosa (ki je morda prazen),"An algorithm has zero or more inputs, i.e., quantities which are given to it initially before the algorithm begins" (Knuth 1973:5). ki se potem izvaja skozi končno število natančno določenih zaporednih stanj, sčasoma proizvede "izhod""An algorithm has one or more outputs, i.e. quantities which have a specified relation to the inputs" (Knuth 1973:5). 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.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).
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. Grški matematiki so pozneje uporabili algoritme v Eratostenovem situ za iskanje praštevil ter Evklidov algoritem za iskanje največjega skupnega delitelja dveh števil. Arabski matematiki, kot je al-Kindi v 9. stoletju, so uporabljali kriptografske algoritme za razbijanje kod na podlagi frekvenčne analize.
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. 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"Kleene 1943 in Davis 1965:274 ali "učinkovite metode".Rosser 1939 in Davis 1965:225 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.
Etimologija Beseda algoritem ima svoje korenine v latinizirani nisbi algorismus, ki kaže na njeno geografsko poreklo, imena perzijskega matematika Mohamed ben Musa al Hvarizmija. Al-Hvarizmi (arabizirana perzijščina الخوارزمی c. 780–850) je bil matematik, astronom, geograf in učenjak v Hiši modrosti v Bagdadu in njegovo ime pomeni 'doma iz Horezma', medrečjem vzhodno od Aralskega jezera, ki je danes del Uzbekistana.
Neformalna definicija Neformalna definicija bi lahko bila "sklop pravil, ki natančno opredeljuje zaporedje operacij",Stone 1973:4 vse od računalniških programov do tipičnega birokratskega postopka in kuharskega recepta.
Na splošno je program lahko algoritem le v primeru, če se sčasoma ustaviStone simply requires that "it must terminate in a finite number of steps" (Stone 1973:7–8). - čeprav so včasih neskončne zanke tudi zaželene.
Prototipni primer algoritma je Evklidov algoritem, ki se uporablja za določitev največjega skupnega delitelja dveh celih števil; primer (obstajajo tudi drugi) je opisan v zgornjem diagramu poteka in tudi v kasnejšem poglavju.
Spodnji citat iz ponuja neformalni pomen besede "algoritem":Nobeno človeško bitje ne more pisati dovolj hitro, dovolj dolgo ali majhno† (†"majhno in še manjše brez omejitve ... poskušali bi pisati na molekule, na atome, na elektrone"), da bi zapisalo enega za drugim imena vseh članov preštevne neskončne množice. Toda ljudje lahko naredimo v primeru nekaterih preštevnih neskončnih množic nekaj enako uporabnega: lahko damo izrecna navodila za določanje n-tega člana množice za poljubni končni n. Takšna navodila moramo podati nazorno v obliki, ki ji lahko sledi računalniški stroj ali človek, ki je sposoben izvajati le nekaj osnovnih operacij s simboli.Boolos and Jeffrey 1974,1999:19
Formalizacija Algoritmi so bistveni za računalniško obdelavo podatkov. Številni računalniški programi vsebujejo algoritme, ki podrobno podajajo navodila, ki jih mora računalnik izvesti—v določenem vrstnem redu—za izvedbo določene naloge, kot je to na primer izračun plač zaposlenih. Tako lahko za algoritem štejemo katero koli zaporedje operacij, ki ga lahko Turingov popoln sistem ponazori. Med avtorji, ki zagovarjajo to tezo, so Minsky (1967), Savage (1987) in Gurevič (2000).
Turingovi stroji lahko opredelijo računske procese, ki se ne zaustavijo. Neformalne definicije algoritmov običajno zahtevajo, da se algoritem vedno zaustavi. Zaradi tega pogoja ostaja vprašanje, ali gre pri formalnem postopku algoritem ali ne, na splošno odprto —zaradi izreka teorije izračunljivosti, znanega kot problem zaustavitve.
Običajno se, ko je algoritem povezan z obdelovanjem informacij, podatki lahko preberejo iz vhodnega vira, jih zapišejo v izhodno napravo in shranijo za nadaljnjo obdelavo. Shranjeni podatki se obravnavajo kot del internega stanja entitete, ki izvaja algoritem. V praksi je stanje shranjeno v eni ali več podatkovnih strukturah.
Za nekatere od teh računskih procesov mora biti algoritem natančno opredeljen: določen na način, ki se lahko uporabi v katerikoli okoliščini, ki bi lahko nastala. To pomeni, da je treba sistematično obravnavati vse pogojne korake, za vsak primer posebej; kriterij mora biti jasen (in izračunljiv) za vse primere.
Ker je algoritem natančen seznam natančnih korakov, je vrstni red izračuna vedno ključnega pomena za delovanje algoritma. Za navodila se navadno predvideva, da so zapisana kot točen seznam in opisana "od vrha" proti "do dna"— ideja, ki je bolj formalno zapisana s potekom izvajanja.
Doslej je razprava o formalizaciji algoritmov temeljila na ukaznem programiranju. To je najpogostejši koncept—nalogo skuša opisati na diskretni, "mehanski" način. Edinstvena temu konceptu formaliziranih algoritmov je prireditvena operacija, ki nastavlja vrednost spremenljivke .Zgled take prireditve lahko najdete spodaj.
Za nekatere alternativne koncepte glej funkcionalno programiranje in logično programiranje.
Izražanje algoritma Obstaja veliko načinov za izražanje in zapis algoritma. Nekateri so zelo neformalni, nekateri so precej formalne in matematične narave, nekateri pa so precej grafični - vključno z naravnimi jeziki, s psevdokodo, diagrami poteka, diagrami v jeziku drakon, programskimi jeziki ali s tabelami za nadzor (procesirajo jih interpreterji). Izrazi algoritma v naravnem jeziku so ponavadi gostobesedni in dvoumni in se le redko uporabljajo za kompleksne ali tehnične algoritme. Psevdokode, diagrami poteka, drakon-diagrami in tabele za nadzor so strukturiran način za izražanje algoritmov in se izogibajo dvoumnostim, ki jih pogosto najdemo v izjavah, ki temeljijo na naravnem jeziku. Programski jeziki so primarno namenjeni izražanju algoritmov v obliki, ki jo lahko izvaja računalnik, pogosto pa se uporabljajo tudi kot način definiranja ali dokumentiranja algoritmov.
Obstaja širok nabor predstavitev, npr. program Turingovega stroja lahko podamo kot zaporedje strojnih tabel, kot diagrame poteka, kot drakon-diagrame ali kot obliko osnovne strojne kode ali zbirne kode.
Predstavitve algoritmov lahko razvrstimo v tri sprejete ravni opisa Turingovega stroja, in sicer:Sipser 2006:157
1 Opis na visokem nivoju “... proza za opis algoritma, pri čemer se ne upoštevajo podrobnosti izvedbe. Na tej ravni nam ni treba omenjati, kako stroj upravlja s trakom ali glavo. " 2 Opis izvedbe »... proza uporabljena za določanje načina, kako Turingov stroj uporablja glavo in način shranjevanja podatkov na traku. Na tej ravni ne podajamo podrobnosti o stanju ali prehodni funkciji. " 3 Formalni opis Najbolj podrobni, "najnižja raven", podaja "tabelo stanja" Turingovega stroja.
Za primer preprostega algoritma "Seštej m + n", opisanega na vseh treh ravneh, glejte Algoritem#Zgledi.
Načrtovanje Načrtovanje algoritma se nanaša na metodo ali matematični postopek algoritmov, ki rešujejo probleme ali pa so inženirske narave. Načrtovanje algoritmov je del teorij mnogih rešitev operativnih raziskav, kot sta dinamično programiranje in deli in vladaj. Tehnike za načrtovanje in implementacije načrta algoritma se imenujejo tudi vzorci načrtovanja algoritmov, z zgledi, ki vsebujejo vzorce predlog šablonske metode in vzorci dekoratorja.
Eden najpomembnejših vidikov načrtovanja algoritmov je ustvarjanje algoritma z učinkovitim časom izvajanja, znan tudi kot notacija O.
Tipični koraki pri razvoju algoritmov:
Opredelitev problema Razvoj modela Specifikacija algoritma Oblikovanje algoritma Preverjanje pravilnosti algoritma Analiza algoritma Implementacija algoritma Testiranje programov Priprava dokumentacije
Implementacija desno|sličica| Logični NAND algoritem je implementiran elektronsko v čipu 7400 Večina algoritmov naj bi se implementirala kot računalniški programi. Vendar se algoritmi lahko implementirajo tudi na druge načine, na primer v biološki nevronski mreži (npr. človeški možgani izvajajo aritmetiko, ali žuželke, ki iščejo hrano), v električnem krogu ali v mehanski napravi.
Računalniški algoritmi sličica| Primeri diagramov poteka kanoničnih Böhm-Jacopinijevih struktur: SEQUENCE (pravokotniki, ki se spuščajo ob strani), WHILE-DO in IF-THEN-ELSE. Tri strukture so narejene iz primitivnega pogojnega GOTO ( , prikazan kot diamant), brezpogojnega GOTO (pravokotnik), različnih operatorjev za prireditev (pravokotnik) in HALT (pravokotnik). Gnezdenje teh struktur znotraj prireditvenih blokov povzroči kompleksne diagrame (cf. Tausworthe 1977: 100, 114).