Didattica dei Fondamenti dell’Informatica 2

Didattica dei Fondamenti dell’Informatica 2

Seconda giornata: progettare un algoritmo corretto, efficiente, e possibilmente ottimo!

Guido Proietti

Email: guido.proietti@univaq.it

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

Richiamo: Complessità computazionale di un algoritmo e di un problema

Definizione

Un algoritmo A ha una complessità computazionale O(f(n)) su istanze di dimensione n se T(n)=O(f(n)), ove T(n) è il numero di passi elementari dell’algoritmo sulle istanze di ingresso di

dimensione n che comportano più lavoro per l’algoritmo stesso (ovvero, T(n) misura il caso peggiore dell’algoritmo)

Definizione

Un problema P ha una complessità computazionale O(f(n)) se esiste un algoritmo che risolve P la cui complessità

computazionale è O(f(n))

Richiamo: gerarchia delle classi

Decidibili

ExpTime

(ARRESTO(k)) P (ricerca)

NP NP-completi (SAT)

Progettare un algoritmo

Vogliamo progettare algoritmi (per problemi calcolabili!) che:

– Producano correttamente il risultato desiderato

– Siano efficienti in termini di tempo di

esecuzione ed occupazione di memoria

Le quattro proprietà fondamentali di un algoritmo (oltre l’efficienza)

• La sequenza di istruzioni deve essere finita

• Essa deve portare ad un risultato corretto

• Le istruzioni devono essere eseguibili materialmente

• Le istruzioni non devono essere ambigue

Algoritmi e strutture dati

• Concetto di algoritmo è inscindibile da quello di dato

• Da un punto di vista computazionale, un

algoritmo è una procedura che prende dei dati in input e, dopo averli elaborati, restituisce dei dati in output

 I dati devo essere organizzati e strutturati in modo tale che la procedura che li elabora sia

“efficiente”

Analisi di algoritmi

– dimostrare formalmente che un algoritmo è corretto

Complessità:

– Stimare la quantità di risorse (tempo e memoria) necessarie all’algoritmo

– stimare il più grande input gestibile in tempi ragionevoli

– confrontare due algoritmi diversi – ottimizzare le parti “critiche”

f(n) = (g(n)) se  due costanti c>0 e n

≥0 tali che f(n) ≥ c g(n) per ogni n ≥ n

Notazione asintotica 

f(n) = (g(n)) f(n)

c g(n)

Esempi

• Sia f(n) = 2n² - 5n; vogliamo dimostrare che f(n)=(n²).

f(n)/n² = (2n² - 5n)/n² = 2 - 5/n ma 2 - 5/n ≥ 1 per n ≥ 5

quindi basta scegliere c=1 e n₀=5 e avremo che 2n² - 5n ≥ 1n² per n ≥ n₀=5.

• f(n) = (n) (c=1, n₀=2)

• f(n) =(log n) (c=1, n₀=2)

• Invece, f(n)  (n³)

Legame con il concetto di limite

   f n g n 

n g

n

lim_n f  0   

       _ ^{ }_{ }  ⁰ n

g n lim f

n g n

f _n

     ^{ }_{ } (se esiste) 0 n

g n lim f

n g n

f    _n 

f(n) = (g(n)) se  tre costanti c

,c

>0 e n

≥0 tali che c

g(n) ≤ f(n) ≤ c

g(n) per ogni n ≥ n

Notazione asintotica 

n₀ n

f(n) = (g(n))

f(n) c₁ g(n) c₂ g(n)

Relazioni tra O, Ω e Θ

 n g(n) f n Og n 

f    

 n Og(n) f n Θg n 

f   

 n g(n) f n g n 

f     

 n g(n) f n Θg n 

f    

 n g(n) f n g n  e f n Og n 

f      

• 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

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

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

IL problema: l’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_n>

(NOTA: la dimensione dell’input è n)

• Output: una permutazione {1,2,…,n}  {i₁,i₂,…,i_n}, ovvero un riarrangiamento <a_i1, a_i2,…, a_in> della

sequenza di input in modo tale che a_i1  a_i2 … a_in

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

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) =





k=1 n-1

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

k=1 n-1

1 assegnamento

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

InsertionSort

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

2 4 7 5 3 1

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

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

elementi, inserendo l’elemento in posizione k+1-esima nella giusta posizione rispetto ai primi k elementi

InsertionSort (A)

1. for k=1 to n-1 do

2. x = A[k+1]

3. for j=1 to k+1 do

4. if (A[j] > x) then break 5. if (j < k+1) then

6. for t=k downto j do A[t+1]= A[t]

7. A[j]=x

• Linea 2: elemento x=A[k+1] da inserire nella posizione che gli compete

• Linee 3 e 4: individuano la posizione j in cui va messo x

• Linee 5 e 6: se la posizione j è diversa da k+1, si fa spazio per inserire x, “shiftando” tutti gli elementi da j a k verso destra

Correttezza

• Si dimostra facendo vedere che alla fine del generico

passo k (k=1,…, n-1) i primi k+1 elementi sono ordinati (si noti la differenza con il Selection Sort, in cui invece dovevamo far vedere anche che erano i più piccoli)

• Induzione su k:

– k=1: banale: si riordinano A[1] e A[2];

– k>1: All’inizio del passo k i primi k elementi sono ordinati (ipotesi induttiva). Allora la tesi segue dal fatto che

l’algoritmo inserisce A[k+1] nella giusta posizione rispetto alla sequenza A[1],…,A[k]

InsertionSort (A)

1. for k=1 to n-1 do

2. x = A[k+1]

3. for j=1 to k+1 do

4. if (A[j] > x) then break 5. if (j < k+1) then

6. for t=k downto j do A[t+1]= A[t]

7. A[j]=x

T(n) = (n)+



j*≤k+1 confronti k+1–j*

assegnamenti

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

k=1 n-1

T(n) = T

(n) = T

(n) = (n

)

k+1 oper.

Complessità temporale

1 assegnamento

InsertionSort2 (A)

1. for k=1 to n-1 do

2. x = A[k+1]

3. j = k

4. while j > 0 e A[j] > x do 5. A[j+1] = A[j]

6. j= j-1

7. A[j+1]=x

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

t_k ≤ 2k assegnam.





 tempo(n) = O(n

)

k=1 n-1

k=1 n-1

Una variante dell’IS più efficiente

Si noti che tempo(n) è AL PIÙ UGUALE ad un polinomio di 2º grado in n, e quindi la

Caso migliore, peggiore, e medio di InsertionSort2

• Caso migliore

– array già ordinato in ordine crescente  t_k = 0

 T_best(n) = (n) (costo del ciclo for esterno)

• Caso peggiore

– array ordinato in ordine decrescente  t_k = 2k

 T(n) =



• Caso medio

– L’elemento in posizione k+1 ha la medesima probabilità di essere inserito in ciascuna delle k posizioni che lo precedono  la sua posizione attesa è k/2  il valore atteso di t_k = k

 T (n) =





k=1

n-1 n-1

Legge di Murphy?

« Se qualcosa può andar male, lo farà. »

In realtà, negli algoritmi il caso medio costa spesso come il caso peggiore (asintoticamente), in quanto le

strutture di controllo fondamentali degli algoritmi sono i cicli, e spesso il caso medio implica l’esecuzione della metà delle istruzioni di un ciclo, senza quindi avere un abbattimento asintotico della complessità.

Riepilogo

Insertion Sort 2 Insertion Sort 1

Θ(n) Caso migliore Selection Sort Θ(n²)

Θ(n²)

Caso medio Θ(n²) Θ(n²) Θ(n²)

Θ(n²) Θ(n²) Θ(n²) Caso peggiore

Complessità spaziale

Ricordiamo che oltre alla complessità temporale

dobbiamo valutare anche la complessità spaziale di un algoritmo, ovvero lo spazio di memoria necessario per ospitare le strutture di dati utilizzate dall’algoritmo.

La complessità spaziale del Selection Sort e dell’Insertion Sort è Θ(n)

Nota: Se la complessità spaziale di un certo algoritmo è Θ(g(n)), e se tale algoritmo “ispeziona” l’intera memoria occupata, allora la complessità temporale dell’algoritmo è (g(n)), ovviamente.

Conseguenze per il problema dell’ordinamento

La complessità spaziale di qualsiasi algoritmo che risolve il problema dell’ordinamento è

(n)

…ma qualsiasi algoritmo che risolve il problema

dell’ordinamento deve ispezionare tutti i dati in ingresso, e quindi ha complessità temporale T(n)=(n)



Tutti gli algoritmi che risolveranno il problema

dell’ordinamento avranno una complessità temporale (n)

Delimitazioni inferiori (lower bound)

Definizione

Un algoritmo A ha complessità computazionale (g(n)) su istanze di dimensione n se T(n)=(g(n)) (significa che numero di passi elementari necessari per eseguire A nel caso peggiore è (g(n)), e quindi non è

detto che debbano essere necessari per ogni istanza di dimensione n:

istanze facili potrebbero richiedere meno risorse!)

Definizione (lower bound o complessità intrinseca di un problema) Un problema P ha una delimitazione inferiore alla complessità

computazionale (g(n)) se ogni algoritmo che risolve P ha complessità computazionale (g(n)).

Ottimalità di un algoritmo

Definizione

Dato un problema P con complessità intrinseca (g(n)), un algoritmo che risolve P è ottimo (in termini di complessità asintotica, ovvero a meno di costanti moltiplicative e di

termini additivi/sottrattivi di “magnitudine” inferiore) se ha complessità computazionale O(g(n)).

Quindi, per il problema dell’ordinamento…

• Upper bound temporale: O(n

)

– Insertion Sort, Selection Sort

• Lower bound temporale: (n)

– “banale”: dimensione dell’input

Abbiamo un gap lineare tra upper bound e lower bound!

Possiamo fare meglio, ovvero abbassare

l’upper bound e/o innalzare il lower bound ?

Ordinamento per confronti

Dati due elementi a_i ed a_j, per determinarne l’ordinamento relativo effettuiamo una delle seguenti operazioni di confronto:

a_i  a_j ; a_i  a_j ; a_i  a_j ; a_i  a_j ; a_i  a_j

Non si possono esaminare i valori degli elementi o ottenere informazioni sul loro ordine in altro modo.

Notare: Tutti gli algoritmi di ordinamento considerati fino ad ora sono algoritmi di ordinamento per confronto.

• Consideriamo un generico algoritmo A, che ordina eseguendo solo confronti: dimostreremo che A esegue (nel caso peggiore) (n log n) confronti

• Un generico algoritmo di ordinamento per confronti lavora nel modo seguente:

- Confronta due elementi a_i ed aj (ad esempio effettua il test ai  a_j);

- A seconda del risultato, riordina e/o decide il confronto successivo da eseguire.

 Un algoritmo di ordinamento per confronti può essere descritto in modo astratto usando un albero di decisione, nel quale i nodi interni rappresentano i confronti, mentre le foglie rappresentano gli output prodotti

Lower bound (n log n) per l’ordinamento

• Descrive le diverse sequenze di confronti che A esegue su un’istanza <a1,a₂,

…,a_n> di lunghezza n; i movimenti dei dati e tutti gli altri aspetti dell’algoritmo vengono ignorati

• Nodo interno (non foglia): i:j (modella il confronto tra a_i e a_j)

• Nodo foglia: i₁,i₂,…,i_n (modella una risposta (output) dell’algoritmo, ovvero una permutazione <a_i1,a_i2,…,a_in> degli elementi)

• L’albero di decisione è associato ad un algoritmo e alla dimensione n dell’istanza

Albero di decisione

Esempio

2:3

1,2,3 1:3 2,1,3 2:3

1:3 1:2

1,3,2 3,1,2 2,3,1 3,2,1

Š 

Š  Š 

Š 

Š 











Input <a₁,a₂,a₃> Riconoscete

l’algoritmo associato?

È proprio l’Insertion Sort 2!

Esercizio per casa: costruire l’albero di decisione

per il SS su una sequenza di 3 elementi.

• Per una particolare istanza, i confronti eseguiti da A su quella istanza rappresentano un cammino radice – foglia

• L’algoritmo segue un cammino diverso a seconda delle caratteristiche dell’input

– Caso peggiore: cammino più lungo – Caso migliore: cammino più breve

• Il numero di confronti nel caso peggiore è pari all’altezza dell’albero di decisione (ovvero alla lunghezza, in termini di numero di archi, del più lungo cammino radice-foglia)

Proprietà

Lemma: Un albero strettamente binario (ovvero, in cui ogni nodo interno ha esattamente due figli) con k foglie ha altezza h(k)  log₂ k.

Dim: Dimostrazione per induzione su k:

– Caso base k=1 (albero-nodo ): banale h(k)=0≥ log₂1=0

– Caso k>1: supposto vero per k-1 foglie, dimostriamolo per k; poiché la radice ha 2 figli, uno dei due suoi sottoalberi deve contenere

almeno la metà (parte intera sup.) delle foglie, e quindi

h(k) ≥1+h(k/2) ≥

1+log

(k/2)

=1+log

k-log

2=log

k.

QED

Altezza in funzione delle foglie

• Consideriamo l’albero di decisione di un qualsiasi algoritmo che risolve il problema dell’ordinamento di n elementi

• Tale albero deve avere almeno n! foglie: infatti, se l’algoritmo è corretto, deve contemplare tutti i possibili output, ovvero le n!

permutazioni della sequenza di n elementi in input

• Dal lemma precedente, avremo che l’altezza h(n) dell’albero di decisione sarà:

Il lower bound (n log n)

h(n)  log₂(#foglie)  log₂(n!)

Formula di Stirling:

n!  (2n)^1/2 ·(n/e)ⁿ

> log₂ (n/e)ⁿ =

= n log₂ (n/e)

= n log₂ n – n log₂ e

=

=

• Problema dell’ordinamento:

– Lower bound - (n log n) albero di decisione – Upper bound – O(n

) IS,SS

• Proviamo a costruire un algoritmo ottimo, usando la tecnica del divide et impera:

1 Divide: dividi l’array a metà

2 Risolvi il sottoproblema ricorsivamente

3 Impera: fondi le due sottosequenze ordinate

Un algoritmo ottimo: il MergeSort

(John von Neumann, 1945)

Esempio di esecuzione

7 2 4 5 3 1 5 6

7 2 4 5 3 1 5 6

7 2 4 5 3 1 5 6

7 2 4 5 3 1 5 6

1 2 3 4 5 5 6 7

2 4 5 7 1 3 5 6

2 7 4 5 1 3 5 6

7 2 4 5 3 1 5 6

input output

Input ed output delle

chiamate

ricorsive

• Due array ordinati A e B possono essere fusi rapidamente:

– estrai ripetutamente il minimo di A e B e copialo nell’array di output, finché A oppure B non

diventa vuoto

– copia gli elementi dell’array non ancora

completamente svuotato alla fine dell’array di output

Fusione di sequenze ordinate

Notazione: dato un array A e due indici x  y, denotiamo con A[x;y] la porzione di A costituita da A[x], A[x+1],…,A[y]

Merge (A, i₁, f₁, f₂)

1. Sia X un array ausiliario di lunghezza f₂-i₁+1 2. i=1

3. i₂=f₁+1

4. while (i₁ f₁ e i₂  f₂) do 5. if (A[i₁]  A[i₂]) 6. then X[i]=A[i₁]

7. incrementa i e i₁ 8. else X[i]=A[i₂]

9. incrementa i e i₂

10. if (i₁<f₁) then copia A[i₁;f₁] alla fine di X

fonde A[i₁;f₁] e A[f₁+1;f₂] output in A[i₁;f₂]

Osservazione: usa l’array ausiliario X

Algoritmo di fusione di sequenze ordinate

Lemma

La procedure Merge fonde due sequenze ordinate di lunghezza n₁ e n₂ eseguendo al più n₁+ n₂ -1 confronti Dim: Ogni confronto “consuma” un elemento di A.

Nel caso peggiore tutti gli elementi tranne l’ultimo sono aggiunti alla sequenza X tramite un confronto.

Il numero totale di elementi è n₁+ n₂. Quindi il numero totale

di confronti è n₁+ n₂ -1. QED

Numero di confronti: C(n=n₁+ n₂)=O(n₁+ n₂)=O(n) (si noti che vale anche C(n)=Ω(min{n₁,n₂}))

Numero di operazioni (confronti + copie)? T(n)=(n₁+ n₂)

Costo dell’algoritmo di merge

MergeSort (A, i, f)

1. if (i  f) then return 2. m = (i+f)/2

3. MergeSort(A,i,m) 4. MergeSort(A,m+1,f) 5. Merge(A,i,m,f)

MergeSort

Complessità del MergeSort

Si vede facilmente che il tempo di esecuzione di MergeSort è:

T(n) = 2 T(n/2) + Θ(n) con T(1)=1, da cui:

T(n)=2(2T(n/2

)+Θ(n/2))+Θ(n)=

=2(2(2T(n/2

)+Θ(n/2

))+Θ(n/2))+Θ(n)=…

e per k = log

n si ha n/2

 = 1 e quindi

T(n)=2(2(…(2T(n/2^k)+Θ(1))+…+Θ(n/2²))+Θ(n/2))+Θ(n)

= 2^{log n}·Θ(1)+2^{log n-1}·Θ(2)+2^{log n-2}·Θ(2²)+…+ 2⁰·Θ(n)

= n∙Θ(1)+n/2∙Θ(2)+n/4∙Θ(4)+…+1∙Θ(n) = Θ(n log n)

Più precisamente…

1. Nel caso peggiore, il MS esegue (n log n - ⌈ ⌉ 2

+ 1) confronti, che corrisponde ad un numero compreso tra (n log n - n + 1) e

(n log n + n + O(log n))

2. Nel caso medio, il MS esegue (n log n - ⌈ ⌉ 2

+ 1) – 0.2645·n confronti

3. Nel caso migliore (array già ordinato), il MS

esegue n-1 confronti

Osservazioni finali

• Il MergeSort è un algoritmo (asintoticamente) ottimo rispetto al numero di confronti eseguiti nel caso peggiore

• Il MergeSort non ordina in loco, e utilizza memoria ausiliaria (l’occupazione di

memoria finale è pari a 2n)