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
 
I corsi di Scienze Matematiche Fisiche e Naturali
 
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