Strumenti Utente

Strumenti Sito


db:algoritmi

Algoritmi

Approfondimenti

Info

Quest'argomento non è collegato ad altri approfondimenti correlati. Si consiglia, in ogni caso, di controllare sempre [ l'Indice ] degli Approfondimenti

Questa pagina è solo improntata in attesa di completamento da parte dei Collaboratori. Se sei interessato a collaborare attivamente con Extrapedia, leggi come fare [ Collabora ]

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 1) 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 2) finito di stati successivi ben definiti, producendo alla fine “output” e termina allo stato finale. 3) Il passaggio da uno stato all'altro non è necessariamente deterministico; alcuni algoritmi, noti come Algoritmi randomizzati, incorporano input casuali. 4)

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. 5)

La parola stessa Algoritmo deriva dal cognome latinizzato del matematico del IX secolo Muhammad Ibn Musa al-Khwarizmi. 6) 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” 7) o il “metodo efficace”. 8) 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.


Qualora alcuni link non funzionassero, si prega di comunicarlo allo Staff - staff@extrapedia.org


1)
Ben definito rispetto all'agente che esegue l'algoritmo: “Esiste un agente informatico, di solito umano, che può reagire alle istruzioni ed eseguire i calcoli” - Rogers 1987
2)
“Una procedura che ha tutte le caratteristiche di un algoritmo a eccezione del fatto che forse manca di completamento può essere chiamata un 'metodo computazionale'” - Knuth 1973
3)
“Un algoritmo ha uno o più output, cioè quantità che hanno una relazione specifica con gli input” - Knuth 1973
4)
“un calcolo è eseguito in modo discreto e graduale, senza l'uso di metodi continui o analogici … portato avanti deterministicamente, senza ricorrere a metodi o dispositivi casuali” - Rogers 1987
5)
Roger L Cooke (2005) - “La storia della matematica: un breve corso”
6)
Brezina, Corona (2006) - Al-Khwarizmi: L'inventore dell'algebra“
7)
Kleene 1943 in Davis 1965: pag. 274
8)
Rosser 1939 in Davis 1965: pag. 225
db/algoritmi.txt · Ultima modifica: 13/04/2019 16:03 (modifica esterna)