Glossario dei termini

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 q1e un resto r1< b: se quest’ultimo non è nullo, dividendo bper r1si ricavano un nuovo quoziente q2e un resto r2< r1; ser2non è nullo, si divider1 per r2, e così via. Il procedimento termina alla n– esima iterazione quando rn + 1= 0: in tal caso, rn è il massimo comun divisore cercato. Per esempio, per trovare il MCD fra 72 e 20, si ha:

q1= 3; r1 = 12; q2= 1; r2 = 8; q3= 1; r3 = 4; q4= 2; r4 = 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 π.