Home

Federica EU

1/29

Massimo Benerecetti » 1.Analisi di algoritmi

Algoritmo

Un algoritmo è una procedura ben definita per risolvere un problema: una sequenza di passi che, eseguiti da un esecutore, portano alla soluzione del problema.

La sequenza di passi che definisce un algoritmo deve essere descritta in modo finito.

Viene di seguito riportato un semplice algoritmo che calcola il numero delle coppie (i,j) di numeri compresi tra 1 e N, tali che i ≤ j.

int Count1(int N)

sum = 0 for i = 1 to N

for j = i to N

sum = sum + 1

return sum

Proprietà degli algoritmi

Non ambiguità: tutti i passi che definiscono l’algoritmo devono essere non ambigui e chiaramente comprensibili all’esecutore;

Generalità: la sequenza di passi da eseguire dipende esclusivamente dal problema generale da risolvere, non dai dati che ne definiscono un’istanza specifica;

Correttezza: un algoritmo si dice corretto se esso produce il risultato corretto a fronte di qualsiasi istanza del problema ricevuta in ingresso. Può essere stabilita tremite:
- dimostrazione formale (matematica);
- ispezione informale;

Efficienza: è la misura delle risorse computazionali che esso impiega per risolvere un problema. Alcuni esempi sono:
- tempo di esecuzione;
- memoria impiegata;
- altre risorse: banda di comunicazione.

Modello computazionale e analisi di algoritmi

Un algoritmo, a differenza di un programma, è definito in maniera indipendente dallo specifico esecutore (ad esempio un calcolatore) che lo dovrà utilizzare.
Al fine di studiare le proprietà di efficienza di un algoritmo, avremo bisogno di introdurre un modello astratto di computazione.
Tale modello di computazione dovrà essere sufficientemente generale da poter rappresentare in maniera astratta il funzionamento di un qualsiasi calcolatore.
Tra gli esempi più noti di modelli di computazione ricordiamo la Macchina di Turing e la Macchina RAM.
Dato un modello di computazione, l’analisi di efficienza di un algoritmo si ridurrà, quindi, a calcolare quante risorse del modello computazionale (spazio o tempo) siano necessarie per completare la computazione determinata dall’algoritmo a fronte dell’input che esso riceve.
Ci concentreremo, a titolo di esempio, nell’analisi del tempo di esecuzione di un algoritmo.

Il Modello della Macchina RAM

Il modello RAM (Random-Access Memory) è un modello di computazione che consiste di:

una memoria principale infinita
- Ogni cella di memoria può contenere una quantità di dati finita.
- Impiega lo stesso tempo per accedere ad ogni cella di memoria.
un singolo processore + programma:
- la computazione che può essere eseguita in 1 unità di tempo:
- operazioni di lettura, scrittura in memoria;
- calcoli elementari: addizione, moltiplicazione, confronto, …

Il modello RAM è un’astrazione dei moderni computer.

Il nostro scopo è ora quello di calcolare quante operazioni elementari siano necessarie ad una macchina aderente al modello RAM al fine di completare l’esecuzione di un algoritmo che riceve in ingresso un’istanza di problema di una dimensione N.
Tale quantità, essendo dipendente dalla dimensione N dell’input, risulterà essere una funzione di N e prenderà il nome dei funzione tempo.
Se N denota la dimensione dell’input, denoteremo la funzione tempo con T(N).

Esempio 1

Un problema di conteggio

Algoritmo che calcola il numero delle coppie (i,j) di numeri compresi tra 1 e N, tali che i ≤ j.

int Count1(int N)

1 sum = 0 2 for i = 1 to N

3 for j = i to N

4 sum = sum + 1

5 return sum

Esempio
Input: N=4
(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)
Output = 10

Calcolo il tempo di esecuzione

Come si calcola il tempo di esecuzione di un algoritmo?

per ogni linea, si calcola il numero di operazioni elementari che la sua esecuzione comporta;
se una linea viene ripetuta più volte (ad esempio perché contenuta nel corpo di un ciclo iterativo) durante l’esecuzione, è necessario calcolare quante volte viene eseguita e moltiplicare questo numero per il numero di operazioni elementari che essa comporta;
infine, si sommano i contributi delle linee e si cerca di calcolare la funzione risultante.

Analisi dell’esempio 1

Vogliamo calcolare il numero di operazioni elementari necessarie a completare la computazione per un valore di N in ingresso (che in questo caso rappresenta la dimensione dell’istanza del problema).

int Count1(int N)

1 sum = 0 (assegnamento a sum)

2 for i = 1 to N $\xrightarrow{\hspace{3cm}} \sum_{i=1}^{N+1} 2$

3 for j = i to N $\xrightarrow{\hspace{2.7cm}} \sum_{i=1}^{N} \sum_{j=i}^{N+1} 2$

4 sum = sum + 1 $\xrightarrow{\hspace{2cm}} \sum_{i=i}^{N} \sum_{j=1}^{N} 2$

5 return sum $\xrightarrow{\hspace{3.8cm}} 1$ (lettura di sum)

Assumiamo che la testa di un ciclo for impieghi 2 operazioni elementari (una per l’incremento o assegnamento e una per la valutazione della condizione di terminazione).
Si noti che la testa di un ciclo for (così come per un ciclo while) viene sempre eseguita una volta un più del suo corpo.

Analisi dell’esempio 1

int Count1(int N)

1 sum = 0 (assegnamento a sum)

2 for i = 1 to N

3 for j = i to N

4 sum = sum + 1

5 return sum (lettura di sum)

Sommando tra di loro i termini a destra delle frecce otteniamo la seguente funzione di T(N) per il tempo di esecuzione dell’algoritmo:
$T(N) = 2+2(N+1)+2\sum_{i=1}^{N}\sum_{j=i}^{N+1}1+2\sum_{i=1}^{N} \sum_{j=i}^{N}1 = 2N^2 + 6N + 4$

Esempio 2

Poiché è evidente che il numero di incrementi di sum, fissato i, è pari a N-i+1, anche la seguente versione dell’algoritmo risolve correttamente il problema:

int Count2(int N)

1 sum = 0 (assegnamento a sum)

2 for i = 1 to N

3 sum = sum + (N-i+1)

4 return sum (lettura di sum)

Assumendo che la riga 3 corrisponda a 7 operazioni elementari (3 operazioni aritmetiche, 3 letture in memoria e una scrittura).
Smmando tra di loro i termini a destra delle frecce otteniamo la seguente funzione di T(N) per il tempo di esecuzione dell’algoritmo:
$T(N) = 2+2\sum_{i=1}^{N+1}1+7\sum_{i=1}^{N}1 = 2+2(N+1)+7N = 9N + 4$

Esempio 3

Poiché, nell’algoritmo precedente il valore di sum è inizializzata a 0 e, per ogni valore di i ( $1\leq i \leq N$ ), viene incrementata di N-i+1, è evidente che il valore finale di sum sarà

$\sum_{i=1}^{N} (N-i+1) = \sum_{i=1}^{N} i = \frac{N(N+1)}{2}$

Quindi il seguente algoritmo risolve il problema correttamente:

int Count3(int N) 1 sum = N*(N+1)/2 (3 op. aritmetiche, una lettura e una scrittura) 2 return sum (lettura di sum)
È, quindi, chiaro che il tempo di esecuzione risulta essere $T(N) = 6$

Tempi di esecuzione di algoritmi

Tempi di esecuzione di algoritmi con la funzione di tempo indicata nella riga in prima colonna, al variare della dimensione dell'input (supponenedo che un'operazone atomica impieghi 1 ηs=10^-9 s).

Notazione asintotica e analisi di algoritmi

Confrontare tra di loro due algoritmi dal punto di vista dell’efficienza significa confrontare la velocità di decadimento delle loro prestazioni a fronte dell’aumento della dimensione del problema che ricevono in ingresso.
A tal fine è sufficiente confrontare l’andamento asisntotico delle loro le loro funzioni del tempo di esecuzione.
Nelle slide a segiure, verranno introdotte tre notazioni asisntotiche, che permettono di esprimere in maniera sintetica rispettivamente le relazioni di efficienza maggiore, minore ed equivalente tra due algoritmi.

Notazioni asintotiche: limite superiore

La funzione g(n) è detta limite superiore asintotico di f(n) se solo se $\exists c>0, n_0>0\ \forall n \geq n_0.\ f(n) \leq c g(n)$
Scriviamo $f(n) = O(g(n))$
Leggiamo f(n) è O-grande di g(n).
Intuitivamente, una funzione g(n) è limite superiore asintotico per la funzione f(n) se, asintoticamente, f(n) non cresce più velocemente di g(n).

In figura: Rappresentazione grafica della relazione $f(n) = O(g(n))$

Notazione O-grande: esempio

Si consideri la funzione $f(n) = 3n^2 + 5$ .

Per mostrare che $f(n) = O(n^2)$ dobbiamo individuare due costanti positive $c$ e $n_0$ tali per cui

$\forall n \geq n_0. f(n) \leq c g(n)$

Scegliendo $c=4$ e $n_0=3$ otteniamo:

$4 g(n) = 4n^2 = 3n^2 + n^2$

Si noti che, per ogni n ≥ 3, $n^2 \geq 9$ , quindi

$3n^2 + n^2 \geq 3n^2 + 9$ per ogni n ≥ 3

Per transitività, possiamo quindi affermare che, per ogni n ≥ 3

$4n^2 \geq 3n^2 + 9 > 3n2 + 5 = f(n)$

Concludiamo, quindi, che $f(n) = O(g(n))$ .

In figura: Rappresentazione grafica della relazione $3n^2+5 = O(n^2)$

Notazioni asintotiche: limite inferiore

La funzione g(n) è detta limite inferiore asintotico di f(n) se solo se $\exists c>0, n_0>0\ \forall n \geq n_0. f(n) \geq c g(n)$
Scriviamo $f(n) = \Omega(g(n))$
Leggiamo f(n) è Omega-grande di g(n).
Intuitivamente, una funzione g(n) è limite inferiore asintotico per la funzione f(n) se, asintoticamente, f(n) non cresce più lentamente di g(n).

In figura: Rappresentazione grafica della relazione $3n^2+5 =\Omega(n^2)$

Notazione Ω-grande: esempio

Si consideri la funzione $f(n) = \frac{n^2 }{2} - 7$ .

Per mostrare che $f(n) = \Omega(n^2)$ dobbiamo individuare due costanti positive $c$ e $n_0$ tali per cui

$\forall n \geq n_0. f(n) \geq c g(n)$

Scegliendo $c=\frac{1}{4}$ e $n_0=4$ otteniamo:

$\frac{1}{4} g(n) = \frac{1}{4}n^2 = \frac{1}{2}n^2 - \frac{1}{4}n^2$

Si noti che, per ogni n ≥ 6, $\frac{1}{4}n^2 \geq 9$ , quindi

$\frac{1}{2}n^2 - \frac{1}{4}n^2 \leq \frac{1}{2}n^2 - 9 \leq \frac{1}{2}n^2 - 7$ per ogni n ≥ 6

Per transitività, possiamo quindi affermare che, per ogni n ≥ 6

$\frac{1}{4}n^2 < \frac{1}{2}n^2 - 7 = f(n)$

Concludiamo, quindi, che $f(n) = \Omega(g(n))$ .

Rappresentazione grafica della relazione [tex]\frac{1}{2}n^2-7 = \Omega(n^2)[/tex].

Notazioni asintotiche: limite stretto

La funzione g(n) è detta limite asintotico stretto di f(n) se solo se $\exists c_1,c_2>0,n_0>0\ \forall n \geq n_0.\ c_1 g(n) \leq f(n) \leq c_2 g(n)$
Scriviamo $f(n) = \Theta(g(n))$
Leggiamo f(n) è Theta di g(n).
Intuitivamente, una funzione g(n) è limite asintotico stretto per la funzione f(n) se, asintoticamente, f(n) cresce con la stessa velocità di g(n).
Si noti che, per definizione, $f(n) = \Theta(g(n))$ se e soltanto se vale sia $f(n) = O(g(n))$ che $f(n) = \Omega(g(n))$

Didascalia immagine Non superare i 90 caratteri spazi inclusi.

Proprietà delle notazioni asintotiche

Alcuni teoremi sulle notazioni asintotiche:

$f(n) = O(g(n))$ se e solo se $g(n) = \Omega(f(n))$ .
Se $f_1(n)=O(f_2(n))$ e $f_2(n)=O(f_3(n))$ , allora $f_1(n)=O(f_3(n))$
Se $f_1(n)=\Omega(f_2(n))$ e $f_2(n)=\Omega (f_3(n))$ , allora $f_1(n)=\Omega (f_3(n))$
Se $f_1(n)=\Theta(f_2(n))$ e $f_2(n)=\Theta (f_3(n))$ , allora $f_1(n)=\Theta (f_3(n))$
Se $f_1(n) = O(g_1(n))$ e $f_2(n) = O(g_2(n))$ , allora $O(f_1(n) + f_2(n)) = O(max\{g_1(n), g_2(n)\})$
Se f(n) è un qualsiasi polinomio di grado d, allora $f(n) = \Theta(n^d)$

Notazioni asintotiche e limiti asintotici

Le notazioni asintotiche sono ricondicubili ai seguenti limiti asintotici:

Se $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = 0$ allora $f(n) = O(g(n))$

Se $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = k > 0$ allora $f(n) = O(g(n))$

e $f(n) = \Omega(g(n))$
quindi $f(n) = \Theta(g(n))$

Se $\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)} = \infty$ allora $f(n) = \Omega(g(n))$

Somma della massima sottosequenza contigua

Consideriamo il seguente problema:

Siano dati in input un intero N, con N ≥ 1, e una sequenza A=(a₁, a₂,…, a_N) di N valori interi. Si vuole calcolare il più grande intero S tale che $S = \sum_{i}^{j}a_k$ per qualche $1 \leq i , j \leq N$

Si noti che tutti gli elementi nella sommatoria sono elementi contigui nella sequenza in input.

Esempio:
Input: N = 9 e A = (2,-4,8,3,-5,4,6,-7,2)
Output: 16, cioè la somma dei valori nella sottosequenza (8,3,-5,4,6) di A.

Prima soluzione

Una prima soluzione consiste nel generare tutti gli indici i e j (con i ≤ j), corrispondenti ai possibili estremi di una sottosequenza di A (si veda l’algoritmo Count1);
per ogni coppia di indici, calcolare nella variabile sum la somma dei valori di A tra essi contenuti;
usiamo la variabile maxsum per tenere traccia della somma massima corrente. Essa viene aggiornata ogni volta che si trova una nuova sottosequenza di somma maggiore.

L’algoritmo seguente risolve il problema:
int Max_seq_sum_1(int N, array A[])

maxsum = 0 for i = 1 to N do

for j = i to N do

sum = 0 for k = i to j do

sum = sum + A[k]

maxsum = max(maxsum,sum)

return maxsum

Analisi della prima soluzione

int Max_seq_sum_1(int N, array A[])
1 maxsum = 0 $\xrightarrow{\hspace{4cm}} 1$
2 for i = 1 to N do $\xrightarrow{\hspace{3cm}} 2(N+1)$

3 for j = i to N do $\xrightarrow{\hspace{2.7cm}}\sum_{i=1}^{N}\sum_{j=i}^{N+1} 2$

4 sum = 0 $\xrightarrow{\hspace{2.7cm}}\sum_{i=1}^{N}\sum_{j=i}^{N} 1$

5 for k = i to j do $\xrightarrow{\hspace{2.5cm}}\sum_{i=1}^{N}\sum_{j=i}^{N}\sum_{k=i}^{j+1} 2$

6 sum = sum + A[k] $\xrightarrow{\hspace{2.3cm}}\sum_{i=1}^{N}\sum_{j=i}^{N}\sum_{k=i}^{j} 5$

7 maxsum = max(maxsum,sum) $\xrightarrow{\hspace{2.7cm}}\sum_{i=1}^{N}\sum_{j=i}^{N} 3$

8 return maxsum $\xrightarrow{\hspace{4cm}} 1$
Eseguendo i calcoli della sommatoria otteniamo: $T(N) = \Theta(N^3)$

Seconda soluzione

È facile osservare che l’algoritmo precedente effettua spesso operazioni ripetutamente.
Poiché $\sum_{k=i}^{j+1}A[k] = A[j+1] + \sum_{k=i}^{j}A[k]$ è possibile ottenere il valore di sum di per la sequenza da i a j+1 in tempo costante, sommando A[j+1] al valore di sum già calcolato all’itarazione precedente.
A tal fine, è sufficiente mantenere inalterato il valore di sum tra le iterazioni che individuano sottosequenza che partono dallo stesso valore di i e riazzerare sum solo quando i viene incrementato.

L’algoritmo seguente risolve il problema incorporando l’osservazione appena fatta:

int Max_seq_sum_2(int N, array A[])

maxsum = 0 for i = 1 to N do

sum = 0 for j = i to N do

sum = sum + A[j] maxsum = max(maxsum,sum)

return maxsum

Analisi della seconda soluzione

Procediamo al calcolo del tempo di esecuzione:

int Max_seq_sum_2(int N, array A[])

1 maxsum = 0

2 for i = 1 to N do

3 sum = 0

4 for j = i to N do

5 sum = sum + A[j]

6 maxsum = max(maxsum,sum)

7 return maxsum

Eseguendo i calcoli della sommatoria otteniamo: $T(N) = \Theta(N^2)$

Analisi della seconda soluzione

Considerando la figura a fianco, possiamo osservare che le seguenti affermazioni sono vere:

Se $a_p + \ldots + a_r \geq 0$ allora $a_p+ \ldots +a_{r+k} \geq a_{r+1} +\ldots + a_{r+k}\ \ \forall k \geq 1$
Se $a_p+\ldots+a_j > 0$ per ogni $p \leq j \leq r-1$ ma $a_p+\ldots+a_r < 0$ allora $a_{p+j}+\ldots+a_{r+k} < a_{r+1} +\ldots+ a_{r+k}\ \ \forall 0 \leq j \leq r\ e\ \forall k \geq 1$

Nel caso 2, è evidente che ogni sottosequenza di A il cui punto d’inizio è inferiore a r+1 (e che termina oltre r) risulta avere una somma inferiore alla sua sottosequenza che parte da r+1.

In questo caso è dunque possibile ignorare tutte queste sottosequenze e considerare solo quelle che iniziano a partire dall’indice r+1.

Sottosequenza di A che illustra i casi enunciati a fianco.

Terza soluzione

L’algoritmo seguente risolve il problema sfruttando le osservazioni della slide precedente.

int Max_seq_sum_3(int N, array A[])

maxsum = 0 sum = 0 for j = 1 to N do

if (sum + A[j] > 0) then

sum = sum + A[j]

else

sum = 0

maxsum = max(maxsum,sum)

return maxsum

Confronto asintotico tra il tempo di esecuzione degli algoritmi presentati.

Terza soluzione

La variabile j contiene l’indice in cui termina la sottosequenza corrente;
ogni volta che la somma della sottosequenza che termina al valore corrente di j (chiamato r nella slide precedente) risulta negativa, si azzera il valore di sum;
l’azzeramento di sum simula lo spostamento del punto di partenza delle nuove sottosequenze da considerare al valore successivo (chiamato r+1 nella slide precedente) a quello corrente, che è quello che ha determinato la somma negativa.

Analisi della terza soluzione

Procediamo al calcolo del tempo di esecuzione:

int Max_seq_sum_3(int N, array A[])

1 maxsum = 0

2 sum = 0

3 for j = 1 to N do

4 if (sum + A[j] > 0) then 5

5 sum = sum + A[j]

else

6 sum = 0

7 maxsum = max(maxsum,sum)

8 return maxsum

Considerando che sia una esecuzione della linea 5 che una della linea 6 impiegano tempo costante (rispettivamente, 5 e 1 operazioni elementari ), possiamo concludere che, complessivamente, il numero di operaizoni elementari dovute alle esecuzioni del costrutto if then else non è superiore a 10N.

In conclusione, risulta $T(N) = \Theta(N)$ .

Conclusione

Possiamo, in conclusione, affermare che le tre soluzioni al problema hanno proprietà di efficienza tra loro molto differenti.
La tabella a fianco mostra come la seconda versione dell’algoritmo sia asintoticamente migliore della prima e la terza migliore della seconda.
L’analisi qui effettuata rivela quindi che, ai fini di una implementazione, la terza versione è sicuramente quella da considerare.

Confronto asintotico tra il tempo di esecuzione degli algoritmi presentati.

Le lezioni del Corso

1. Analisi di algoritmi

2. Algoritmi di Ordinamento: InsertionSort e analisi per casi

3. Analisi di algoritmi ricorsivi

4. L'algoritmo di ordinamento HeapSort I

5. L'algoritmo di ordinamento HeapSort II