Algoritmo

E’ una procedura di calcolo che consiste nell’applicare una sequenza finita di istruzioni (“passi”) al fine di ottenere un determinato risultato. Un algoritmo è iterativo se il procedimento deve essere ripetuto per cercare di conseguire lo scopo prefissato: un esempio di ciò è l’algoritmo euclideo per il calcolo del massimo com un divisore (MCD) fra due numeri naturali ae b, conb≠ 0. Se a> b, dividendo il numero maggiore per il minore si ottengono un quoziente q₁e un resto r₁< b: se quest’ultimo non è nullo, dividendo bper r₁si ricavano un nuovo quoziente q₂e un resto r₂< r₁; ser₂non è nullo, si divider₁ per r₂, e così via. Il procedimento termina alla n– esima iterazione quando r_{n + 1}= 0: in tal caso, r_n è il massimo comun divisore cercato. Per esempio, per trovare il MCD fra 72 e 20, si ha:

q₁= 3; r₁ = 12; q₂= 1; r₂ = 8; q₃= 1; r₃ = 4; q₄= 2; r₄ = 0.

Perciò, il MCD fra 72 e 20 è 4.

L’algoritmo euclideo è convergente perché ad ogni iterazione permette di ottenere un valore sempre più vicino a quello voluto; inoltre, esso consente di determinare quello esatto dopo un numero finito di iterazioni. Invece, dato un algoritmo iterativo convergente, nel caso in cui ad ogni iterazione si ricavi un valore sempre più prossimo a quello desiderato, ma tale avvicinamento prosegua all’infinito, al procedimento di calcolo è associato un errore di approssimazione, che diminuisce all’aumentare del numero di iterazioni, ma non può mai essere nullo: ciò si verifica, ad esempio, nella ricerca di un valore approssimato di  oppure di π.