473 matches
-
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 și polinoamele de o variabilă. Aceasta a dus la noțiuni moderne de algebră abstractă, cum ar fi inelele euclidiene. s-a generalizat și pentru alte structuri matematice, cum ar fi nodurile și polinoamele multivariate. Algoritmul lui Euclid are numeroase aplicații practice și
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
tipuri de numere, cum ar fi întregii Gaussieni și polinoamele de o variabilă. Aceasta a dus la noțiuni moderne de algebră abstractă, cum ar fi inelele euclidiene. s-a generalizat și pentru alte structuri matematice, cum ar fi nodurile și polinoamele multivariate. Algoritmul lui Euclid are numeroase aplicații practice și teoretice. Este un element cheie al algoritmului RSA, 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
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
ar fi calcularea numerelor care satisfac mai multe congruențe (Teorema chinezească a resturilor) sau inversul multiplicativ al unui corp. Algoritmul lui Euclid poate fi utilizat pentru a construi fracții continue, în metoda lanțului Sturm pentru găsirea rădăcinilor reale ale unui polinom, și în mai mulți algoritmi moderni de factorizare a întregilor. În fine, este o unealtă de bază pentru demonstrarea unor teoreme din teoria modernă a numerelor, cum ar fi teorema celor patru pătrate a lui Lagrange și teorema fundamentală a
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
idealuri. În secolul al XIX-lea au fost dezvoltate și alte aplicații ale algoritmului lui Euclid. În 1829, Charles Sturm a arătat că algoritmul este util în metoda lanțurilor Sturm de numărare a rădăcinilor reale dintr-un interval dat ale polinoamelor. Algoritmul lui Euclid a fost prima metodă de descoperire a relațiilor între numere întregi de același ordin de mărime. În ultimii ani, s-au mai dezvoltat câțiva alți algoritmi noi legați de relațiile între întregi, ca de exemplu algoritmul Ferguson-Forcade
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
mai sus, algoritmul lui Euclid este folosit pentru a găsi cel mai mare divizor comun a două numere naturale (numere întregi pozitive). Acesta poate fi, însă, generalizat la numere reale, și la sisteme de numere mai exotice, cum ar fi polinoamele, întregii cuadratici și cuaternionii Hurwitz. În ultimele două cazuri, algoritmul lui Euclid este folosit pentru a demonstra proprietatea crucială de unicitate a factorizării, anume aceea că astfel de numere pot fi factorizate în mod unic în elemente ireductibile, structuri similare
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
m"/"n"; numărătorul și numitorul sunt prime între ele și respectă relația recursivă unde "m" = "n" = 1 și "m" = "n" = 0 sunt valorile inițiale. Convergentul "m"/"n" este cea mai bună aproximație rațională a lui "a"/"b" cu numitorul "n": Polinoamele de o singură variabilă "x" se pot aduna, înmulți și descompune în polinoame ireductibile, structuri analoage numerelor prime din mulțimea numerelor întregi. Cel mai mare divizor comun "g"("x") al două polinoame "a"("x") și "b"("x") este definit ca
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
unde "m" = "n" = 1 și "m" = "n" = 0 sunt valorile inițiale. Convergentul "m"/"n" este cea mai bună aproximație rațională a lui "a"/"b" cu numitorul "n": Polinoamele de o singură variabilă "x" se pot aduna, înmulți și descompune în polinoame ireductibile, structuri analoage numerelor prime din mulțimea numerelor întregi. Cel mai mare divizor comun "g"("x") al două polinoame "a"("x") și "b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
rațională a lui "a"/"b" cu numitorul "n": Polinoamele de o singură variabilă "x" se pot aduna, înmulți și descompune în polinoame ireductibile, structuri analoage numerelor prime din mulțimea numerelor întregi. Cel mai mare divizor comun "g"("x") al două polinoame "a"("x") și "b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
o singură variabilă "x" se pot aduna, înmulți și descompune în polinoame ireductibile, structuri analoage numerelor prime din mulțimea numerelor întregi. Cel mai mare divizor comun "g"("x") al două polinoame "a"("x") și "b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q"("x") și un polinom rest "r"("x") care satisfac ecuația
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
al două polinoame "a"("x") și "b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q"("x") și un polinom rest "r"("x") care satisfac ecuația recursivă unde "r"("x") = "a"("x") și "r"("x") = "b"("x"). Polinomul cât este ales astfel încât termenul dominant al lui "q"("x") "r"("x") să fie egal cu
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
b"("x") este definit ca produsul polinoamelor ireductibile comune, care pot fi identificate folosind algoritmul lui Euclid. Procedura de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q"("x") și un polinom rest "r"("x") care satisfac ecuația recursivă unde "r"("x") = "a"("x") și "r"("x") = "b"("x"). Polinomul cât este ales astfel încât termenul dominant al lui "q"("x") "r"("x") să fie egal cu termenul dominant al lui "r"("x
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
de bază este similară cu cea de la întregi. La fie care pas "k", se calculează un polinom cât "q"("x") și un polinom rest "r"("x") care satisfac ecuația recursivă unde "r"("x") = "a"("x") și "r"("x") = "b"("x"). Polinomul cât este ales astfel încât termenul dominant al lui "q"("x") "r"("x") să fie egal cu termenul dominant al lui "r"("x"); aceasta asigură că gradul fiecărui rest este mai mic decât gradul predecesorului său grad["r"("x")] < grad["r
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
grad["r"("x")]. Întrucât gradul este un număr întreg nenegativ, și întrucât el scade la fiecare pas, algoritmul lui Euclid se încheie într-un număr finit de pași. Ultimul rest nenul este cel mai mare divizor comun al celor două polinoame inițiale, "a"("x") și "b"("x"). De exemplu, fie următoarele polinoame de gradul patru, care fiecare se descompune în două polinoame de gradul doi: și Împărțind pe "a"("x") la "b"("x") rezultă un rest "r"("x") = "x" + (2/3
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
întrucât el scade la fiecare pas, algoritmul lui Euclid se încheie într-un număr finit de pași. Ultimul rest nenul este cel mai mare divizor comun al celor două polinoame inițiale, "a"("x") și "b"("x"). De exemplu, fie următoarele polinoame de gradul patru, care fiecare se descompune în două polinoame de gradul doi: și Împărțind pe "a"("x") la "b"("x") rezultă un rest "r"("x") = "x" + (2/3) "x" + (5/3) "x" − (2/3). În pasul următor, "b"("x
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
încheie într-un număr finit de pași. Ultimul rest nenul este cel mai mare divizor comun al celor două polinoame inițiale, "a"("x") și "b"("x"). De exemplu, fie următoarele polinoame de gradul patru, care fiecare se descompune în două polinoame de gradul doi: și Împărțind pe "a"("x") la "b"("x") rezultă un rest "r"("x") = "x" + (2/3) "x" + (5/3) "x" − (2/3). În pasul următor, "b"("x") se împarte la "r"("x") rezultând restul "r"("x") = "x
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
r"("x") rezultă un rest nul, indicând că "r"("x") este cel mai mare divizor comun al lui "a"("x") și "b"("x"), consistent cu factorizarea acestora. Multe dintre aplicațiile descrise mai sus pentru numere întregi sunt valabile și pentru polinoame. Algoritmul lui Euclid se poate folosi pentru rezolvarea de ecuații liniare diofantice și de probleme chinezești ale resturilor pentru polinoame; se pot defini și fracții continue de polinoame. Algoritmul lui Euclid polinomial are și alte aplicații proprii, cum ar fi
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
și "b"("x"), consistent cu factorizarea acestora. Multe dintre aplicațiile descrise mai sus pentru numere întregi sunt valabile și pentru polinoame. Algoritmul lui Euclid se poate folosi pentru rezolvarea de ecuații liniare diofantice și de probleme chinezești ale resturilor pentru polinoame; se pot defini și fracții continue de polinoame. Algoritmul lui Euclid polinomial are și alte aplicații proprii, cum ar fi lanțurile Sturm, o tehnică de numărare a rădăcinilor reale ale polinoamelor într-un interval dat de pe axa numerelor reale. Aceasta
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
dintre aplicațiile descrise mai sus pentru numere întregi sunt valabile și pentru polinoame. Algoritmul lui Euclid se poate folosi pentru rezolvarea de ecuații liniare diofantice și de probleme chinezești ale resturilor pentru polinoame; se pot defini și fracții continue de polinoame. Algoritmul lui Euclid polinomial are și alte aplicații proprii, cum ar fi lanțurile Sturm, o tehnică de numărare a rădăcinilor reale ale polinoamelor într-un interval dat de pe axa numerelor reale. Aceasta are aplicații în mai multe zone, cum ar
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
liniare diofantice și de probleme chinezești ale resturilor pentru polinoame; se pot defini și fracții continue de polinoame. Algoritmul lui Euclid polinomial are și alte aplicații proprii, cum ar fi lanțurile Sturm, o tehnică de numărare a rădăcinilor reale ale polinoamelor într-un interval dat de pe axa numerelor reale. Aceasta are aplicații în mai multe zone, cum ar fi criteriul de stabilitate Routh-Hurwitz din teoria sistemelor. În cele din urmă, coeficienții polinoamelor nu sunt obligatoriu numere întregi, reale, și nici măcar complexe
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
Sturm, o tehnică de numărare a rădăcinilor reale ale polinoamelor într-un interval dat de pe axa numerelor reale. Aceasta are aplicații în mai multe zone, cum ar fi criteriul de stabilitate Routh-Hurwitz din teoria sistemelor. În cele din urmă, coeficienții polinoamelor nu sunt obligatoriu numere întregi, reale, și nici măcar complexe. De exemplu, coeficienții pot fi din orice corp, cum ar fi corpurile finite GF("p") descrise mai sus. Concluziile corespunzătoare despre algoritmul lui Euclid și despre aplicațiile acestuia sunt valabile chiar
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numere întregi, reale, și nici măcar complexe. De exemplu, coeficienții pot fi din orice corp, cum ar fi corpurile finite GF("p") descrise mai sus. Concluziile corespunzătoare despre algoritmul lui Euclid și despre aplicațiile acestuia sunt valabile chiar și pentru asemenea polinoame. Întregii gaussieni sunt numere complexe de forma α = "u" + "vi", unde "u" și "v" sunt numere întregi obișnuite și "i" este unitatea imaginară. Definind un algoritm analog celui al lui Euclid, se poate arăta că întregii gaussieni au fiecare o
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
în "R" cu proprietatea că "a" = "qb" + "r" și "f"("r") < "f"("b"). Un exemplu de astfel de funcție este funcția normă utilizată pentru a ordona numerele întregi gaussiene ca mai sus. Funcția "f" poate fi modulul numărului, sau gradul polinomului. Principiul de bază este acela că la fiecare pas al algoritmului, "f" se reduce; astfel, dacă "f" poate fi redus doar de un număr finit de ori, algoritmul trebuie să se termine într-un număr finit de pași. Acest principiu
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
numere întregi "a" și "b" este generatorul idealului lor. Cu alte cuvinte, oricare ar fi întregii "s" și "t", există un alt întreg "m" cu proprietatea că Deși aceasta este valabilă și când "s", "t", "m", "a" și "b" reprezintă polinoame de o singură variabilă, ea "nu" este adevărată pentru inele de polinoame de mai mult de o variabilă. În acest caz, se poate defini o mulțime finită de polinoame generatoare "g", "g" etc. astfel încât orice combinație liniară de două polinoame
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
oricare ar fi întregii "s" și "t", există un alt întreg "m" cu proprietatea că Deși aceasta este valabilă și când "s", "t", "m", "a" și "b" reprezintă polinoame de o singură variabilă, ea "nu" este adevărată pentru inele de polinoame de mai mult de o variabilă. În acest caz, se poate defini o mulțime finită de polinoame generatoare "g", "g" etc. astfel încât orice combinație liniară de două polinoame de mai multe variabile "a" și "b" pot fi exprimate ca multipli
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]
-
este valabilă și când "s", "t", "m", "a" și "b" reprezintă polinoame de o singură variabilă, ea "nu" este adevărată pentru inele de polinoame de mai mult de o variabilă. În acest caz, se poate defini o mulțime finită de polinoame generatoare "g", "g" etc. astfel încât orice combinație liniară de două polinoame de mai multe variabile "a" și "b" pot fi exprimate ca multipli ai generatoarelor unde "s", "t" și "m" sunt polinoame de mai multe variabile. Orice astfel de polinom
Algoritmul lui Euclid () [Corola-website/Science/312202_a_313531]