1

2.

Analisi degli Algoritmi

2

Algoritmi e strutture dati - Definizioni Struttura dati: organizzazione sistematica dei

dati e del loro accesso Algoritmo: procedura suddivisa in passi che,

eseguiti in sequenza, consentono di eseguire un compito in tempo finito

Esempio: Max. di un vettore di n elementi

Algorithm arrayMax(A, n)currentMax = A[0];for (i=0; i < n; i++)

if (A[i] > currentMax)

currentMax = A[i];return currentMax;

3

Nel mondo reale.......

Gli algoritmi sono al cuore di innumerevoli applicazioni informatiche

Esempi Routing in Internet DBMS Analisi e classificazione di documenti/Motori

di ricerca Ottimizzazione di progetti Etc. Etc. Etc.

4

Esempio: Routing in Internet

Astrazione usando grafi:

I nodi rappresentano router

Gli archi descrivono i link fisici Costi sugli archi (link) : ritardo, livello di congestione

Obiettivo: determinare “buon” cammino sorg.-

dest.

Protocollo di Routing

A

ED

CB

F

2

2

13

1

1

2

53

5

Cammino “buono”: Di solito significa cammino a costo minimo

Possibili def. alternative

5

Esempio: Accesso a basi di dati

Obiettivo: rispondere rapidamente.

Interrogazione

Data RecordData base

.

.

.

Interrogazione

6

Qualità di algoritmi e strutture dati

Efficienza Tempo di esecuzione Spazio (quantità di memoria)

I due aspetti sono interdipendenti

8

Come misurare l’efficienza?

Perché B gira più velocemente ? Possiamo affermare che B sia “migliore” di A?

Programma A

Problema

Programma B

10 ms

1 ms

Dati

9

Misura dell’efficienza - obiettivi

Indipendenza dall’implementazione

Generale (valida per ogni input, di

qualsiasi dimensione)

Misura indipendente dalla

piattaforma Hw/Sw

10

Modello di costo RAMRandom Access Machine

Assegnazione

Op. aritmetiche

Test

Lettura/Scrittura

A = 10; (costo 1) A = B*C + D – 7; (costo 4) A == B (costo 1)

System.out.println(A); (Costo

1)

Macchina che esegue le istruzioni in sequenza.Insieme di operazioni primitive a costo unitario:

11

Modello di costo/2Costo di operazioni complesse:

Ciclo: somma costo test di fine ciclo e

costo corpo del ciclo

if…then…else: costo test più costo blocco

istruzioni che segue then o else (a

seconda del caso)

Attivazione di un metodo: somma dei costi

di tutte le istruzioni presenti nel

metodo

Costo: somma di tutti i costi

12

Esempio

Nel primo caso (vett. di 3 elementi) si ha costo 1 (ass.)+1 (ass. nel for) + 6 (test e incr. nel for) + 1 (test finale for) + 3 (test if) + 1 (istruz. return) = 13

Nel secondo caso si ha 1 (ass.) + 1 (ass. nel for) + 10 (test e incr. nel for) + 1 (test finale for) + 5 (test if) + 1 (istr. ass. nell’if) + 1 (istruz. return) = 20

AlgorithmarrayMax(A, n)currentMax=A[0]; for (i=0; i<n; i++)

if (A[i]>currentMax)

currentMax=A[i];return currentMax;

7

1

4

1

8

6

3

4

n=3 n=5

13

Perché il modello è accettabile?

A=A+B*C;MUL B,CADD A,B

AB

C

N finito (es. 32 o 64 )

Ogni istruzionecorrisponde a una sequenza finita di istruzioni macchina

Ogni variabile occupauna quantità finita dimemoria e quindi i tempi di accesso a duevariabili sono legati da una costante

14

Vantaggi e svantaggi

Vantaggi: prescinde dalla piattaforma Hw/Sw e dal linguaggio di programmazione

Svantaggi: l’indicazione che si ottiene è qualitativa

15

Quale input considerare? La misura deve dipendere dalla dimensione dell’input (n nel nostro esempio) ma non dal particolare input considerato

Possibile alternative:Analisi del caso peggiore: si considera il costo di esecuzione nel caso peggiore

Analisi del caso medio: si considera il costo medio dell’algoritmo rispetto ad una distribuzione dell’input (richiede la conoscenza della distribuzione)

In ogni caso occorre definire la dimensione dell’input

16

Dimensione dell’input

In generale: No. bit necessari a rappresentare l’input

Esempio (calcolo del Max. in un array di n interi)n interi finiti (< MAXINT)log(MAXINT) bit per rappresentare ogni valore.

Poiché MAXINT è una costante in pratica, il numero di bit necessari a rappresentare un intero è costante (es. 32)

Quindi: dimensione input è proporzionale a n

A volte le cose possono non essere così ovvie (si pensi al problema di indovinare un numero proposto nell’ultima slide)

17

AlgorithmarrayMax(A, n)currentMax=A[0]; for (i=0; i<n;

i++) if (A[i]>currentMax)

currentMax=A[i];return currentMax;

Analisi nel caso peggiore (esempio)

Nel caso peggiore l’array e’ ordinato in senso crescente

In questa ipotesi l’istruzione

currentMax=A[i]; è eseguita n-1 volte.

Il costo complessivo dell’algoritmo è allora 1(ass)+1(ass for)+2n(test ed increm for)+2(n-1)(test e ass. if)+1(test finale for) +1(return)=4n+3

1

4

6

3

8

18

Analisi asintotica

Se si considerano tutte le costanti l’analisi può divenire eccessivamente complessa

Interessa conoscere il costo al variare della dimensione dell’input, a meno di costanti

Motivo: il costo è comunque calcolato a meno di costanti, per le ipotesi fatte circa il modello

Un’analisi di questo tipo è detta asintotica

L’analisi asintotica è influenzata dall’operazione dominante di un algoritmo

19

Istruzione dominante Un’ operazione o istruzione si dice dominante se il numero d(n) di volte che essa è eseguita nel caso peggiore di input di dimensione n soddisfa:

f(n)<=a d(n) + b,dove f(n) è la complessità dell’algoritmo nel caso peggiore ed a e b sono costanti opportune

Es.: istruzione if (A[i]>currentMax) in AlgorithmarrayMax(A, n)

20

Analisi di Insertion SortAlgorithm insertionSort(A,

n)for (i=0; i<n; i++) {

tmp=A[i];for (j=i; j>0 &&

tmp<A[j-1]; j--)A[j]=A[j-1];

A[j] = tmp;}return A;

Inserisce l’elemento A[i] nella posizione corretta nel vettore ordinato A[0,…,i-1]

Ex: 5 4 3 2 1

i=0 5 4 3 2 1 0 confronti

i=1 4 5 3 2 1 1 confronto

i=2 3 4 5 2 1 2 confronti

i=3 2 3 4 5 1 3 confronti

i=4 1 2 3 4 5 4 confronti

Ex: 1 2 3 4 5 f(n)= n

€

f (n) = ii= 0

n−1

∑ =n(n −1) /2 =O(n2)

21

Esempiclass esercizio {

public void Ex1(int n) {int a, i;

for (i=0; i<n;i++)a=i;

}public void Ex2(int n) {int a, i;

for (i=0; i<n*n;i++)a=i;

}public void Ex3(int n) {int a, i, j;

for (i=0; i<n;i++) for (j=0; j<=i;j++)

a=i;}

}

Valutare la complessitàdei tre metodi

Complessità di Ex3: 1+2+....+n=O(n2)

23

Metodo Divide et Impera

Il problema è risolto ricorsivamente attraverso la sua scomposizione in problemi di taglia inferiore

Divide: Problema suddiviso in un numero di sottoproblemi di taglia inferioreImpera: Sottoproblemi risolti ricorsivamente o direttamente se di dimensione piccola a sufficienzaCombina: Le soluzioni dei sottoproblemi sono combinate per ottenere la soluzione al problema originale

24

Merge Sort A[0...n]

Si suppone n pari per semplicità

A[0...n/2-1] A[n/2...n-1]

Suddividi A in due sottovettori di dim. n/2

A[0...n/2-1] A[n/2...n-1]

MergeSort A[0...n/2-1] MergeSort A[n/2...n-1]

Merge

A ordinato

25

Merge Sort/2

void mergesort(int[] A, int first, int last){ if (first < last) { int mid = (first + last) / 2; mergesort(A, first, mid); mergesort(A, mid+1, last); merge(A, first, last); }}

26

Merge Sort A[0...n] /3

Divide: divide gli n elementi da ordinare in due sottosequenze da n/2 elementi. Costo: O(n)

Impera: ordina ricorsivamente usando il merge sort le due sottosequenze. Costo: 2f(n/2)

Combina: fonde le due sottosequenze ordinate. Costo: O(n)

La ricorsione termina quando si hanno solo due elementi da ordinare. Costo:O(1)

Costo dell’algoritmo Merge Sort: ⎩

⎨⎧

>+=

=2),()2/(2

2),1()(

nnnf

nnf

θ

θ

27

L’array [1 8 6 4 10 5 3 2 22]ordinatocon mergesort

28

Mergevoid merge(int[] data, int first, int last) {

int mid = (first + last) / 2; int i1 = 0, i2 = first, i3 = mid + 1; while (i2 <= mid && i3 <= last) if (data[i2] <data[i3]) temp[i1++] = data[i2++]; else temp[i1++] = data[i3++]; while (i2 <= mid) temp[i1++] = data[i2++]; while (i3 <= last) temp[i1++] = data[i3++]; for (i1 = 0, i2 = first;

i2 <= last; data[i2++] = temp[i1++]);

}

29

Equazioni di ricorrenza

Tempo di esecuzione di algoritmi ricorsivi descritti con equazioni di ricorrenza. Ex: MergeSort:

Semplificazioni: Argomenti non interi.

Condizioni al contorno: per n piccolo

⎩⎨⎧

≥+=

=2 ,)2/(2

1 ,)(

2

1

nncnf

ncnf

⎡ ⎤ ⎣ ⎦⎩⎨⎧

>++=

=2),()2/()2/(

2),1()(

nnnfnf

nnf

θ

θ

)1(θ

30

Soluzione di equazioni di ricorrenza Metodo per sostituzione. Si tenta una soluzione g(n) e si verifica se soddisfa l’equazione di ricorsione.

Dimostrazione per induzione.

Base dell’induzione: f(1)≤g(1)

Ipotesi induttiva: f(n/2) ≤g(n/2)

Passo induttivo: f(n) ≤g(n)

Per Merge Sort:

ancnng += log)(

31

Soluzione equazioni di ricorrenza per Merge Sort

Base: Ipotesi induttiva: Passo induttivo:

agcf =≤= )1()1( 1

)2/()2/( ngnf ≤

ancn

anccnncn

ancncn

ancnnc

ncngnf

+≤++−≤++≤

++≤+≤

log 2log 2)2/(log

2)2/(log)2/(2 )2/(2)(

2

2

2

2

ccc ≤+ 21

32

Esercizi/1

1. Mostrare che la soluzione di f(n)=f(n/2)+f(n/2)+1 è O(n)

2. Mostrare che la soluzione di f(n)=2f(n/2+10)+n è O(nlog n)

33

f(n)=f(n/2)+f(n/2)+1

Ipotesi: f(n)<=g(n)=cn

f(n/2)+f(n/2)+1<=cn/2 + cn/2 +1 = cn +1 NO!

Ipotesi: f(n)<=g(n)=cn-b

f(n/2)+f(n/2)+1<=cn/2-b + cn/2-b +1 = cn -2b+1

b>=1

34

f(n)=2f(n/2+10)+n

Rinominiamo n+20= m. Quindi: f(m)=2f(m/2)+m-20

Ipotesi: f(m)<=g(m)=cmlogm

f(m)<=2c (m/2) (log m-1)+m-20<=cm log m

se c>=1Quindi: f(n)<=g(n)=(n+20)log(n+20)

35

Esercizi/2

Mostrare che la soluzione di f(n)=f(n/2)+1 è O(log n)

36

Esercizi/3

Si consideri il problema della ricerca in un vettore di interi: dato il vettore A[1..n] ed un intero k, si vuole stabilire se k sia tra gli elementi di A o meno Considerato il classico

algoritmo basato sulla ricerca binaria, si mostri che esso ha complessità O(log n)

37

Esercizi/4

Si consideri il problema di “indovinare” un numero intero nel numero minimo di tentativi: ad ogni tentativo, l’algoritmo propone un valore ad un oracolo, che conosce il numero da indovinare. L’oracolo risponde dicendo se il numero proposto sia maggiore, minore o uguale a quello da indovinare (nell’ ultimo caso il gioco termina). Si proponga un algoritmo efficiente

e se ne esprima la complessità temporale in funzione del generico numero N da indovinare