(Graficul fluxului unui algoritm (algoritmul lui Euclid) pentru calcularea celui mai mare divizor comun a două numere a și b în locații numite A și B. Algoritmul funcţionează prin scăderi succesive în două bucle: dacă (IF) testul B ≥ A rezultă „da”(sau adevărat) (mai exact numărul b în locația B este mai mare sau egal cu numărul a în locația A) atunci (THEN) algoritmul specifică B ← B – A (adică numărul b – a înlocuieşte vechiul număr b). În mod similar, dacă )IF) A > B, atunci A ← A – B. Procesul se termină atunci când (conținutul) B este 0, rezultând cel mai mare duvizor comun în A. (Algoritm derivat din Scott 2009:13; simbolurile și stilul de desen din Tausworthe 1977 ).)
În matematică și informatică, un algoritm este un set autonom pas-cu-pas de operații care urmează să fie efectuate. Există algoritmi care efectuează calcule, de prelucrare a datelor, precum și pentru raționament automatizat.
Un algoritm este o metodă eficientă care poate fi exprimat într-o cantitate finită de spațiu și timp și într-un limbaj formal bine definit pentru calcularea unei funcții. Pornind de la o stare inițială și o intrare inițială (probabil string nul), instrucțiunile descriu un calcul care, atunci când sunt executate, continuă printr-un număr finit de stări succesive bine definite, care produc în cele din urmă o „ieșire” și se termină într-o stare finală. Trecerea de la o stare la alta nu este neapărat deterministă; unii algoritmi, cunoscuţi sub numele de algoritmi aleatorii, includ intrare aleatoare.
Conceptul de algoritm a existat de secole, cu toate acestea o formalizare parțială a ceea ce avea să devină algoritmul modern a început cu încercările de a rezolva Entscheidungsproblem („problema deciziei”) prezentată de David Hilbert în 1928. Formalizările ulterioare s-au încadrat ca încercări de a defini ” calculabilitatea eficientă „sau” metoda eficientă „; aceste formalizări au inclus funcțiile recursive Gödel-Herbrand-Kleene din 1930, 1934 si 1935, calculul lambda al lui Alonzo Church dini 1936, „Formularea 1” a lui Emil Post din 1936, și mașinile Turing ale lui Alan Turing din 1936-7 și 193
Definiţie informală
O definiție informală ar putea fi „un set de reguli care definește exact o secvență de operații” care ar include toate programele de calculator, inclusiv programe care nu efectuează calcule numerice. În general, un program este doar un algoritm dacă se oprește în cele din urmă.
Un exemplu prototipic de algoritm este algoritmul lui Euclid pentru a determina cel mai mare divizor comun a două numere întregi; un exemplu (există și altele) este descris de diagrama de mai sus.
Boolos & Jeffrey (1974, 1999) oferă o semnificație informală a cuvântului în următorul citat:
„Nicio ființă umană nu poate scrie destul de repede, sau destul de mult, sau suficient de mic („mai mic, și mai mic, fără limită … până la a scrie pe molecule, pe atomi, electroni”), pentru a lista toți membrii unui infinit numărabil stabilit prin scrierea numelor lor, unul după altul, în o notație. Dar oamenii pot face ceva la fel de util, în cazul anumitor seturi infinite numărabile: Pot da instrucțiuni explicite pentru determinarea elementului al n-lea al setului, pentru n arbitrar finit. Astfel de instrucțiuni trebuie să fie date foarte explicit, într-o formă în care acestea ar putea fi urmate de o mașină de calcul, sau de un om care este capabil să efectueze operațiuni doar foarte elementare pe simboluri.„
Un „set infinit numărabil” este unul ale cărui elemente pot fi puse într-o corespondenţă unu-la-unu cu numerele întregi. Astfel, Boolos și Jeffrey spun că un algoritm presupune instrucțiuni pentru un proces care „creează” întregi de ieșire dintr-un întreg „de intrare” arbitrar sau numere întregi care, în teorie, pot fi arbitrar de mari. Astfel, un algoritm poate fi o ecuație algebrică, cum ar fi y = m + n – două „variabilele de intrare” arbitrare m și n care produc o ieșire y. Dar diferitele încercări ale autorilor pentru a defini noțiunea indică faptul că cuvântul implică mult mai mult decât acest lucru, ceva de ordinul a (pentru exemplul suplimentar):
Instrucțiuni precise (în limba înțeleasă de „calculator”) pentru un proces rapid, eficient, „bun”, care specifică „mutările” „calculatorului” (maşină sau om, dotat cu necesarul de informaţii și capabilități conținute intern) pentru a găsi, decoda, şi apoi procesa simbolurile/întregii de intrare arbitrari m și n, simbolurile + și = … și a produce „eficient”, într-un timp „rezonabil”, întregul de ieşire y într-un anumit loc și într-un format specific.
Conceptul de algoritm este de asemenea utilizat pentru a defini noțiunea de decidabilitate. Această noțiune este esenţială pentru a explica modul în care sistemele formale se nasc pornind de la un set mic de axiome și reguli. În logică, momentul în care este nevoie de un algoritm pentru a finaliza nu poate fi măsurat, deoarece nu este aparent legat de dimensiunea noastră obișnuită fizică. Din aceste incertitudini, care caracterizează lucrările în curs, se naşte indisponibilitatea unei definiții a algoritmului care se potriveste ambelor utilizări, concretă (într-un sens) și abstractă, a termenului.
Lasă un răspuns