Înmatematică,algoritmul lui Euclid este o metodă eficientă de calcul alcelui mai mare divizor comun (CMMDC). El este denumit după matematicianul grecEuclid, care l-a descris în Cărțile VII și X dinElementele. CMMDC a două numere este cel mai mare număr care ledivide pe ambele. Algoritmul lui Euclid exploatează observația că cel mai mare divizor comun al două numere nu se modifică dacă numărul cel mai mic este scăzut din cel mai mare. De exemplu, 21 este CMMDC al numerelor 252 și 105 (252 = 21 × 12; 105 = 21 × 5); întrucât 252 − 105 = 147, CMMDC al lui 147 și 105 este tot 21. Cum cel mai mare dintre cele două numere este redus, repetarea acestui proces dă numere din ce în ce mai mici, până când unul dintre ele este 0. Când se întâmplă aceasta, CMMDC este celălalt număr, cel nenul. Inversând pașii algoritmului lui Euclid, CMMDC se poate exprima prin suma celor două numere inițiale, fiecare înmulțite cu un întreg pozitiv sau negativ, de exemplu:21 = 5 × 105 + (−2) × 252. Această proprietate importantă se numeșteidentitatea lui Bézout. Prima descriere rămasă a algoritmului lui Euclid este lucrarea lui Euclid intitulatăElementele (c. 300 î.e.n.), fiind unul dintre cei mai vechi algoritmi numerici încă utilizați. Algoritmul original a fost descris doar pentru numere naturale și lungimi geometrice (numere reale), dar algoritmul a fost generalizat în secolul al XIX-lea și la alte tipuri de numere, cum ar fi întregii gaussieni șipolinoamele de o variabilă. Aceasta a dus la noțiuni moderne dealgebră abstractă, cum ar fi inelele euclidiene. Algoritmul lui Euclid s-a generalizat și pentru alte structuri matematice, cum ar finodurile și polinoamele multivariabilă. Algoritmul lui Euclid are numeroase aplicații practice și teoretice. Este un element cheie al algoritmuluiRSA, o metodă de criptare cu chei publice des folosită în comerțul electronic. Este utilizat pentru a rezolva ecuațiile diofantice, cum ar fi calcularea numerelor care satisfac mai multe congruențe (teorema chinezească a resturilor) sau inversul multiplicativ al unuicorp. Algoritmul lui Euclid poate fi utilizat pentru a construifracții continue, în metoda lanțului Sturm pentru găsirea rădăcinilor reale ale unui polinom, și în mai mulți algoritmi moderni defactorizare a întregilor. Este utilizat și la demonstrarea unor teoreme dinteoria modernă a numerelor, cum ar fi teorema celor patru pătrate a lui Lagrange șiteorema fundamentală a aritmeticii (factorizarea unică). Algoritmul lui Euclid calculează eficient CMMDC a două numere oricât de mari sunt, deoarece nu necesită niciodată un număr de pași mai mare decât de cinci ori numărul de cifre (în bază 10) al celui mai mic întreg.Gabriel Lamé a demonstrat aceasta în 1844, marcând începutulteoriei complexității computaționale. În secolul al XX-lea s-au dezvoltat metode de îmbunătățire ale eficienței algoritmului. |
 - …turla bisericii dinPrachatice(foto),Cehia, a fost declarată în 2005arie naturală protejată cu suprafața de 90 m² datorită coloniei delilieci prezentă acolo?
- … la alegerile municipale dinSão Paulo din 1959, candidatura luiCacareco, o femelă derinocer negru, a obținut mai multe voturi decât oricare dintre partidele politice participante?
- ...dramaturgulgrecEschil a murit, potrivit legendei, lovit în cap de oțestoasă aruncată de la înălțime de unvultur?
- ...vârful muntos cel mai îndepărtat de centrul Pământului nu esteEverest, ci vulcanulChimborazo dinEcuador?
- ...veșmântul purtat deMaica Tereza este protejat de omarcă înregistrată pentru a evita exploatarea sa comercială?
- ... în septembrie1939, regeleGeorge al VI-lea al Regatului Unit se afla în război cuGermania Nazistă ca suveran al Marii Britanii, dar era neutru ca suveran al Irlandei de Nord?
- ...Farul Amédée dinNoua Caledonie a fost aprins pentru prima dată la 15 noiembrie 1865, de ziua de nume aîmpărătesei Eugénie, soția luiNapoleon al III-lea?
|
.jpg)
