Algoritmi e Calcolo Parallelo 2012/2013 - Tecniche di Analisi
-
Upload
pier-luca-lanzi -
Category
Education
-
view
176 -
download
1
description
Transcript of Algoritmi e Calcolo Parallelo 2012/2013 - Tecniche di Analisi
Prof. Pier Luca Lanzi
Tecniche di AnalisiAlgoritmi e Calcolo Parallelo
Prof. Pier Luca Lanzi
Riferimenti
• Bertossi Alan A., Montresor Alberto. “Algoritmi e strutture di dati” (seconda edizione), CittàStudi 2010
• Stanley B. Lippman, Barbara E. Moo, Josee Lajoie“C++ Primer”, 5th Edition Addison-Wesley
2
Prof. Pier Luca Lanzi
Le maggiori difficoltà nell’analisi dellacomplessità si incontra nell’…
Analisi degli algoritmi ricorsivi
Analisi del caso medio
Analisi “ammortizzata” di una sequenza di operazioni
Prof. Pier Luca Lanzi
Espandere fino a derivare una formula chiusa
(merge sort)
Usare relazioni di ricorrenza “comuni”(divide et impera/master theorem)
“tentare” una soluzione
Prof. Pier Luca Lanzi
Divide et Impera
(Divide) Dividere il problema insottoproblemi più semplici
(Impera) Risolvere i sottoproblemiseparatamente (ricorsivamente)
Ricombinare i sottoproblemi nella soluzione
Prof. Pier Luca Lanzi
costo suddivisionee ricombinazione
grandezza dei sottoproblemi
# sottoproblemi
• Divide: divide il vettore di lunghezza n in due sottovettori di n/2 elementi
• Impera: Ordina ricorsivamente i due sottovettori
• Ricombina: le soluzioni dei sottoproblemi in tempo lineare
T(n) = 2T(n/2) + cn
• Come calcoliamo T(n)? SostituzioneMaster method
Algoritmo di Merge Sort 6
Prof. Pier Luca Lanzi
7Analisi di Algoritmi Ricorsivi: Master Method
• T(n) = aT(n/b) + f(n)dove a≥1, b>1, ed f è asintoticamente positiva
• Caso 1: f (n) = O(nlogba – ε) per una costante ε > 0Soluzione: T(n) = Θ(nlogba)
• Caso 2: f (n) = Θ(nlogba lgkn) per una costante k≥0Soluzione: T(n) = Q(nlogba lgk+1n)
• Caso 3: f (n) = Ω(nlogba+ε) per una costante ε>0 f(n) soddisfa af (n/b)≤cf(n) per una costante c <
1Soluzione: T(n) = Θ(f(n))
Prof. Pier Luca Lanzi
Ricorrenze Lineari con Partizione Bilanciata
• Si applica a forme ricorsive del tipo,
T(n) = d, se n=1T(n) = aT(n/b) + cnβ
dove a≥1, b>1
• Posto α = log a/log b1.T(n) = Θ(nα) se α>β2.T(n) = Θ(nαlogn) se α=β3.T(n) = Θ(nβ) se α<β
8
Prof. Pier Luca Lanzi
costo suddivisionee ricombinazione
grandezza dei sottoproblemi
# sottoproblemi
• Divide: confronta l’elemento centrale
• Impera: ricerca l’elemento in uno dei due sottovettori
• Non c’è ricombinazione
T(n) =1T(n/2) + c
• Per calcolare T(n), nlogb
a = nlog2
1 = n0 = 1, ovvero, il secondo caso con k=0, e quindi T(n) = Θ(lg n)
Esempio: Ricerca Binaria 9
Prof. Pier Luca Lanzi
Calcolo di an
• Calcolare an con n naturale
• L’algoritmo tipico è Θ(n), possiamo fare di meglio?
• Approccio Divide-et-Impera
• T(n) = T(n/2) + Θ(1) T(n) = Θ(lg n)
10
a n =a n/2 × a n/2 se n è pari
a (n–1)/2 × a (n–1)/2 × a se n è dispari
Prof. Pier Luca Lanzi
Moltiplicazione fra Matrici
nnnn
n
n
nnnn
n
n
nnnn
n
n
bbb
bbb
bbb
aaa
aaa
aaa
ccc
ccc
ccc
21
22221
11211
21
22221
11211
21
22221
11211
n
kkjikij bac
1
Input: A = [aij], B = [bij].Output: C = [cij] = A× B.
i, j = 1, 2,… , n.
11
Prof. Pier Luca Lanzi
Algoritmo Standard
for i 1 to ndo for j 1 to n
do cij 0for k 1 to n
do cij cij + aik× bkj
Complessità Θ(n3)
12
Prof. Pier Luca Lanzi
Algoritmo Divide-et-Impera
C = A × B
8 moltiplicazioni (n/2)´(n/2)4 somme (n/2)´(n/2)
matrice nxn = 2x2 matrice di (n/2)x(n/2) sottomatrici
C11 = A11 B11 +A12 B21
C12 = A11 B12 +A12 B22
C21 = A21 B11 +A22 B21
C22 = A21 B21 +A21 B22
13
Prof. Pier Luca Lanzi
Somme su matricin/2xn/2
Su matrici n/2
# moltiplicazioni
Algoritmo Divide-et-Impera 14
T(n) =8T(n/2) + Θ(n2)
nlogba = nlog28 = n3 Primo caso T(n) = Θ(n3)
Nessun miglioramento!
Prof. Pier Luca Lanzi
Moltiplicazione fra Matrici:Metodo di Strassen
• Divide: suddivide A and B in sottomatrici di dimensione (n/2)x(n/2) utilizzati per creare i termini che devono essere moltiplicati usando + e –
• Impera: esegue 7 moltiplicazioni di sottomatrici (n/2)x(n/2)
• Ricombina: crea C usando somme e sottrazioni di sottomatrici (n/2)x(n/2)
T(n) = 7 T(n/2) + Q(n2)
15
nlogba = nlog27 » n2.81 T(n) = Θ(nlg7)
2.81 sembra poco ma appare all’esponente!
Il miglioreè Q(n2.37…)
Prof. Pier Luca Lanzi
DomandaSarebbe possibile parallelizzare la
moltiplicazione fra matrici?
Prof. Pier Luca Lanzi
Analisi Ammortizzata
• Si considera il tempo richiesto per eseguire, nel caso pessimo, un'intera sequenza di operazioni
• In una sequenza di operazioni, ci sono operazioni costose e meno costose
• Se le operazioni più costose sono poco frequenti, allora il loro costo può essere ammortizzato dalle operazioni meno costose
• Importante differenzaAnalisi del caso medio: basata su probabilità, su
singola operazioneAnalisi ammortizzata: deterministica, su
operazioni multiple, caso pessimo
17
Prof. Pier Luca Lanzi
Tecniche per l’Analisi Ammortizzata
• Metodo dell'aggregazione Si calcola la complessità O(f(n)) per eseguire n operazioni
in sequenza nel caso pessimo Il costo ammortizzato di una singola operazione è
O(f(n)/n)
• Metodo degli accantonamenti (o del contabile) Alle operazioni vengono assegnati costi ammortizzati che
possono essere maggiori/minori del loro costo effettivo Provare che la somma dei costi ammortizzati è un
limite superiore al costo effettivo
• Metodo del potenziale (derivata dalla fisica) Lo stato del sistema viene descritto tramite differenze di
potenziale
18
Prof. Pier Luca Lanzi
Esempio: Contatore Binario (1)
• Implementiamo un contatore binario di k bit con un array di bit
• Un numero binario x registrato in A ha il bit meno significativo in A[0] e il più significativo in A[k-1] per cui:
• Supponiamo che A venga usato per contare a partire da x=0 usando l’operazione di incremento
19
Prof. Pier Luca Lanzi
Esempio: Contatore Binario (2) 20
8 0 0 0 0 1 0 0 0 15
9 0 0 0 0 1 0 0 1 16
10 0 0 0 0 1 0 1 0 18
14 0 0 0 0 1 1 1 0 25
13 0 0 0 0 1 1 0 1 23
11 0 0 0 0 1 0 1 1 19
12 0 0 0 0 1 1 0 0 22
15 0 0 0 0 1 1 1 1 26
16 0 0 0 1 0 0 0 0 31
x A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] costo
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 1
2 0 0 0 0 0 0 1 0 3
3 0 0 0 0 0 0 1 1 4
4 0 0 0 0 0 1 0 0 7
5 0 0 0 0 0 1 0 1 8
6 0 0 0 0 0 1 1 0 10
7 0 0 0 0 0 1 1 1 11
Prof. Pier Luca Lanzi
Esempio: Contatore Binario (3)
• Analisi “grossolana”Una singola operazione di incremento richiede
tempo O(k) nel caso pessimo Limite superiore O(nk) per una sequenza di n
incrementi
• Analisi più accurataOsserviamo che il tempo necessario ad eseguire
l’intera sequenza è proporzionale al numero di bit che vengono modificati
Quanti bit vengono modificati?
21
Prof. Pier Luca Lanzi
Esempio: Contatore Binario (4) 22
8 0 0 0 0 1 0 0 0 15
9 0 0 0 0 1 0 0 1 16
10 0 0 0 0 1 0 1 0 18
14 0 0 0 0 1 1 1 0 25
13 0 0 0 0 1 1 0 1 23
11 0 0 0 0 1 0 1 1 19
12 0 0 0 0 1 1 0 0 22
15 0 0 0 0 1 1 1 1 26
16 0 0 0 1 0 0 0 0 31
x A[7] A[6] A[5] A[4] A[3] A[2] A[1] A[0] costo
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 1
2 0 0 0 0 0 0 1 0 3
3 0 0 0 0 0 0 1 1 4
4 0 0 0 0 0 1 0 0 7
5 0 0 0 0 0 1 0 1 8
6 0 0 0 0 0 1 1 0 10
7 0 0 0 0 0 1 1 1 11
Prof. Pier Luca Lanzi
Metodo dell’Aggregazione
• Dalla simulazione si vede che:A[0] viene modificato ad ogni incremento del
contatore,A[1] viene modificato ogni 2 incrementi,A[2] viene modificato ogni 4 incrementi....
• In generale, A[i] viene modificato ogni 2i incrementi
• Il costo aggregato è
• Il costo ammortizzato: 2n/n = 2 = O(1)
23
Prof. Pier Luca Lanzi
Metodo degli Accantonamenti (o del contabile)
• Si assegna un costo ammortizzato ai distinto* ad ognuna delle operazioni possibili che può essere diverso dal costo effettivo ci
• Le operazioni meno costose vengono caricate di un costo aggiuntivo detto credito
costo ammortizzato = costo effettivo + credito prodotto
• I crediti accumulati saranno usati per pagare le operazioni più costose
costo ammortizzato = costo effettivo – credito consumato
• (*) Nell'aggregazione, abbiamo calcolato costo ammortizzato costante
24
Prof. Pier Luca Lanzi
Metodo degli Accantonamenti (o del contabile)
• Lo scopo è dimostrare che la somma dei costi ammortizzati ai è un limite superiore ai costi effettivi ci:
dimostrare che il valore così ottenuto è “poco costoso”
• Alcuni punti da ricordare La dimostrazione deve essere valida per tutte le sequenze
di input (caso pessimo)
Il credito è espresso dalla seguente formula e quindi è positivo
25
Prof. Pier Luca Lanzi
Contatore Binario con il Metodo degli Accantonamenti
• Il costo effettivo dell'operazione di incremento è d (dove d è il numero di bit che cambiano valore)
• Poniamo il costo ammortizzato dell'operazione di incremento pari a 2 1 per cambio del bit da 0 a 1 (costo effettivo) 1 per il futuro cambio dello stesso bit da 1 a 0
• Ne segue che In ogni istante, il credito è pari al numero di bit 1
attualmente presenti Costo totale ammortizzato: O(n)
26
Prof. Pier Luca Lanzi
Metodo del Potenziale
• Una funzione potenziale Φ associa a ogni configurazione un numero reale Φi
• Φi è il valore della funzione potenziale dopo che è stata eseguita l’operazione i
• Il costo ammortizzato ai è calcolato come il costo effettivo ci più l’incremento di potenziale, ovvero
ai = ci + Φi – Φi-1
• Il costo ammortizzato della sequenza di n operazioni diventa
Σ ai = Σ ci + Φn – Φ0
• Nel caso del contatore Φi è il numero di bit a uno nella sequenza
27
Prof. Pier Luca Lanzi
Contatore Binario con il Metodo dei Potenziali
• Scegliamo come funzione potenziale Φ(A) il numero bit 1 presenti nel contatore.
• All'inizio, zero bit accesi, quindi Φ(A0) = 0
• Alla fine, Φ(An) ≥ 0 e quindi la differenza di potenziale è non negativa, quindi il costo ammortizzato è un
28
operazione costo differenza di costo effettivo potenziale ammortizzato
add 1+t -t+1 2
Prof. Pier Luca Lanzi
Problema 1
• Si consideri la seguente modifica dell’algoritmo di mergesort che prende come input un array A e gli indici l and r e restituisce come output il vettore A in cui gli elementi da l a r sono ordinati.
slowMergeSort(A, l, r)if (l < r)
int mid = (l + r)/2;slowMergeSort(A, l, mid)slowMergeSort(A, l, mid) //! Riapplica il sortslowMergeSort(A, mid + 1, r)merge(A, l, mid, r)
• Si calcoli la complessità dell’algoritmo slowMergeSort.
29
Prof. Pier Luca Lanzi
Problema 2
• Si consideri la relazione di ricorrenza
T(n) =1 per n=1T(n)<=2T(n/2)+n per n=2h, h>0
Si dimostri per induzione che T(n)<=cn per qualche costante c
30
Prof. Pier Luca Lanzi
Problema 3
• L’algoritmo di insertion sort può essere espresso coma una procedura ricorsiva in questo modo. Per ordinare un vettore A di n elementi (A[1..n]), prima ordiniamo il vettore corrispondente ai primi n-1 elementi (A[1..n-1]) e poi inseriamo l’elemento A[n] nel vettore ordinato A[1..n-1]. Scrivere una versione ricorsiva della funzione C++ per l’insertion sort vista a lezione. Scrivere l’equazione ricorrente per il tempo di ordinamento e calcolarne la complessità.
31
Prof. Pier Luca Lanzi
Problema 4
• Scrivere un programma C++ che legge da tastiera una sequenza di n numeri interi con valori da 0 a k (compreso) e poi può calcolare in un tempo O(1) quanti elementi sono compresi in un intervallo [a,b] specificato dall’utente. La complessità dell’algoritmo deve essere Θ(n+k).
32
Prof. Pier Luca Lanzi
Problema 5
• Data una sequenza di n elementi da ordinare, sappiamo che la sequenza consiste di n/k sottosequenze, ognuna delle quali contiene k elementi. Gli elementi di una sottosequenza sono più piccoli degli elementi nella sottosequenza successiva e più grandi che gli elementi della sequenza precedente. Quindi per ordinare tutta la sequenza di n elementi è sufficiente ordinare le n/k sottosequenze di k elementi. Mostrare che il numero di comparazioni necessarie per risolvere questo problema è limitato da Ω(n lg k).
33
Prof. Pier Luca Lanzi
Problema 6
• Moltiplicazione Numeri Complessi (a+bi)(c+di) = [ac – bd] + [ad + bc]i Input: a, b, c, dOutput: ac-bd, ad+bc
• Modello di calcoloCosto moltiplicazione: 1, costo
addizione/sottrazione: 0.01
• Domande Quanto costa l'algoritmo “banale” dettato dalla
definizione?Si può fare di meglio? (Soluzione di Gauss)Qual è il ruolo del modello di calcolo?
34
Prof. Pier Luca Lanzi
Problema 7: Somma di Numeri Binari
• Algoritmo elementare della sommaRichiede di esaminare tutti gli n bitCosto totale cn (c e’ il costo per sommare tre bit
e generare riporto)
• Domanda: Esiste un metodo più efficiente?
35
* * * * * * * * * * * * * * ** * * * * * * * * * * * * * *
+* * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
Prof. Pier Luca Lanzi
Problema 8: Prodotto di Numeri Binari
• Algoritmo elementare
36
* * * * * * * * * * * * * *
* * * * * * ** * * * * * *
* * * * * * ** * * * * * ** * * * * * *
* * * * * * * * * * * * * *
x
n2
Prof. Pier Luca Lanzi
Prodotto di Numeri Binari
• Confronto fra i costi di esecuzione
Somma: Tsum(n) = c1n
Prodotto: Tprod(n) = c2n2 + c3n
• Si potrebbe erroneamente concludere che il problema della moltiplicazione è inerentemente più costoso del problema dell'addizione (la nostra esperienza lo “conferma”)
• Per provare che il problema del prodotto è più costoso del problema della somma, dobbiamo provare che non esiste una soluzione in tempo lineare per il prodotto
37
Prof. Pier Luca Lanzi
Prodotto di Numeri Binari: Dividi et Impera
• Divide: dividi il problema in sottoproblemi di dimensioni inferiori
• Impera: risolvi i sottoproblemi in maniera ricorsiva
• Combina: unisci le soluzioni dei sottoproblemi in modo da ottenere la risposta del problema principale
• Moltiplicazione ricorsiva X = a2n/2 + b Y = c2n/2 + d XY = ac2n + (ad+bc)2n/2 + bd
• Nota: Moltiplicare per 2t equivale a uno shift di t posizioni, in
tempo lineare Sommare due vettori di bit anch’esso in tempo lineare
• Complessità
38
a b
c d
Prof. Pier Luca Lanzi
Prodotto di Numeri Binari: Gaussified-product (Karatsuba 1962)• Definendo
A1 = ac
A3 = bd
m = (a+b)(c+d)=ac+ad+bc+bd
A2 = m−A1−A3=ad+bc
• Si ottiene,
XY = A12n+A22n/2 + A3
• Che ha una complessità pari a,
39
Tstandard(106) =1012
Tkaratsuba(106) = 3x109