Un esempio di algoritmo: l’algoritmo di Euclide esteso**

image_pdfimage_print

Si parla attualmente di algoritmi, sempre più frequentemente, come ad una moderna magia . In realtà , gli algoritmi erano già noti agli antichi greci; anche voi li avrete senz’altro usati alle scuole medie,  dove vi sono stati propinati come matematica (tipo l’algoritmo della divisione o quello della radice quadrata). In realtà l’algoritmo è un procedimento di calcolo iterato a seconda del fatto che si verifichino o no determinate condizioni. L’algoritmo della radice quadrata è nato ben prima dei computer e del software, e può essere eseguito (nella sua forma più semplice) perfino da un cavallo; Quindi quando c’è qualche idiozia ripetitiva da eseguire, allora possiamo essere in presenza di un algoritmo. Come cedete, niente al mondo  è  cambiato. Volevo proporvi un esempio di algoritmo:

L’ algoritmo di Euclide esteso.

Procediamo con un esempio numerico; consideriamo i due numeri:
294 e 144 e proponiamoci di risolvere per primo il seguente problema:

Trovare il MCD(204,144) ; con MCD indichiamo naturalmente il massimo comun divisore. Dubito che qualcuno lo abbia usato alle scuole inferiori, di solito si usa la scomposizione in fattori (comuni, con il minimo esponente). L’algoritmo è chiamato “algoritmo di Euclide”, perché sembra sia stato il primo a trovarlo, anche se applicato ai segmenti e formulato in modo leggermente diverso.

Dividiamo  il più grande (294) per il più piccolo (144), troveremo un quoziente e un resto, che di solito si indicano con q,r.

  1. ) 204 = 144 · 1 + 60 (q=1,r=60)

dividiamo adesso iterativamente il divisore per il resto:

2) 144 = 60 · 2 + 24 (q1=2,r1=24)

3) 60 = 24 · 2 + 12 (q2=2, r2=12)

4) 24 = 12 · 2 + 0 (q3=2,r3=0)

E’ da notare che ad ogni iterazione il resto successivo r è strettamente minore del resto precedente 60>21>12; dovendo poi essere r>=0 ad un certo punto deve necessariamente annullarsi.

Il massimo comun divisore è l’ultimo resto non nullo, ovvero 12 nel nostro caso. Infatti , guardando le eguaglianze sopra, si vede che 12 le divide tutte, e quindi divide anche 204 e 144. Infatti  dalla 4) si sa che 12 divide 24, ma allora dividendo sia 24 che 12 per la 3)divide il 60; dividendo 60 e 24 divide 144 per la 2) e per la 1) divide anche 204.

(se un numero divide ambo i termini di una somma, allora divide la somma stessa)

Se riprendiamo adesso  le divisioni eseguite sopra ed esplicitiamo il resto otteniamo:

60 = 204 + 144 · (−1)

24 = 144 + 60 · (−2)

12 = 60 + 24 · (−2)

Oltre ad essere un divisore comune, 12 è anche il massimo ; se infatti d è un altro divisore di 204 e 144  essendo 60 = 204 + 144 · (−1) allora d divide anche 60(se un numero è divisore di ambo i termini di una differenza allora è divisore anche della differenza); per lo stesso motivo è divisore anche di 24 e 12.Dividendo  anche il 12 significa che 12 è più grande di d oppure uguale, quindi 12 è il massimo. Vogliamo ora esprimere 12, che è il MCD (204,144) come combinazione lineare di 204 e 144.

Sostituiamo ora nell’ ultima identità (12 = 60 + 24 · (−2)) il numero 24 con la sua combinazione lineare di 144 e 60 (penultima identità)

12 = 60 + 24 · (−2) ; ma 24 = 144 + 60 · (−2)

quindi :

12=60 + [144 + 60 · (−2)] · (−2)=144 · (−2) + 60 · 5;

ma 60 = 204 + 144 · (−1)

allora:

12=144 · (−2) + [204 + 144 · (−1)] · 5

Quindi:
12=204 · 5 + 144 · (−7) (12 MCD, x=58, y=-7)

Per chi non fosse ancora convinto, accenno una dimostrazione non troppo formale, con le lettere al posto dei numeri. E’ un po’ più difficile; può bastare l’esempio numerico.

Supponendo a>b cominciamo a dividere a per b:

  1. a=b\cdot q_{0}+ r_{0} con 0\leq r_{0}<b

2) b=r_{0}\cdot q_{1}+ r_{1} con 0\leq r_{1}<r_{0}

3) r_{0}=r_{1}\cdot q_{2}+ r_{2} con 0\leq r_{2}<r_{1}
. . .

n) r_{n-2}=r_{n-1}\cdot q_{n}+ r_{n} con 0\leq r_{n}<r_{n-1}
n+1)r_{n-1}=r_{n}\cdot q_{n+1}+ 0

notiamo come nel caso numerico che:

0\leq ..< r_{n}<r_{n-1}<...<r_{2}<r_{1}<r_{0}

questa è una successione (finita) strettamente decrescente i cui termini non possono mai diventare negativi; quindi prima o poi deve annullarsi.

Seguendo il ragionamento dell’esempio numerico, vediamo che l’ultimo resto non nullo  r_{n} divide a e b; infatti oltre a stesso r_{n} divide r_{n-1} quindi dalla  n) divide ancher_{n-2} e così via, risalendo la catena si arriva a vedere che r_{n} divide sia a che b, quindi è un divisore comune. Per vedere che è il massimo esplicitiamo il resto come abbiamo fatto nel caso numerico.

  1. r_{0}=a-b\cdot q_{0}

2) r_{1} =b-r_{0}\cdot q_{1}

3) r_{2} =r_{0}-r_{1}\cdot q_{2}
. . .

n) r_{n}=r_{n-2}-r_{n-1}\cdot q_{n}

se d è un divisore di a e b allora , per la 1) è divisore anche di r_{0} quindi per la 2) anche di r_{1} e per la 3) di r_{2}; e così  via fino ad arrivare a r_{n},; essendo d divisore anche di r_{n} che è il nostro divisore comune trovato , allora r_{n} è il massimo divisore comune di a,b.

0 0 vote
Article Rating
Subscribe
Notificami
guest
0 Commenti
Inline Feedbacks
View all comments