Home

Federica EU

1/11

Maria De Falco » 2.Complessità dell'algoritmo delle divisioni successive

Complemento a due

Sia k un numero naturale positivo e sia
S = {n ∈ ${\hbox {\symb Z}}$ tali che |n| < 2^k}
Nell’insieme {0,1}^k⁺¹ si può introdurre un’operazione ⊥ ponendo
(a_k a_k₋₁ … a₀) ⊥ (b_k b_k₋₁ … b₀) uguale alla (k +1)−pla ottenuta da
(a_k a_k₋₁ … a₀)₂ + (b_k b_k₋₁ … b₀)₂ elidendo un eventuale “overflow”
Inoltre nell’insieme {0, 1}^k⁺¹ si può introdurre un’operazione ◊ che ha lo stesso procedimento dell’operazione · tra numeri positivi in base 2, utilizzando però ⊥ al posto di +.
Si ponga 0^{^}=1 e 1^{^}=0.
Per ogni (a_k a_k₋₁ … a₀) appartenente a {0,1}^k⁺¹, la (k+1)-pla
(a_k, a_k₋₁, … , a₀)^{^} = (a_k^{^}, a_k₋₁^{^}, … , a₀^{^}) ⊥ (0, … ,0, 1)
si chiama complemento a due di (a_k, a_k₋₁, … , a₀).
E’ facile dimostrare che valgono le seguenti condizioni:

(0,…,0)^=(0,…,0)
(1,0,…,0)^=(1,0,…,0)
per ogni x appartenente a {0,1}^k⁺¹ , x⊥ x^ = (0,…,0)

Complemento a due

Si consideri ora la funzione f:S → {0,1}^k⁺¹\{(1,0,…,0)}definita ponendo

f(n)=(0, a_k₋₁, … , a₀) se n≥0 e n=(a_k₋₁ … a₀)₂

f(n)=(f(-n))^ se n<0

Proposizione 2.1 (senza dimostrazione)
La funzione f su definita verifica le seguenti proprietà:

se n e m sono elementi di S tali che n+m appartiene a S, allora f(n)⊥f(m)=f (n+m)
se n e m sono elementi di S tali che nm appartiene a S, allora f(n)◊f(m)=f (nm)
f è biettiva

Complemento a due

Tenendo conto della Proposizione 2.1, si ha:

se si stanno eseguendo algoritmi per i quali sia gli input che gli output appartengono a S, la funzione f viene utilizzata per estendere la rappresentazione in base 2 dall’insieme {n ∈ S tali che n≥0}a tutto l’insieme Se e le operazioni ⊥ e ◊ vengono utilizzate come rappresentazioni della somma e del prodotto tra essi
estendendo la terminologia introdotta per i numeri positivi scritti in base 2, se x=(a_k,a_k₋₁, … ,a₀) è un elemento di {0,1}^k⁺¹\{(1,0,…,0)}, le componenti a_k,a_k₋₁, … ,a₀vengono chiamate cifre binarie di x. Se x e y sono elementi di {0,1}^k⁺¹\{(1,0,…,0)}, ogni operazione eseguita su una singola cifra binaria nel calcolo di x⊥ye x*y è chiamata operazione elementare
se x e y sono elementi di {0,1}^k⁺¹\{(1,0,…,0)}, eseguire x⊥y richiede O(k) operazioni elementari e eseguire x◊y richiede O(k²) operazioni elementari

Complessità delle operazioni tra numeri interi

Utilizzando il meccanismo appena descritto, si ha:

Proposizione 2.2

Se n e m sono interi relativi tali che |n| e |m| sono minori o uguali di un intero positivo r, allora:

eseguire n +m richiede O(log r) operazioni elementari
eseguire nm richiede O((log r)²) operazioni elementari

Algoritmo delle divisioni successive

Si enuncerà e si dimostrerà ora un teorema, noto come algoritmo delle divisioni successive.
Si ricordi che la funzione di ${\hbox {\symb Z}}$ \{0} in $\symb N_0$ che associa ad ogni numero intero diverso da 0 il suo valore assoluto, rende ${\hbox {\symb Z}}$ anello euclideo.
L’algoritmo delle divisioni successive verrà enunciato scegliendo come ambiente un qualunque anello euclideo, in modo da poterlo utilizzare non solo in questa lezione, nell’ambiente ${\hbox {\symb Z}}$ dei numeri interi, ma anche successivamente nell’anello dei polinomi ad una indeterminata a coefficienti in un opportuno campo.

Teorema 2.3 (algoritmo delle divisioni successive)
Sia A un anello euclideo. Se a e b sono elementi di A\{0}, esiste un massimo comun divisore d di a e b. Inoltre esistono u , v є A tali che d=au+bv.

Algoritmo delle divisioni successive

Dimostrazione

Sia g:A → $\symb N_0$ la funzione che rende A anello euclideo.
Esistono elementi q₁ e r₁ di A tali che a=bq₁+r₁ con r₁=0 oppure g(r₁)<g(b).
Se r₁ è diverso da 0, esistono elementi q₂ e r₂ di A tali che b=r₁q₂+r₂ con r₂=0 oppure g(r₂)<g(r₁).
Si ponga a=r_-1,b=r₀ , e si supponga di aver determinato degli elementi r₁, r₂ ,…, r_i-1 appartenenti a A\{0} tali che g(b)>g(r₁)>g(r₂)>…>g(r_i-1).
Allora esistono elementi q_i e r_i di A tali che r_i-2=r_i-1q_i+r_i con r_i=0 oppure g(r_i)<g(r_i-1).
Sia t il minimo numero naturale tale che r_t+1=0 ⇒ r_t-1=r_tq_t+1.

Algoritmo delle divisioni successive

Se t=0, allora a=bq₁, sicché b è un massimo comun divisore di a e b, e l’asserto è dimostrato perché b=a∙0+b∙1.
Da adesso in poi si supporrà t ≥1.
Si tenga presente che per ogni con i≥t, i resti r_i-2,r_i-1 , r_isono legati dalle relazioni:

r_i-2=r_i-1q_i+r_ie quindi r_i=r_i-2- r_i-1q_i

Si proverà ora che r_t è un massimo comun divisore di a e b.
Da r_t-1=r_tq_t+1 segue che r_t è un divisore di r_t-1.
Si supponga che per qualche i=1,…,t, si abbia che r_t è un divisore di r_j per ogni j≥i-1; allora da r_i-2=r_i-1q_i+r_i segue che r_t è un divisore anche di r_i-2.
Dunque r_t è un divisore di r_i per ogni i=-1, 0,…,t, e quindi è un divisore sia di a che di b.
Sia ora c un qualunque divisore comune di a e b; si proverà che c è un divisore di r_t.
Si supponga che per qualche i=1,…,t , si abbia che c è un divisore di r_j per ogni j≤i-1; allora da r_i=r_i-2– r_i-1q_i, segue che c è un divisore anche di r_i.
Dunque c è un divisore di r_i per ogni i=-1, 0,1,…,t, e quindi è un divisore sia di r_t.
Si è dunque provato che r_tè un massimo comun divisore di a e b

Algoritmo delle divisioni successive

Si determineranno ora degli elementi u e v tali che r_t=au+bv.
Ponendo u_t=0 e v_t=1, si ha r_t=u_tr_t-1+v_tr_t .
Si supponga che per qualche i=1,…,t esistano elementi u_i e v_i tali che r_t=u_ir_i-1+v_ir_i; allora da r_i=r_i-2– r_i-1q_i, segue che r_t=u_ir_i-1+v_ir_i=u_ir_i-1+v_i(r_i-2-r_i-1q_i)=v_ir_i-2+(u_i-v_iq_i)r_i-1 e quindi

ponendo u_i-1=v_i e v_i-1=u_i-v_iq_i si ha r_t=u_i-1 r_i-2 + v_i-1 r_i-1

Al termine di questo procedimento si determinano u₀ e v₀ tali che r_t=u₀r_-1+v₀r₀=u₀a+v₀b.

Complessità dell’algoritmo delle divisioni successive in Z

Teorema 2.4
Siano a e b numeri interi tali che a≥b>0. Allora:

determinare un massimo comun divisore d di a e b con l’algoritmo delle divisioni successive ha complessità O((log a)³)
determinare degli interi u e v tali che d=au+bv con l’algoritmo delle divisioni successive ha complessità O((log a)³)

Dimostrazione
Si ponga a=r_-1 e b=r₀ e sia

r₁ > … > r_i-2 > r_i-1> r_i > … > r_t=d

la catena dei resti.

Complessità dell’algoritmo delle divisioni successive in Z

Si può supporre che sia t ≥ 1 (sicché, in particolare, a>b).

Si ricordi che per ogni con i≥t, i resti r_i-2,r_i-1 , r_isono legati dalla relazione:

r_i=r_i-2– r_i-1q_i

Dunque per ogni i≥t, si ha r_i-2 =r_i-1q_i + r_i ≥ r_i-1 + r_i > 2r_i
In particolare,
a>r₀>2r₂ >4r₄ > … ⇒ a>2ⁱr_2i per ogni i≥0
a>r₀>r₁ >2r₃ >4r₅ > … ⇒ a>2ⁱr_2i+1 per ogni i≥0

Complessità dell’algoritmo delle divisioni successive in Z

Sia j il numero naturale tale che t=2j oppure t=2j+1 .
Allora in entrambi i casi, si ha a>2^jr_t ≥2^j e quindi log₂a>j ⇒ 2log₂a ≥ 2j+1 ≥t ⇒ t=O(log a).

Da quanto detto segue che per determinare d si eseguono O(log a) divisioni euclidee ciascuna delle quali ha complessità O((log a)²), per una complessità totale di O((log a)³).
Nella dimostrazione del Teorema 2.3 si è visto che per determinare la coppia (u,v), si pone

(u_t , v_t)=(0,1) e (u_i-1 , v_i-1)=(v_i , u_i-v_iq_i);

la coppia (u,v) cercata è la coppia (u₀ ,v₀) che si ottiene alla fine di questo processo.
Quindi |u_t|=0≤r_t e |v_t|=1≤r_t-1 .
Si supponga |u_j|≤r_j e |v_j|≤r_j-1; allora |u_j-1|=|v_j|≤r_j-1 e |v_j-1|=|u_j-v_jq_j|≤ |u_j|+|v_j|∙|q_j| ≤ r_j+ r_j-1 q_j=r_j-2 .
Allora per ogni i≤t, |u_i|≤|r_i| e |v_i|≤|r_i-1|.
D’altra parte, per ogni i≤t, il calcolo di (u_i-1 , v_i-1) partendo (u_i , v_i) consiste solo nell’eseguire u_i-v_iq_i ; poiché |u_i|≤a, |v_i|≤a e |q_i|≤a, segue dalla Proposizione 2.2 che tale calcolo ha complessità O((log a)²).
Dunque determinare (u,v) ha complessità O(t ∙ (log a)²) e quindi O((log a)³).