Algoritmo, procedura sistematica che produce, in un numero finito di passaggi, la risposta a una domanda o la soluzione di un problema. Il nome deriva dalla traduzione latina, Algoritmi de numero Indorum, del trattato aritmetico del matematico musulmano del IX secolo al-Khwarizmi "Al-Khwarizmi concernente l'arte indù del reckoning".
informatica: algoritmi e complessità
Un algoritmo è una procedura specifica per risolvere un problema computazionale ben definito. Lo sviluppo e l'analisi degli algoritmi è fondamentale
Per domande o problemi con solo un insieme finito di casi o valori esiste sempre un algoritmo (almeno in linea di principio); è costituito da una tabella di valori delle risposte. In generale, non è una procedura così banale rispondere a domande o problemi che hanno un numero infinito di casi o valori da considerare, come "Il numero naturale (1, 2, 3, …) è un numero primo?" o "Qual è il massimo comune divisore dei numeri naturali aeb?" La prima di queste domande appartiene a una classe chiamata decidibile; un algoritmo che produce una risposta sì o no è chiamato procedura decisionale. La seconda domanda appartiene a una classe chiamata calcolabile; un algoritmo che porta a una specifica risposta numerica è chiamato procedura di calcolo.
Gli algoritmi esistono per molte infinite classi di domande; Euclid's Elements, pubblicato circa 300 aC, ne conteneva uno per trovare il più grande divisore comune di due numeri naturali. Ogni studente della scuola elementare viene esercitato in una lunga divisione, che è un algoritmo per la domanda "Dopo aver diviso un numero naturale a per un altro numero naturale b, quali sono il quoziente e il resto?" L'uso di questa procedura computazionale porta alla risposta alla domanda decidibile "B divide a?" (la risposta è sì se il resto è zero). L'applicazione ripetuta di questi algoritmi alla fine produce la risposta alla domanda decidibile "È un numero primo?" (la risposta è no se a è divisibile per qualsiasi numero naturale più piccolo oltre a 1).
A volte non può esistere un algoritmo per risolvere una classe infinita di problemi, in particolare quando vengono apportate ulteriori restrizioni al metodo accettato. Ad esempio, due problemi del tempo di Euclide che richiedevano l'uso solo di una bussola e di una retta (righello non marcato) —trecciare un angolo e costruire un quadrato con un'area uguale a un determinato cerchio — furono perseguiti per secoli prima che si dimostrassero impossibili. All'inizio del XX secolo, l'influente matematico tedesco David Hilbert propose 23 problemi che i matematici avrebbero dovuto risolvere nel prossimo secolo. Il secondo problema sulla sua lista richiedeva un'indagine sulla coerenza degli assiomi dell'aritmetica. La maggior parte dei matematici aveva pochi dubbi sull'eventuale raggiungimento di questo obiettivo fino al 1931, quando il logico di origine austriaca Kurt Gödel dimostrò il sorprendente risultato che devono esistere proposizioni (o domande) aritmetiche che non possono essere provate o smentite. In sostanza, qualsiasi proposta del genere porta a una procedura di determinazione che non finisce mai (una condizione nota come problema di arresto). Nel tentativo infruttuoso di accertare almeno quali proposizioni sono irrisolvibili, il matematico e logico inglese Alan Turing ha definito rigorosamente il concetto vagamente compreso di algoritmo. Sebbene Turing abbia dimostrato che devono esistere proposizioni indecidibili, la sua descrizione delle caratteristiche essenziali di qualsiasi macchina per algoritmi di uso generale, o macchina di Turing, è diventata la base dell'informatica. Oggi i problemi di decidibilità e calcolabilità sono fondamentali per la progettazione di un programma per computer, un tipo speciale di algoritmo.
