Extrapedia

In Matematica e Informatica, un Algoritmo è una specifica inequivocabile su come risolvere una classe di problemi. Gli algoritmi possono eseguire calcoli, elaborazione dati, ragionamento automatico e altre attività.

Come metodo efficace, un Algoritmo può essere espresso in una quantità finita di spazio e tempo e in un linguaggio formale ben definito ¹⁾ per il calcolo di una funzione. A partire da uno stato iniziale e da un input iniziale, le istruzioni descrivono un calcolo che, una volta eseguito, procede attraverso un numero ²⁾ finito di stati successivi ben definiti, producendo alla fine “output” e termina allo stato finale. ³⁾ Il passaggio da uno stato all'altro non è necessariamente deterministico; alcuni algoritmi, noti come Algoritmi randomizzati, incorporano input casuali. ⁴⁾

Il concetto di Algoritmo esiste da secoli. I matematici greci utilizzavano algoritmi nel Setaccio di Eratostene per trovare i numeri primi, e l'Algoritmo euclideo per trovare il massimo comune divisore di due numeri. ⁵⁾

La parola stessa Algoritmo deriva dal cognome latinizzato del matematico del IX secolo Muhammad Ibn Musa al-Khwarizmi. ⁶⁾ Una formalizzazione parziale di ciò che sarebbe diventato il concetto moderno di Algoritmo è iniziata con i tentativi di risolvere il problema decisionale (Entscheidungsproblem) posto da David Hilbert nel 1928. Formazioni successive sono state formulate come tentativi di definire la “calculabilità effettiva” ⁷⁾ o il “metodo efficace”. ⁸⁾ Tali formalizzazioni includevano le funzioni ricorsive di Kurt Gödel - Jaques Herbrand - Stephen Cole Kleene del 1930, 1934 e 1935, il “lambda calculus” di Alonzo Church del 1936, la “Formulazione 1” di Emil Post del 1936 e le “macchine di Turing” di Alan Turing del 1936-1937.