Un algoritmo è una sequenza di passaggi ben definiti che producono un risultato in un tempo finito.
Passo ben definito: è qualcosa che puoi fare, o calcolare, che è definito con precisione. Solo leggendo il passo sai cosa devi fare e come farlo. Nello specifico, puoi scriverlo in un linguaggio di programmazione che conosci e assicurarti che il frammento del programma corrisponda esattamente al passo.
Sequenza: i passaggi vengono eseguiti in un ordine specificato. I passaggi possono essere eseguiti più volte a seconda dei dati (cicli) o non eseguiti affatto a seconda dei dati (se le istruzioni). Gli algoritmi paralleli impongono solo un ordine parziale sui passaggi, quindi qui sto semplificando eccessivamente. Sarebbe più corretto descriverlo come un insieme parzialmente ordinato rispetto a una sequenza, ma volevo mantenere le parole un po 'più semplici. Inoltre, è facilmente possibile incorporare un set parzialmente ordinato in un ordine completo.
Risultato: uno stato o un valore finale. Non deve essere prevedibile in anticipo, ma deve essere un fine definito che soddisfi alcune condizioni. Ciò significa che un sistema operativo non è un algoritmo, sebbene ne utilizzi molti.
Finite: è garantito che un algoritmo si fermi a volte, almeno su una macchina che può funzionare abbastanza a lungo. Non è necessariamente garantito che si fermi in un tempo prevedibile e non è garantito che si fermi prima che il sole si espanda e diventi rosso su qualsiasi macchina esistente. Ciò significa anche che un sistema operativo non è un algoritmo, poiché idealmente funzionerà per sempre. Ho visto la parola "procedura" usata per descrivere qualcosa che sarebbe un algoritmo se fossimo sicuri che si fermerebbe prima o poi. (È possibile avere un algoritmo che si fermerà in una quantità di tempo sconosciuta Supponiamo che la congettura di Goldbach sia stata dimostrata matematicamente falsa, in una dimostrazione non costruttiva, quindi c'era un numero pari > 2 che non era la somma di due primi, un algoritmo che ha semplicemente testato i numeri pari alla fine terminerebbe, anche se nessuno saprebbe quando.)
L'algoritmo è un tipo di cosa intenzionalmente astratto, quindi non consideriamo domande come "È fisicamente possibile eseguirlo prima della morte termica dell'Universo?". Sarebbero troppo difficili da rispondere. Se si riferisce alle operazioni del computer, è facile da implementare in un linguaggio di programmazione.