Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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| < 2k}
Nell’insieme {0,1}k+1 si può introdurre un’operazione ⊥ ponendo
(ak  ak1   …  a0) ⊥ (bk  bk1   …  b0) uguale alla (k +1)−pla ottenuta da
(a ak1  …   a0) 2 + (b bk1  …   b0) 2  elidendo un eventuale “overflow”
Inoltre nell’insieme {0, 1}k+1 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 (ak  ak1   …  a0) appartenente a  {0,1}k+1, la (k+1)-pla
(ak , ak1 ,  … , a0)^ = (ak^  , ak1,  … , a0^ ) ⊥  (0, … ,0, 1)
si chiama complemento a due di  (ak , ak1 ,  … , a0).
E’ facile dimostrare che valgono le seguenti condizioni:

  1. (0,…,0)^=(0,…,0)
  2. (1,0,…,0)^=(1,0,…,0)
  3. per ogni x appartenente a {0,1}k+1 , x⊥ x^ = (0,…,0)

Complemento a due

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

f(n)=(0, ak1 ,  … , a0) se n≥0 e n=(ak1   …  a0)2

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

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

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

Complemento a due

Tenendo conto della Proposizione 2.1, si ha:

  1. 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
  2. estendendo la terminologia introdotta per i numeri positivi scritti in base 2, se x=(ak ,ak1 ,  … ,a0) è un elemento di {0,1}k+1\{(1,0,…,0)}, le componenti ak ,ak1 ,  … ,a0 vengono chiamate cifre binarie di x. Se x e y sono elementi di {0,1}k+1\{(1,0,…,0)}, ogni operazione eseguita su una singola cifra binaria nel calcolo di x⊥ye x*y è chiamata operazione elementare
  3. se x e y sono elementi di {0,1}k+1\{(1,0,…,0)}, eseguire x⊥y richiede O(k) operazioni elementari e eseguire x◊y richiede O(k2) 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)2) 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 q1 e r1 di A tali che a=bq1+r1 con r1=0 oppure g(r1)<g(b).
Se r1 è diverso da 0, esistono elementi q2 e r2 di A tali che b=r1q2+r2 con r2=0 oppure g(r2)<g(r1).
Si ponga a=r-1 ,b=r0 , e si supponga di aver determinato degli elementi r1, r2 ,…, ri-1 appartenenti a A\{0} tali che g(b)>g(r1)>g(r2)>…>g(ri-1).
Allora esistono elementi qi e ri di A tali che ri-2=ri-1qi+ri con ri=0 oppure g(ri)<g(ri-1).
Sia t il minimo numero naturale tale che rt+1=0  ⇒  rt-1=rtqt+1.

Algoritmo delle divisioni successive

Se t=0, allora a=bq1, 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    ri-2 ,ri-1 , ri    sono legati dalle relazioni:

ri-2=ri-1qi+ri          e quindi     ri=ri-2 - ri-1qi

Si proverà ora che rt è un massimo comun divisore di a e b.
Da  rt-1=rtqt+1 segue che rt è un divisore di rt-1  .
Si supponga che per qualche i=1,…,t, si abbia che rt è un divisore di rj per ogni j≥i-1; allora da ri-2=ri-1qi+ri segue che rt è un divisore anche di ri-2.
Dunque rt è un divisore di ri  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 rt.
Si supponga che per qualche i=1,…,t , si abbia che c è un divisore di rj per ogni j≤i-1; allora da ri=ri-2 – ri-1qi , segue che c è un divisore anche di ri .
Dunque c è un divisore di ri per ogni i=-1, 0,1,…,t, e quindi è un divisore sia di rt .
Si è dunque provato che rt è un massimo comun divisore di a e b

Algoritmo delle divisioni successive

Si determineranno ora degli elementi u e v tali che rt=au+bv.
Ponendo ut=0 e vt=1, si ha rt=utrt-1+vtrt .
Si supponga che per qualche i=1,…,t  esistano elementi ui e vi tali che rt=uiri-1+viri ; allora da ri=ri-2 – ri-1qi , segue che rt=uiri-1+viri=uiri-1+vi(ri-2-ri-1qi)=viri-2+(ui-viqi)ri-1  e quindi

ponendo ui-1=vi  e  vi-1=ui-viqi  si  ha  rt =ui-1 ri-2 + vi-1 ri-1

Al termine di questo procedimento si determinano u0 e v0 tali che rt=u0r-1+v0r0=u0a+v0b.

Complessità dell’algoritmo delle divisioni successive in Z

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

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

Dimostrazione
Si ponga a=r-1  e   b=r0 e sia

r1 > … > ri-2 > ri-1> ri > … > rt=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    ri-2 ,ri-1 , ri    sono legati dalla relazione:

ri=ri-2 – ri-1qi

Dunque per ogni i≥t, si ha ri-2 =ri-1qi + ri ≥ ri-1 + ri > 2ri
In particolare,
a>r0>2r2 >4r4 > …  ⇒  a>2ir2i  per ogni i≥0
a>r0>r1 >2r3 >4r5 > …  ⇒  a>2ir2i+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>2j rt ≥2j  e quindi  log2a>j  ⇒  2log2a ≥ 2j+1 ≥t  ⇒  t=O(log a).

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

(ut , vt)=(0,1)  e  (ui-1 , vi-1)=(vi , ui-viqi);

la coppia (u,v) cercata è la coppia (u0 ,v0) che si ottiene alla fine di questo processo.
Quindi |ut|=0≤rt  e  |vt|=1≤rt-1 .
Si supponga |uj|≤rj  e  |vj|≤rj-1 ; allora |uj-1|=|vj|≤rj-1 e |vj-1|=|uj-vjqj|≤ |uj|+|vj|∙|qj| ≤ rj+ rj-1 qj=rj-2 .
Allora per ogni i≤t, |ui|≤|ri|  e   |vi|≤|ri-1|.
D’altra parte, per ogni i≤t, il calcolo di (ui-1 , vi-1) partendo (ui , vi) consiste solo nell’eseguire ui-viqi ; poiché |ui|≤a, |vi|≤a e |qi|≤a, segue dalla Proposizione 2.2 che tale calcolo ha complessità O((log a)2).
Dunque determinare (u,v) ha complessità O(t ∙ (log a)2) e quindi O((log a)3).

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion