Euclide, algoritmodiEuclide, algoritmodi (per il MCD) o algoritmo delle divisioni successive, algoritmo che, dati due numeri interi a e b, permette di calcolarne il → massimo comune divisore mcd(a, [...]
dove ri (x) è l’i-esimo resto ottenuto e «deg» indica il grado del polinomio. Più in generale, l’algoritmodiEuclide può essere riformulato in ogni dominio euclideo D, richiedendo a ogni passo che sia verificata la condizione
dove ν: D − {0 ...
Leggi Tutto
. Termine matematico derivato da al-Khuwārizmī (v.), soprannome del matematico arabo Muḥammad ibn Mūsà (morto nell'820). Tale termine fu usato nel Medioevo specialmente per indicare i procedimenti di calcolo [...] .
Parimenti il procedimento per la ricerca del massimo comune divisore di due numeri o di due funzioni razionali intere, per mezzo di divisioni successive, prende il nome dialgoritmo del massimo comun divisore (detto anche algoritmodiEuclide). ...
Leggi Tutto
algoritmoalgoritmo procedimento sistematico di calcolo, oggi per lo più destinato a essere eseguito da un automa esecutore quale un computer. Il termine deriva dal nome latinizzato del matematico di [...] divisore fra due numeri interi a e b, indicato simbolicamente con mcd(a, b), può essere risolto utilizzando l’algoritmo euclideo (→ Euclide, algoritmodi) che si basa sulla proprietà che se due numeri naturali a, b, con a > b, sono divisibili per ...
Leggi Tutto
Introduzione Storica. -1. Il vocabolo algebra è una derivazione della parola araba al-giabr, che si trova per la prima volta nel libro Kitāb al-giabr wa 'l-muqābalah dell'astronomo e geografo Muhammad [...] del massimo comun divisore si fa allora applicando ad A e B l'algoritmodiEuclide (Elementi, libro VII), che serve a determinare il massimo comun divisore di due numeri interi. Con successive divisioni si ottengono le identità:
dove i successivi ...
Leggi Tutto
Informatica
Fabrizio Luccio
Franco P. Preparata
Carl-Erik Fröberg
Piero Sguazzero
Piero Dell'Orco e Tomaso Poggio
Teoria della computazione di Fabrizio Luccio
SOMMARIO: 1. Origine e motivazioni. [...] per risolvere una data classe di problemi. Un esempio classico ben noto è l'algoritmodiEuclide per trovare il massimo comun divisore di due interi assegnati.
Un'analisi dettagliata di una grande varietà dialgoritmi ha rivelato che ci sono ...
Leggi Tutto
L'Ottocento: matematica. Teoria dei numeri
Catherine Goldstein
Teoria dei numeri
Le tappe più significative dello sviluppo di un settore della scienza o dell'arte si accordano raramente con la suddivisione [...] parte, Eisenstein e Jacobi fornirono molte dimostrazioni di queste leggi, oltre a esaminare anche il caso di altre potenze, ma gli ostacoli che si presentavano erano molto seri: l'algoritmodiEuclide non era più valido e le proprietà aritmetiche ...
Leggi Tutto
frazione continua
frazione continua in aritmetica, espressione della forma
usualmente scritta, per motivi tipografici, in linea (ma si noti la posizione dei segni +) come
o, ancor più semplicemente, [...] continua che lo esprime è finita; in tal caso lo sviluppo di x in frazione corrisponde all’algoritmodiEuclide. Per esempio dati i due numeri 840 e 611, in base all’algoritmodiEuclide, poiché si hanno le uguaglianze
si ha che
In questo caso ...
Leggi Tutto
massimo comune divisore
massimo comune divisore (in simbolo mcd) tra due numeri interi a, b è il numero intero M che soddisfa le due seguenti proprietà:
• M divide a e b;
• se c è un intero che divide [...] due numeri interi, il massimo comune divisore tra due polinomi p e q può essere calcolato applicando l’algoritmodiEuclide oppure a partire da due fattorizzazioni note in polinomi irriducibili dei polinomi dati, effettuando il prodotto dei fattori ...
Leggi Tutto
Sturm, teorema di
Sturm, teorema di o regola di Sturm, algoritmo per la determinazione del numero di zeri reali di un polinomio a coefficienti reali p(x) compresi tra due dati valori a e b che non siano [...] di p(x). La regola di Sturm consente di determinare con esattezza (a differenza del metodo di → Budan-Fourier) il numero di radici reali di un polinomio a coefficienti reali che cadono in un intervallo. A tal fine si applica l’algoritmodi → Euclide ...
Leggi Tutto
Informazione e computazione quantistica: teoria
Mario Rasetti
Al crocevia tra scienza e tecnologia
La nuova disciplina che va sotto il nome di informazione e computazione quantistica si sviluppa al [...] , trovare il massimo comune divisore fra due numeri (per es., con l’algoritmodiEuclide) non richiede che risorse di tempo polinomiali, si individueranno i fattori primi di N in modo efficiente se si riuscirà a determinare r in tempo polinomiale ...
Leggi Tutto
metodo
mètodo s. m. [dal lat. methŏdus f., gr. μέϑοδος f., «ricerca, indagine, investigazione», e anche «il modo della ricerca», comp. di μετα- che include qui l’idea del perseguire, del tener dietro, e ὁδός «via», quindi, letteralmente «l’andar...