Lezione del 13 marzo 2009 Osservazione: Se la funzione TimeA

(1)

Lezione del 13 marzo 2009

Osservazione: Se la funzione Time

A

(n), che calcola il numero di operazioni elementari eseguite dall’algoritmo A per un input di dimensione n (nel caso peggiore), viene calcolata in funzione dell’input x (e non della sua dimensione n) e se essa risulta di ordine polinomiale O(x

^k

), possiamo notare che l’algoritmo A ha allora complessità esponenziale in n: infatti esisterà una costante C tale che il numero di operazioni elementari eseguite dall’algoritmo A per un input x sia  Cx

^k

, e tenendo conto che x < 2

ⁿ

(essendo n la lunghezza binaria di x) si ricava:

Time

A

(n)  C(2

^k

)

ⁿ

dunque Time

A

(n) è di ordine esponenziale O(a

ⁿ

) dove a=2

^k

. Complessità di alcuni algoritmi aritmetici.

a) Costruiamo un algoritmo A=Somma(x,y) per calcolare la somma x+y di due numeri naturali x,y dati in input: supponiamo che, se n=L(x),m=L(y) sono le lunghezze binarie degli addendi, si abbia nm.

L’algoritmo di somma si può eseguire con gli stessi metodi che si usano per sommare numeri naturali rappresentati in base 10, utilizzando le operazioni elementari di somma sui singoli bits:

- si incolonna la rappresentazione binaria di y sotto quella di x, aggiungendo (se n>m) n-m bits=0 alla sinistra dei bits di y

- si inizializza il valore del riporto c=0

- procedendo da destra verso si sinistra si somma ogni bit di x con il bit dello stesso posto di y (con l’operazione elementare BitSum di somma di bits), ottenendo ad ogni passo una delle cifre binarie di x+y e un nuovo valore del riporto c

- se l’ultimo riporto è c=1 si aggiunge a sinistra un ulteriore bit=1 nel risultato x+y - si esce con output x+y

Per esempio se x=(110011)

2

, y=(1101) allora:

110011+

001101 1000000

dunque il risultato della somma è x+y=(1000000)

2

. Schematizzando l’algoritmo:

1) input x=(a

n-1

a

n-2

…..a

1

a

0

)

2

, y=(b

m-1

b

m-2

…..b

1

b

0

)

2

con n=L(x) m=L(y) 2) se n>m si pone b

m

=b

m+1

=…=b

n-1

=0

3) c=0

4) per i=0,1…,n-1 si calcola BitSum(a

i

,b

i

,c)=(t,c

1

) e si pone z

i

=t, c=c

1

5) se c=1 si pone z

n

=1

6) si esce con output x+y=(z

n

z

n-1

…..z

1

z

0

)

2

In tale algoritmo si eseguono n operazioni elementari, dunque Time

A

(n)=O(n), e l’algoritmo ha complessità polinomiale (lineare).

b) Costruiamo un algoritmo A=Diff(x,y) per calcolare la differenza x-y di due numeri naturali x,y

(con x>y) dati in input: se n=L(x),m=L(y) sono rispettivamente le lunghezze binarie, si avrà

certamente nm.

(2)

Si può ricondurre il caso a quello dell’algoritmo Somma(x,y) con il seguente ragionamento:

consideriamo il numero binario y

1

ottenuto da y sostituendo ogni bit 0 con 1 e viceversa e poi aggiungendo a sinistra (n-m) bits =1 (quindi y+y

1

è un numero binario con n bits tutti=1 cioè y+y

1

=2

ⁿ

-1).

Si ha dunque y+(y

1

+1)=2

ⁿ

(y

1

+1 è il cosiddetto “complemento a 2 di y”) da cui x-y=x+(y

1

+1)-2

ⁿ

. Quindi per ottenere x-y basta sommare x con il complemento a 2 di y e poi sottrarre 2

ⁿ

al risultato (il che equivale ad elidere l’ultimo bit =1 a sinistra): poiché nel calcolo di x+(y

1

+1) (addendi lunghezza ≤n ) si esegue (vedere algoritmo Somma(x,y)) un numero n di operazioni elementari, si conclude che Time

A

(n)=O(n), e anche questo algoritmo ha complessità polinomiale (lineare).

c) Costruiamo un algoritmo A=Prod(x,y) per calcolare il prodotto x+y di due numeri naturali x,y dati in input: supponiamo che, se n=L(x),m=L(y) sono le lunghezze binarie dei fattori, si abbia nm.

L’algoritmo di prodotto si può eseguire con gli stessi metodi che si usano per moltiplicare numeri naturali rappresentati in base 10, utilizzando le operazioni elementari di somma sui singoli bits.

Si costruiscono (al più) m righe (una riga in meno per ogni bit =0 in y) ognuna consistente nella copia del numero binario y shiftato opportunamente verso sinistra di un certo numero di posti (il che equivale ad aggiungere a destra dei bits =0) e si sommano tutte le righe (pensate come numeri binari): per contare il numero di operazioni elementari, supponiamo di sommare le righe 2 alla volta (la prima con la seconda, la terza con il risultato della somma della prima con la seconda etc.) eseguendo in totale un numero ≤m-1 di somme fra numeri di lunghezza ≤n+m, e poiché ognuna di tali somme corrisponde ad un numero ≤n+m di operazioni elementari di somma di bits, in totale il numero di operazioni elementari nell’algoritmo è ≤(n+m)(m-1)<n

²

ossia Time

A

(n)=O(n

²

), e anche questo algoritmo ha complessità polinomiale (quadratica).

Per esempio se x=(11011)

2

, y=(1011) allora:

11011x 1011

11011 (si suppone di sommare la prima riga 11011 con la seconda 110110 e poi 110110 sommare il risultato con la terza riga 11011000)

11011000 100101001

dunque il risultato del prodotto è xy=(100101001)

2

.

Tale algoritmo di prodotto non è il più efficiente: esiste un algoritmo più sofisticato che ha complessità O(nlog(n)log(log(n))) “minore” di O(n

²

) (perché lim

n

[nlog(n)log(log(n))]/n

²