Algoritmi e Strutture Dati
Capitolo 12: Divide-et-impera
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Tecniche
Divide-et-impera
✦
Un problema viene suddiviso in sotto-problemi indipendenti, che vengono risolti
ricorsivamente (top-down)
✦
Ambito: problemi di decisione, ricerca
✦
Programmazione dinamica
✦
La soluzione viene costruita (bottom-up) a partire
da un insieme di sotto-problemi potenzialmente ripetuti
✦
Ambito: problemi di ottimizzazione
✦
Memoization (o annotazione)
✦
Versione top-down della programmazione dinamica
✦
© Alberto Montresor
2
Tecniche
Tecnica greedy
✦
Approccio “ingordo”: si fa sempre la scelta localmente ottima
✦
Backtrack
✦
Procediamo per “tentativi”, tornando ogni tanto sui nostri passi
✦
Ricerca locale
✦
La soluzione ottima viene trovata “migliorando” via via soluzioni esistenti
✦
Algoritmi probablistici
✦
Meglio scegliere con giudizio (ma in maniera costosa) o
scegliere a caso (“gratuitamente”)
✦
© Alberto Montresor
3
Divide-et-impera
Tre fasi:
✦
Divide: Dividi il problema in sotto-problemi più piccoli e indipendenti
✦
Impera: Risolvi i sotto-problemi ricorsivamente
✦
Combina: “unisci” le soluzioni dei sottoproblemi
✦
Non esiste una ricetta “unica” per divide-et-impera:
✦
Quick Sort: “divide” complesso, niente fase di “combina”
✦
Merge Sort: “divide” banale, “combina” complesso
✦
E' necessario uno sforzo creativo
✦
© Alberto Montresor
4
Le torri di Hanoi
Gioco matematico
✦
tre pioli
✦
n dischi di dimensioni diverse
✦
Inizialmente, tutti i dischi sono impilati in ordine decrescente
(più piccolo in alto) nel piolo di sinistra
✦
Scopo del gioco
✦
Impilare in ordine decrescente i dischi sul piolo di destra
✦
Senza mai impilare un disco più grande su uno più piccolo
✦
Muovendo al massimo un disco alla volta
✦
Utilizzando il piolo centrale come appoggio
✦
© Alberto Montresor
5
Le torri di Hanoi – Soluzione basata su divide-et-impera
Divide et impera:
✦
n-1 dischi da origine a intermedio
✦
1 disco da origine a destinazione
✦
QuickTime™ and a
GIF decompressor
are needed to see this picture.
n-1 dischi da intermedio a destinazione
✦
© Alberto Montresor
6
Le torri di Hanoi – Soluzione basata su divide-et-impera
Costo computazionale:
✦
T(n) = 2T(n-1)+1
✦
Domanda: Come risolvere questa ricorrenza?
✦
Nota: La soluzione è ottima (si può dimostrare)
✦
© Alberto Montresor
7
Quick Sort
Algoritmo di ordinamento
✦
Basato su divide-et-impera
✦
Caso medio: O(n log n), caso pessimo O(n2)
✦
Caso medio vs caso pessimo
✦
Il fattore costante di Quick Sort è migliore di Merge Sort
✦
E' possibile utilizzare tecniche “euristiche” per evitare il caso pessimo
✦
Quindi spesso è preferito ad altri algoritmi
✦
Ulteriori dettagli
✦
R. Sedgewick, “Implementing Quicksort Programs”
Communications of the ACM, 21(10):847-857, 1978
http://portal.acm.org/citation.cfm?id=359631
✦
© Alberto Montresor
8
Quick Sort
Input: Array A[1..n], indici primo,ultimo tali che 1 ≤ primo ≤ ultimo ≤ n
✦
Divide-et-impera
✦
Divide: partiziona l'array A[primo..ultimo] in due sottovettori A[primo..j-1] e
A[j+1..ultimo] (eventualmente vuoti) in modo che:
✦
A[j] prende il nome di perno
✦
Impera: ordina i due sottovettori A[primo..j-1] e A[j+1..ultimo] richiamando
ricorsivamente Quick Sort
✦
Combina: non fa nulla; i due sottovettori ordinati e l'elemento A[j] sono già ordinati
✦
© Alberto Montresor
9
Quick Sort: Codice
© Alberto Montresor
10
Quick Sort: Esempio di funzionamento Perno
i
20 14 28 29 15 27 12 30 21 25 13
A[i] ≥ x
j
i
20 14 28 29 15 27 12 30 21 25 13
A[i] < x:
j ← j+1, A[i] ↔A[j]
j
i
20 14 28 29 15 27 12 30 21 25 13
A[i] ≥ x
j
i
20 14 28 29 15 27 12 30 21 25 13
A[i] ≥ x
j
i
20 14 28 29 15 27 12 30 21 25 13
A[i] < x:
j
i
20 14 15 29 28 27 12 30 21 25 13
j
© Alberto Montresor
A[i] ≥ x
j ← j+1, A[i] ↔A[j]
Quick Sort: Esempio di funzionamento Perno
i
20 14 15 29 28 27 12 30 21 25 13
A[i] < x:
j ← j+1, A[i] ↔A[j]
j
i
20 14 15 12 28 27 29 30 21 25 13
A[i] ≥ x
j
i
20 14 15 12 28 27 29 30 21 25 13
A[i] ≥ x
j
i
20 14 15 12 28 27 29 30 21 25 13
A[i] ≥ x
j
i
20 14 15 12 28 27 29 30 21 25 13
j
13
j ← j+1, A[i] ↔A[j]
A[primo] ← A[j]; A[j] ← x
14 15 12 20 27 29 30 21 25 28
j
© Alberto Montresor
A[i] < x:
Quick Sort: Esempio di ricorsione
20 14 28 34 15 27 12 30 21 25 13
13 14 15 12 20 27 29 30 21 25 28
© Alberto Montresor
12 13 15 14
25 21 27 29 30 28
12
14 15
21 25
28 29 30
14
21
28
30
13
Quick Sort: Esempio di ricorsione
20 14 28 34 15 27 12 30 21 25 13
13 14 15 12
27 29 30 21 25 28
12
15 14
25 21
29 30 28
14
21
28
12 13 14 15
© Alberto Montresor
30
20 21 25 27 28 29 30
14
Quick Sort: Invariante di ciclo per perno()
All'inizio di ogni iterazione,
✦
(1) primo < k ≤ j, allora A[k] ≤ x
j
(2) j < k < i, allora A[k] > x
(3) k=primo, allora A[k] = x
<x
i
≥x
Inizializzazione
✦
Primo ciclo: i=j=primo. I due range sono vuoti, quindi 1. e 2. sono rispettati.
A[primo] = x dall'assegnazione
✦
Conclusione
✦
i=ultimo+1. Questo significa che tutti gli elementi sono stati divisi in tre partizioni:
x, < di x, ≥ di x
✦
Con lo scambio fra A[j] e A[primo], si ottiene la proprietà desiderata
✦
© Alberto Montresor
15
Quick Sort: Invariante di ciclo per perno()
Conservazione
✦
La proprietà (3) non viene mai toccata
✦
Assumiamo sia vero all'inizio del ciclo i
✦
Caso 1: A[i] ≥ x
✦
j non viene modificato, i viene incrementato di 1.
✦
Le proprietà (1) e (3) restano valide
✦
Poiché A[i] ≥ x, la proprietà (2) è vera anche per il ciclo i+1
✦
Caso 2: A[i] < x
✦
j viene incrementato di 1
✦
Viene effettuato lo swap fra A[i] e A[j] → A'[i] = A[j], A'[j] = A[i]
✦
Quindi A[j] < x, quindi la proprietà (1) è valida per i+1
✦
Se i=j, l'insieme 2. è vuoto e resta tale.
✦
Se j<i, A'[i] ≥ x, quindi (2) è valida per i+1
✦
© Alberto Montresor
16
Quick Sort: Complessità computazionale
Costo di perno(): θ(ultimo-primo) = θ(n)
✦
Costo Quick Sort: Dipende dal partizionamento
✦
Partizionamento peggiore
✦
Dato un problema di dimensione n, viene sempre diviso in due sottoproblemi di
dimensione 0 e n-1
✦
T(n) = T(n-1)+T(0)+θ(n) = T(n-1) + θ(n) = θ(n2)
✦
Domanda
✦
Quando si verifica il caso pessimo?
✦
Partizionamento migliore
✦
Data un problema di dimensione n, viene sempre diviso in due sottoproblemi di
dimensione n/2
✦
T(n) = 2T(n/2)+θ(n) = θ(n log n)
✦
© Alberto Montresor
17
Quick Sort: Complessità computazionale
Partizionamenti parzialmente bilanciati
✦
Il partizionamento nel caso medio di Quick Sort è molto più vicino al caso ottimo
che al caso peggiore
✦
Esempio:
✦
partizionamento 9-a-1: T(n) = T(n/10)+T(9n/10)+cn
✦
Costruiamo l'albero di ricorsione, alto log10/9 n = θ(log n)
✦
partizionamento 99-a-1:
✦
T(n) = T(n/100)+T(99n/100)+cn
Costruiamo l'albero di ricorsione, alto log100/99 n = θ(log n)
✦
Note:
✦
In questi esempi, il partizionamento ha proporzionalità limitata
✦
I fattori moltiplicativi possono essere importanti
✦
© Alberto Montresor
18
Quick Sort: Complessità computazionale


Caso medio:

Il costo dipende dall'ordine degli elementi, non dai loro valori

Dobbiamo considerare tutte le possibili permutazioni

Difficile dal punto di vista analitico
Caso medio: un'intuizione:

Alcuni partizionamenti saranno parzialmente bilanciati

Altri saranno pessimi

In media, questi si alterneranno nella sequenza di partizionamenti

I partizionamenti parzialmente bilanciati “dominano” quelli pessimi
© Alberto Montresor
19
Inneffective sorts
© Alberto Montresor
20
Moltiplicazione di matrici
Moltiplicazione matrici
✦
C=AB
✦
=
A:7x3
© Alberto Montresor
B:3x5

Complessità

T(p,c,q) = p·c·q

T(n) = θ(n3)
C:7x5
21
Come migliorare il prodotto fra matrici
Suddividiamo le matrici n·n in quattro matrici n/2·n/2
✦
Calcolo matrice:
✦
Equazione di ricorrenza:
✦
© Alberto Montresor
22
Come migliorare il prodotto fra matrici
Calcoliamo alcuni termini intermedi
✦
Matrice finale
✦
Equazione ricorrenza
✦
© Alberto Montresor
23
Alcune informazioni storiche
Algoritmo di Strassen (1969):
✦
θ(n2.81)
✦
Il primo ad “scoprire” che era possibile moltiplicare due matrici in meno di n3
moltiplicazioni scalari
✦
Coppersmith and Winograd (1990):
✦
O(n2.38)
✦
Attuale algoritmo migliore
✦
100003 = 1.00 · 1012
100002.81 = 1.74 · 1011
100002.38 = 3.31 · 109
Limite inferiore
✦
Ω(n2)
✦
© Alberto Montresor
24
Metodo divide-et-impera
Quando applicare divide-et-impera
✦
I passi “divide” e “combina” devono essere semplici
✦
Ovviamente, i costi devono essere migliori del corrispondente algoritmo iterativo
✦
Esempio ok: sorting
✦
Esempio non ok: ricerca del minimo
✦
Ulteriori vantaggi
✦
Facile parallelizzazione
✦
“cache oblivious”
✦
utilizzo ottimale della cache
✦
© Alberto Montresor
25