Didattica e Fondamenti degli Algoritmi e della Calcolabilità

Didattica e Fondamenti degli Algoritmi e della Calcolabilità

Quinta giornata

Risolvere efficientemente un problema in P: ancora sulla sequenza di Fibonacci.

Il problema dell’ordinamento

Guido Proietti

Email: guido.proietti@univaq.it

URL: www.di.univaq.it/~proietti/index_personal

• Stiamo cercando di calcolare efficientemente l’n- esimo numero della sequenza di Fibonacci

• Abbiamo progettato 3 algoritmi:

– Fibonacci1, non corretto in quanto approssima la soluzione

– Fibonacci2, che impiega tempo esponenziale in n

– Fibonacci3/4, che impiega tempo proporzionale ad n

• Dovevate dimostrare che per fibonacci2(n) T(n) = F

+ 2 (F

-1) = 3F

-2

Punto della situazione

# Foglie # Nodi interni

Dimostrazione del Lemma 2

Lemma 2: Il numero di nodi interni di un albero strettamente binario è pari al numero di foglie – 1.

Dim: Per induzione sul numero di nodi interni, sia detto k:

– Caso base k=1: se c’è un solo nodo interno, poiché per ipotesi deve avere due figli, tali figli saranno foglie, e quindi il lemma segue.

– Caso k>1: supposto vero fino a k-1, dimostriamolo vero per k nodi interni;

osserviamo che poiché k>1, e l’albero è strettamente binario, abbiamo due possibilità:

1. Uno dei due sottoalberi della radice è una foglia: in tal caso l’altro

sottoalbero (strettamente binario) contiene k-1 nodi interni, e quindi per ipotesi induttiva avrà k foglie; allora, il numero totale di foglie è k+1, da cui segue il lemma;

2. Entrambi i sottoalberi (strettamente binari) contengono nodi interni, in numero totale di k-1=k₁+k₂; ma allora, per ipotesi induttiva, conterranno rispettivamente k₁+1 e k₂+1 foglie, e quindi il numero totale di foglie è

• Possiamo sperare di calcolare F_n in tempo inferiore a Θ(n) (in termini di numero di linee di codice eseguite)? Sembrerebbe impossibile, perché parrebbe che per arrivare ad F_n dobbiamo prima calcolare F_i per ogni i<n

• In realtà, a ben pensarci, l’unico costo che siamo sicuri di dover necessariamente sostenere oltre a quello di lettura dell’input, è quello di scrittura dell’output; esso è esponenziale nel valore in input n (cresce infatti come Θ(ⁿ)), e richiede quindi la scrittura di Θ(log ⁿ) = Θ(n) bit, ma nel modello RAM le operazioni di lettura e scrittura hanno tutte costo unitario! In tale modello, potremmo quindi addirittura pensare di calcolare F_n in tempo costante, ed effettivamente Fibonacci1 è corretto su una RAM!

• Continuiamo quindi a lavorare su una RAM astratta, pensando comunque di pagare O(1) per lettura /scrittura di input/output, ma cerchiamo di ridurre il numero di linee di codice eseguite.

Un nuovo algoritmo

• Fibonacci4 non è il miglior algoritmo possibile

• È possibile dimostrare per induzione la seguente proprietà di matrici:

Potenze ricorsive

1 0 1 1

n = F

F

F

F

• Useremo questa proprietà per progettare un algoritmo più efficiente

1 0 1 1

n volte

1 0 1 1

=  … 

Prodotto di matrici righe per colonne

(AB)

=  a

b

k=1 n

i=1,…, n j=1,…, n

 







 









n n n

n

a a

a a

A

, 1

,

, 1 1

, 1











 







 









n n n

n

b b

b b

B

, 1

,

, 1 1

, 1











Dimostrazione per induzione

Base induzione: n=2

1 1 1 0

2

= F

F

F

F

1 0 1 1 1 1

 1 0 = 2 1

1 1 =

F

F

F

F

Hp induttiva: 1 1

1 0

n-1

= F

F

F

F

1 0 1 1

n

= F

F

F

F

1 1

 1 0 F

+ F

F

+ F

= F

=

F





Algoritmo fibonacci5

• Osserva che il ciclo arriva fino ad n-1, poiché come abbiamo appena dimostrato, e quindi M[1][1]=F_n

• Il tempo di esecuzione è T(n)=2+n+n-1 = Θ(n)

• Possiamo migliorare?

1 0 1 1

n-1

= F

F

F

F

• Possiamo calcolare la n-esima potenza elevando al quadrato la n/2 - esima potenza

• Se n è dispari eseguiamo una ulteriore moltiplicazione

• Esempio: se devo calcolare 3

:

3

= (3

)

= [(3

)

]

= [(3·3)

]

= [(9)

]

= [(9·9)]

= [81]

= 81·81 = 6561

• Esempio: se devo calcolare 3

:

3

= 3·(3

)

= 3·(3·(3)

)

= 3·(3·(3·3))

= 3·(3·9)

= 3·(27)

= 3·(27·27) = 3·(729) = 2187

Calcolo di potenze

 Ho eseguito solo 3 prodotti invece di 8

 Ho eseguito solo 4 prodotti invece di 7

Algoritmo fibonacci6

passaggio per valore

• Tutto il tempo è speso nella funzione potenzaDiMatrice

– All’interno della funzione si spende tempo costante – Si esegue una chiamata ricorsiva con input n/2

• L’equazione di ricorrenza è pertanto:

Tempo di esecuzione

T(n) = T(n/2) + Θ(1)

Metodo dell’iterazione

Si può dimostrare che

T(n) = Θ(log

n )

Infatti: T(n)=T(n/2)+Θ(1)=(T( n/2

)+Θ(1))+Θ(1)=

=((T(n/2

)+Θ(1))+Θ(1))+Θ(1)=…

e per k = log

n si ha n/2

 = 1 e quindi

T(n)=((…(T(n/2

)+Θ(1))+…+Θ(1))+Θ(1))+Θ(1)

= T(1)+k∙Θ(1) = Θ(1) + log

n∙Θ(1) = Θ(log n) fibonacci6 è quindi esponenzialmente più

veloce di fibonacci5!

Riepilogo costi su una RAM

fibonacci6 fibonacci5 fibonacci4 fibonacci3 fibonacci2

Θ(log n) Θ(n) Θ(n) Θ(n) Θ(ⁿ)

Θ(log n)*

Θ(1) Θ(1) Θ(n) Numero di linee di

codice

Occupazione di memoria

fibonacci1 Θ(1) Θ(1)

Θ(ⁿ)

* per le variabili di lavoro delle Θ(log n) chiamate ricorsive

La RAM a costi logaritmici

• La RAM a costi logaritmici è un modello di calcolo più realistico quando si opera su

algoritmi numerici: per manipolare un numero n, richiede log n operazioni

• In questo modo, anche l’accesso all’ i-esima locazione di un array non costa più O(1),

ma O(log i)

Costi su una RAM a costi logaritmici

fibonacci6 fibonacci5 fibonacci4 fibonacci3 fibonacci2

Θ(n log ⁿ)=Θ(n²) Θ(n ⁿ)

Θ(n log n)*

Θ(n) Θ(n) Θ(n log n)

Tempo di esecuzione (si ricordi che la dimensione

dell’input è Θ(log n))

Occupazione di memoria (# bit) fibonacci1 Θ(log ⁿ) = Θ(n) Θ(n)

Θ(ⁿ)

* per le variabili di lavoro delle Θ(log n) chiamate ricorsive

Θ(n log ⁿ)=Θ(n²) Θ(n log ⁿ)=Θ(n²)

Θ(log n log ⁿ)

= Θ(n log n)

Algoritmi non numerici

Dato un insieme S di n elementi presi da un dominio totalmente ordinato, ordinare S

Il problema dell’ordinamento

• Esempi: ordinare una lista di nomi

alfabeticamente, o un insieme di numeri, o un insieme di compiti d’esame in base al cognome dello studente

• Subroutine in molti problemi

• È possibile effettuare ricerche in array ordinati in

tempo O(log n) (ricerca binaria)

Il problema dell’ordinamento (non decrescente)

• Input: una sequenza di n numeri (reali) <a

,a

,

…,a

>

(NOTA: la dimensione dell’input è n)

• Output: una permutazione {1,2,…,n}  {i

,i

,

…,i

}, ovvero un riarrangiamento <a

, a

,…, a

> della sequenza di input in modo tale che a

 a … a

SelectionSort

1 2 4 5 3 7 7 2 4 5 3 1

1 2 4 5 3 7 1 2 3 5 4 7

1 2 3 4 5 7

1 2 3 4 5 7 1 2 3 4 5 7

Approccio incrementale: assumendo che i primi k elementi siano ordinati, estende l’ordinamento ai primi k+1

elementi scegliendo il minimo degli n-k elementi non

ancora ordinati e mettendolo in posizione k+1

SelectionSort (A)

1. for k=1 to n-1 do 2. m = k

3. for j=k+1 to n do

4. if (A[j] < A[m]) then m=j 5. scambia A[m] con A[k]

• linea 2: m mantiene l’indice dell’array in cui si trova il minimo corrente

• linee 3-4: ricerca del minimo fra gli elementi A[k],…,A[n] (m viene aggiornato con l’indice dell’array in cui si trova il minimo corrente)

• linea 5: il minimo è spostato in posizione k

NOTA: Assumiamo che il primo elemento dell’array sia in A[1]

Correttezza

• Si dimostra facendo vedere che alla fine del generico passo k (k=1,…, n-1) si ha: (i) i primi k elementi sono ordinati e (ii) contengono i k elementi più piccoli dell’array

• Induzione su k:

– k=1: Alla prima iterazione viene semplicemente selezionato l’elemento minimo dell’array  (i) e (ii) banalmente verificate.

– k>1. All’inizio del passo k i primi k-1 elementi sono ordinati e sono i k-1 elementi più piccoli nell’array (ipotesi induttiva).

Allora la tesi segue dal fatto che l’algoritmo seleziona il minimo dai restanti n-k elementi e lo mette in posizione k. Infatti:

(ii) i primi k elementi restano i minimi nell’array

(i) l’elemento in posizione k non è mai più piccolo dei primi k-1 elementi

• Sia tempo(I) il tempo di esecuzione di un algoritmo sull’istanza I

T

(n) = min

{tempo(I)}

• Intuitivamente, T

(n) è il tempo di

esecuzione sulle istanze di ingresso che comportano meno lavoro per l’algoritmo, mentre T(n) ricordiamo che denotava il tempo di esecuzione sulle istanze di

ingresso che comportano più lavoro per l’algoritmo (c’era un max invece di min)

Caso migliore di un algoritmo

• Sia P(I) la probabilità di occorrenza del- l’istanza I

T

(n) = ∑

{P(I) tempo(I) }

• Intuitivamente, T

(n) è il tempo di esecuzione nel caso medio, ovvero sulle istanze di

ingresso “tipiche” per il problema

• Richiede di conoscere una distribuzione di probabilità sulle istanze

Caso medio di un algoritmo

Complessit à temporale

SelectionSort (A)

1. for k=1 to n-1 do 2. m = k

3. for j=k+1 to n do

4. if (A[j] < A[m]) then m=j 5. scambia A[m] con A[k]

n-k confronti

(operaz. dominante) 1 scambio

(3 assegnamenti)

il tutto eseguito per k=1,…, n-1

T(n) =  [1+(n-k)+1]=2(n-1)+  k =2(n-1)+n·(n-1)/2 = (n

)

k=1 n-1

 T(n) = T (n) = T (n) = (n

)

k=1 n-1

1 assegnamento

Si noti che T(n) è SEMPRE UGUALE ad un polinomio di 2º grado in n, e quindi la notazione Θ è perfettamente ESPRESSIVA del valore di T(n)

Denotiamo con T(n) il costo di esecuzione dell’algoritmo su una generica esecuzione; si noti che T(n) ≤ T_worst(n) e T(n)≥T_best(n)