1 - Università di Camerino

Algoritmi e Strutture Dati
Università di Camerino
Corso di Laurea in Informatica
(12 CFU)
I periodo didattico
Emanuela Merelli
email:[email protected]
Lezione 3
Tecniche di Progettazione
Argomento: Divide et Impera
Obiettivo conoscitivo:
Tecniche
Algoritmiche:
Divide et Impera
Tecniche di progettazione di
algoritmi
• Approccio Incrementale
– Insertion sort: Se è ordinato A[1..j-1] si inserisce A[j] ...
• Approccio Divide et impera
– Merge sort: divido il problema in n sottoproblemi e
opero ricorsivamente sugli n problemi
• Programmazione Dinamica
–…
Divide-et-impera
Un algoritmo si dice ricorsivo se al suo interno (tra i
suoi comandi) sono presenti chiamate a se stesso
per gestire sottoproblemi analoghi a quello dato
L’approccio seguito dagli algoritmi ricorsivi è quello di
suddividere il problema dato in sottoproblemi simile a
quello di partenza ma di dimensione inferiore
Quindi, una volta che i sottoproblemi sono stati risolti
ricorsivamente, combinare le soluzioni trovate per
creare la soluzione al problema dato
Divide
Impera
Combina
Divide et Impera
• Divide et impera:
– Divide: Se l’istanza del problema da risolvere è troppo
“complicata” per essere risolta direttamente, dividila in due o più
“parti”
– Risolvi ricorsivamente: Usa la stessa tecnica divide et impera
per risolvere le singole parti (sottoproblemi)
– Combina: Combina le soluzioni trovate per i sottoproblemi in
una soluzione per il problema originario.
MergeSort: Algoritmo
Dividi: se S contiene almeno due elementi (un solo
elemento è banalmente già ordinato), rimuovi tutti gli
elementi da S e inseriscili in due vettori, S1 e S2, ognuno
dei quali contiene circa la metà degli elementi di S. (S1
contiene i primi n/2 elementi e S2 contiene i rimanenti n/2
elementi).
Risolvi ricorsivamente: ordina gli elementi in S1 e S2
usando MergeSort (ricorsione).
Combina: fondi gli elementi di S1 e S2 ottenendo un unico
vettore S ordinato (merge)
Mergesort: esempio 2
24
10
21
36
24
10
36
87
39
83
58
21
39
83
58
87
24
10
24
36
36
10
87
83
21
39
21
58
39
83
58
24
36
10
87
24
36
Merge Sort: Algoritmo
Merge-sort(A,p,r)
if p < r then
q= └(p+r)/2┘
Merge-sort(A,p,q)
Merge-sort(A,q+1,r)
Merge(A,p,q,r)
Merge(A,p,q,r)
Rimuovi il più piccolo dei due elementi
affioranti in A[p..q] e A[q+1..r] e inseriscilo
nel vettore in costruzione.
Continua fino a che i due vettori sono svuotati.
Copia il risultato in A[p..r].
Esempio 1
A = <5,2,4,6,1,3,2,6>
12234566
fusione
2456
1236
fusione
25
fusione
5
2
4
fusione
46
13
fusione
fusione
6
1
26
fusione
3
Sequenza iniziale
2
6
Merge
1
12
27
36
38
47
54
1
23
25
32
68
96
12 23
… e così via
Ricorrenze
Quando un algoritmo contiene una chiamata ricorsiva a se stesso, il
suo tempo di esecuzione può spesso essere descritto da una
equazione di ricorrenza o ricorrenza.
Una ricorrenza è una equazione o una disequazione che descrive una
funzione in termini del suo valore su input sempre più piccoli.
Un'equazione ricorsiva esprime il valore di f(n) come combinazione di
f(n1),...,f(nk) dove ni < n, i=1..k.
Equazioni ricorsive
Indichiamo con T(n) il tempo di esecuzione di un problema di
dimensione n. E con (1) un tempo costante
Suddividiamo un problema in a sottoproblemi, ciascuno dei quali ha
una dimensione 1/b rispetto al problema principale e supponiamo di
impiegare un tempo D(n) per suddividere e un tempo C(n) per
combinare le soluzioni dei sottoproblemi. Si ottiene la seguente
ricorrenza:
(1)
se n < c
T(n) =
aT(n/b) + D(n) + C(n) se n > c
Esempio del Merge Sort
(1)
se n=1
2T(n/2) + (n)
se n > 1
T(n) =
Dove:
Divide in un tempo (1)
Impera in 2T(n/2)
Combina in (n)
Equazioni ricorsive:
un esempio semplice
1
se n = 1
T(n/2) + 1
se n > 1
T(n) =
Come si risolve ???
Metodo iterativo
T(n) =
T(n/2)
+ 1
T(n/4)
+1
+ 1
T(n/8)+1
+1
+ 1
.....................
T(n/n)+1
.........................
+ 1
1 + 1 .........................
+ 1
k
Ci fermiamo quando
2k=n
Dobbiamo valutare k
sappiamo che 2k = n, quindi
log2( 2k ) = log2(n), ovvero
k = log2(n)
Induzione
Dobbiamo dimostrare che una affermazione
è vera per ogni n≥0
Teorema.
se
1. affermazione(0) è vera.
2. affermazione(n-1) vera implica
affermazione(n) vera.
Allora affermazione(n) vera per ogni n ≥ 0
Dimostrazione per induzione:
esempio
n
affermazione(n) =
i
= n(n+1)/2
i=1
1
affermazione(1) =
i

i=1
= 1(1+1)/2 = 1
OK
affermazione(n-1) ----> affermazione(n):
n-1
i = (n-1)(n)/2 ---->
i=1

n
i

i=1
= n(n+1)/2
Dimostrazione per induzione:
esempio
n-1
i + n = (n-1)(n)/2 + n = n(n+1)/2
i =
i=1
i=1
n
...ma


L’uguaglianza tra questi due termini non è altro che affermazione(n-1)
e quindi la assumiamo vera per ipotesi induttiva.
Metodo di sostituzione
Primo passo:
Tentiamo di “indovinare” una possibile soluzione:
T(n) ≤ clog2(n)
Secondo passo:
la verifichiamo per induzione come segue:
Assumiamo che T(n’) ≤ clog2(n’) per n’ < n
e dimostriamo che T(n) ≤ clog2(n)
c è una costante (indipendente da n) che determineremo strada facendo…
T(n) = T(n/2) + 1

≤ clog2(n/2)
+ 1
= clog2(n) - clog2(2)
= clog2(n) - c + 1
se c ≥ 1 allora
≤
clog2(n)
Ipotesi induttiva !!!
+ 1
Equazioni ricorsive:
un esempio più complicato
(1)
se n = 1
2T(n/2) + (n)
se n > 1
T(n) =
Soluzione T(n) = (n log(n))
Albero di ricorsione
Cn + 2T(n/2)
C(n/2) + 2T(n/4)
C(n/4) + 2T(n/8)
……
(1)
(1)
C(n/2) + 2T(n/4)
C(n/4) + 2T(n/8)
……
……
C(n/4) + 2T(n/8)
……
…… …… ……
C(n/4) + 2T(n/8)
=cn
+
=cn
+
=cn
+
……
(1)
(1)
=cn
= n(log(n))
Il fattore log(n) deriva dal fatto che
l’albero ha un altezza log(n)
“Master Method o
Metodo dell’esperto”
•T(n) = aT(n/b) + f(n)
a  1, b > 1, f(n) > 0
Poniamo x = logba
f(n) = O(nx-) con >0
allora
T(n) = (nx)
f(n) = (nx)
allora
T(n) = (nx log(n))
f(n) = (nx+) con >0
af(n/b) ≤ cf(n) con c<1
per tutti gli n>n0
allora T(n) = (f(n))
… Merge sort T(n) = (n log(n))
Insertion sort
Merge sort
Worst case
(n2)
(n log(n))
Average case
(n2)
(n log(n))
(n)
(n log(n))
Best case
Perchè ordinare è importante
•... velocizza molto la ricerca !!!
Binary-search(A,x)
i=0
j=length(A)-1
while i<j do
k=(i+j)/2
if A[k]=x then return true
if A[k]>x then j=k-1
if A[k]<x then i=k+1
if A[i]=x then return true
else return false
Analisi di Binary search
•D(t)=j-i
al tempo t
•D(0) = n-1
•.........
•D(t+1) = D(t)/2
•Usciamo dal while quando D(t)<2
•... ... ovvero se t ≥ log2n.
•Quindi T(n) = (log2n)
Priority Queue (Code a Priorità)
•Dati: un insieme di elementi, ognuno dei quali ha
una chiave (un intero per esempio).
•Operazioni: inserimento, trova il massimo,
estrazione del massimo (massima chiave).
•Applicazioni delle PQ:
Job scheduling
Event-driven simulations
Implementazione (facile)
usando vettori
•Prima soluzione: vettore ordinato.
Ricerca massimo:
(1) operazioni
estrazione massimo:
(1) operazioni
inserimento:
(n) operazioni
•Seconda soluzione vettore non ordinato.
•
Ricerca massimo:
(n) operazioni
estrazione massimo:
(n) operazioni
inserimento:
(1) operazioni
•Si può fare meglio ???
Grafi e Alberi
•G=(V,E)
{1,3,4,1} è un ciclo
Un grafo senza cicli
è aciclico
V={1,2,3,4,5,6,7,8}
E={(1,2),(1,3),(1,4),(3,4),(6,7),(7,8)}
1
4
6
2
7
3
5
8
Un albero è un grafo aciclico con un numero di nodi
uguale al numero di archi più uno ( |E|=|V|-1 )
1
Albero
3
4
7
5
3
8
6
2
1
4
6
2
Foresta
5
7
8
Radice
r
h(a) altezza del nodo a:
h(x)=1
h(y)=h(q)=2
h(w)=3
x
y
q
w
Foglie
r è la radice
x è il padre di y
y è un figlio di x
x e q sono avi di w
w e q sono discendenti di x
q è fratello di y