Algoritmo di Euclide in informatica e geometria

Uno dei più antichi algoritmi conosciuti è algoritmo di Euclide, possiamo dirlo per certo perché se ne trovano le tracce, e le formule, negli Elementi di Euclide, scritti intorno al 300 a.C.. Questo non ci assicura che davvero lo abbia scoperto da zero proprio Euclide, potrebbe ad esempio averlo trascritto, magari raffinato, ma traendo spunto da suoi predecessori che un paio di secoli prima avevano avuto questa idea. L’ algoritmo di Euclide è un algoritmo per trovare il massimo comune divisore tra due numeri interi, il massimo comune divisore, è quello che a scuola l’insegnante di matematica fa abbreviare con l’acronimo MCD, maiuscolo perché è “massimo”. Viene spesso citato assieme al minimo comune multiplo, “mcm”, e a volte anche confuso. Dopo Euclide, anche Eudosso di Cnido intorno al 375 a.C. ha trattato il tema e Aristotele intorno al 330 a.C. ha citato l’algoritmo ne I topici.

Algoritmo di Euclide: informatica

Per utilizzare questo algoritmo spesso si utilizzano dei programmi di informatica. Se infatti abbiamo a che fare con numeri piccoli, risulta anche a mano molto semplice da usare, e pratico, ma se si vuole invece impiegare per masse di dati molto grandi, come quelle che oggi spesso ci si trova a trattare, allora l’informatica ci da una mano “imparando” l’algoritmo di Euclide e applicandolo a ciclo continuo fino ad arrivare a fornirci ad una risposta.

Esiste, sempre parlando di computer, un algoritmo alternativo: l’algoritmo del MCD binario. In questo caso per individuare il massimo comune denominatore, viene utilizzata la rappresentazione binaria dei computer che ci permette di evitare le divisioni, aumentando l’efficienza. Tornando all’algoritmo di Euclide, è possibile utilizzare la ricorsione in coda per esprimerlo e farlo “girare”.

In sostanza quando si hanno due numeri naturali a e b, si controlla se b è zero, se lo è, chiaro che il MCD è a, se non lo è, si divide a / b e si guarda se viene un resto pari a zero oppure no. Se il resto è zero, b è il MCD , altrimenti si procede assegnando a = b e b = r e si ripete nuovamente la divisione. Tenendo nota dei quozienti ottenuti durante lo svolgimento dell’algoritmo di Euclide, si ottengono due interi p e q tali che ap + bq = MCD(a, b). Questo l’algoritmo di Euclide esteso.

Ci sono molte occasioni in cui è possibile applicare questo algoritmo, così “semplice” ma allo stesso tempo utile. Ad esempio da sempre, da molto, lo si usa per alcuni polinomi ad una incognita e per polinomi omogenei a due incognite e in ogni contesto in cui è possibile eseguire la divisione col resto. A proposito, quando si ha tra le mani un oggetto algebrico in cui è possibile eseguire la divisione col resto, si ha tra le mani un “anello euclideo”.

Chi se ne intende di informatica può approfondire anche le tecniche di riconoscimento facciale, un tema molto attuale

Algoritmo di Euclide: tempo di calcolo

Il tempo di calcolo dell’ algoritmo di Euclide dipende chiaramente dai valori che si devono gestire, da quali sono e da quanti sono. Anche la tipologia è importante, sotto certi aspetti, perché se si prendono come valori di input due successivi numeri di Fibonacci, allora il tempo di calcolo sarà davvero molto lungo.

Algoritmo di Euclide geometrico

L’idea originaria di Euclide non è però di tipo matematico, bensì geometrico. Spesso la rappresentazione grafica che la geometria utilizza aiuta il nostro cervello ad andare oltre, o ad approfondire.

In questo caso tutto è nato dalla sfida di voler trovare una “misura” comune per la lunghezza di due segmenti. Ecco allora che l’algoritmo di Euclide procedeva sottraendo ripetutamente il più corto dal più lungo che è esattamente ciò che indica di fare la formula che abbiamo visto prima. Se i numeri diventano segmenti è tutto più intuitivo.

L’ algoritmo di Euclide è una di quelle scoperte che, una volta che altri hanno fatto, a noi appare banale. Ma sfido chiunque a farsi venire in mente questo meccanismo ai tempi di Euclide e con i mezzi che aveva.

Algoritmo di Euclide e Ritmo di Euclide

Approfondendo l’algoritmo si incontra anche il ritmo di Euclide. Non è altro che l’algoritmo, applicato al ritmo della musica. Lo ha scoperto Godfried Toussaint nel 2004 che lo ha raccontato in un documento dal titolo “The Euclidean Algorithm Generates Traditional Musical Rhythms”, ovvero “L’algoritmo euclideo genera ritmi musicali tradizionali”.

Cosa servono questi numeri? I MCD di due numeri serve dal punto di vista ritmico per dare il numero di beat e silenzi e generare i ritmo più importanti della musica tradizionale e della World Music. Quasi tutti si basano sul ritmo di Euclide, tranne forse quelli della musica indiana.

Se vi è piaciuto questo articolo continuate a seguirmi anche su Twitter, Facebook, Google+, Instagram

Pubblicato da Marta Abbà il 28 Luglio 2018