-
Notifications
You must be signed in to change notification settings - Fork 0
/
analisi-ammortizzata.tex
160 lines (107 loc) · 6.7 KB
/
analisi-ammortizzata.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
\section{Analisi ammortizzata}
Si consideri il tempo richiesto per eseguire, nel \textbf{caso pessimo}, un'intera sequenza di operazioni. Se le operazioni costose sono relativamente meno frequenti allora il costo richiesto per eseguirle può essere ammortizzato con l'esecuzione delle operazioni meno costose.
\subsection{Metodo dell'aggregazione}
Si basa sul concetto di \textbf{costo ammortizzato}: data una sequenza di $n$ istruzioni aventi complessità $O(f(n))$, il costo ammortizzato della singola operazione si ottiene dividendo la complessità totale per il numero di istruzioni.
$$\hat{c}=\frac{O(f(n))}{n}$$
\subsection{Metodo degli accantonamenti (o dei crediti)}
Si caricano le operazioni meno costose di un costo aggiuntivo. Il costo aggiuntivo viene assegnato come \textbf{credito prepagato} a certi oggetti nella struttura dati. I crediti accumulati saranno usati per pagare le operazioni più costose su tali oggetti.
Il costo ammortizzato delle operazioni meno costose è il costo effettivo aumentato del costo aggiuntivo.
Il costo ammortizzato delle operazioni più costose è il costo effettivo diminuito del credito prepagato utilizzato.
Il costo artificiale fornisce un \textbf{limite superiore} al costo ammortizzato.
\subsection{Metodo del potenziale}
Si associa alla struttura dati $D$ un \textbf{potenziale} $\Phi(D)$ tale che la modifica della struttura dati dovuta alle operazioni meno costose comporti un aumento del potenziale, mentre le operazioni meno costose lo facciano diminuire.
Il costo ammortizzato è quindi la \textbf{somma algebrica} del costo effettivo e della variazione di potenziale. $D_i$ è la struttura dati dopo la \textit{c}-esima operazione e $c_i$ + il costo dell'\textit{i}-esima operazione.
$$\hat{c}_i=c_i+\Phi(D_i)-\Phi(D_{i-1})$$
Il costo ammortizzato di una sequenza di $n$ operazioni è:
$$\hat{c}=\sum_{i=1}^n\hat{c}_i=\sum_{i=1}^n[c_i+\Phi(D_i)-\Phi(D_{i-1})]$$
$$=c+\Phi(D_n)-\Phi(D_0)$$
Se la variazione $\Phi(D_n)-\Phi(D_0)$ del potenziale relativo all'esecuzione di tutta la sequenza non è negativa allora il costo ammortizzato $\hat{c}$ è una \textbf{maggiorazione} del costo reale $c$.
Altrimenti un valore $\Phi(D_n)-\Phi(D_0)$ negativo deve essere compensato con un aumento adeguato del costo ammortizzato delle operazioni.
\subsection{Esercizio 1}
Si vuole realizzare un contatore binario usando un array $A[0...k]$ per memorizzare i $k+1$ bit $b_k...b_1b_0$ della rappresentazione binaria del valore $x$ del contatore. Si vuole che il contatore possa iniziare anche con un valore maggiore di zero. A tale scopop si vuole che, oltre all'operazione \textbf{increment}, che aumenta di 1 il valore del contatore, sia prevista anche un'operazione iniziale \textbf{SET(A,n)}, che inizializza ad n il valore del contatore.
Usare il \textbf{metodo di aggregazione} per dimostrare che le operazioni di una sequenza costituita da una set seguita da $m$ increment, con $m=\Omega(k)$ hanno costo ammortizzato costante.
\linebreak
\linebreak
\textbf{Soluzione}:Vediamo anzitutto gli pseudo-codici delle due funzioni:
\begin{lstlisting}
Increment(A)
i = 0
while i<=k and A[i]==1
A[i] = 0
i++
if i<=k
A[i] = 1
\end{lstlisting}
\begin{lstlisting}
Set(A,n) // O(k)
// PRE: A azzerato
while i<=k and n>0
A[i] = n%2
n = n/2 // preso per difetto
i++
\end{lstlisting}
Sia $\Phi(A)=$``numero di bit impostati a 1''. Il costo di una increment è $c=1+t$, dove $t\ge0$ è il numero di bit trasformati in 1 da 0. Sia $A_0$ lo stato iniziale del contatore azzerato ed $A_1$ il suo stato dopo aver eseguito una Set(A,n). Supponiamo di effettuare $m$ esecuzioni di increment per valutare l'analisi ammortizzata:
$$\Delta\Phi=\Phi(A_m)-\Phi(A_1)=t-1$$
Il numero di bit 1 rispetto ad $A_1$ varia di $-t+1$ in $A_m$. Dunque aggiungiamo $k$ alla formula per calcolare $\hat{c}$, distribuendolo a tutte le operazioni;
$$\hat{c}=c+\Phi(A_n)-\Phi(A_0)+\frac{k}{m}=1+t-t+1+\frac{k}{m}$$
Alla fine il costo ammortizzato è $O(1+\frac{k}{m})$, $m=\Omega(k), m\ge k$.
$$\frac{O(k)+O(1+\frac{k}{m})}{m+1}=O(\frac{k+1+k/m}{m+1})\le O(\frac{k+1+k/k}{k+1})=O(\frac{k+2}{k+1})=O(1)$$
\subsection{Esercizio 2}
Si vuole realizzare un timer usando un array $A$ per memorizzare i $k+1$ bit $b_k,....,b_1,b_0$ della rappresentazione binaria del valore del timer. Le operazioni previste per un timer sono \textit{Set(A,n)} che carica il timer ad $n$ secondi e \textit{Decrement(A)} che diminuisce di un secondo il valore del timer. L'operazione Set si può eseguire solamente quando il timer è azzerato mentre l'operazione Decrement si può eseguire soltanto quando il timer ha valore maggiore di 0. Scrivere le due funzioni Set e Decrement ed analizzarne la complessità ammortizzata.
\linebreak
\linebreak
\textbf{Suggerimento}: Memorizzare l'indice $m$ del bit 1 più significativo ($m=-1$ se tutti i bit sono 0, $m=k$ se tutti i bit sono a 1) ed usare come funzione potenziale il numero di bit uguali a 0 che precedono $A[m]$ più due volte il numero di bit che seguono $A[m]$ (che sono tutti 0), ossia $\Phi=\sum_{i=0}^{m-1}(1-b_i)+2(k-m)$.
\linebreak
\linebreak
\textbf{Soluzione}: Vediamo anzitutto gli pseudo-codici delle due operazioni:
\begin{lstlisting}
Set(A,n) // tutti i bit a 0, n<2^{k+1}
k = A.lenght
i = 0 // parto dal bit meno significativo
while n>0 and i<=k
A[i] = n%2 // il resto della divisione per 2
n = n/2 // divisione intera per difetto
i++
if i>k
error "underflow"
else
A.m = i-1
\end{lstlisting}
\begin{lstlisting}
Decrement(A)
i = 0
while A[i] == 0
A[i] = 1
i++
A[i] = 0 // ora devo mettere apposto l'n
if A.m == i
A.m = A.m-1
\end{lstlisting}
\textbf{Analisi ammortizzata di Set}:
$$\hat{c}=c+\Delta\Phi$$
$$\Delta\Phi=\Phi+\Phi'=2(k-m)+\sum_{i=0}^{m-1}(1-b_i)-2(k+1)=$$
$$=2k-2m+\sum_{i=0}^{m-1}(1-b_i)-2k-2$$
$$\hat{c}\le m+1-2m+m-2 \le -1$$
Il costo è costante quindi ho concluso la dimostrazione.
\linebreak
\linebreak
\textbf{Analisi ammortizzata di Decrement}
\linebreak
\linebreak
$c=c+1$, proporzionale a $t-1$, dove $t$ è il numero di bit trasformati in 0.
$$\hat{c}=c+\Delta\Phi$$
$$\Delta\Phi=\Phi-\Phi'=2(k-m)+\sum_{i=0}^{m-1}(1-b_i)-2(k-m')+\sum_{i=0}^{m'-1}(1-b_i)=$$
$$-2m+2m'-t+1$$
$m$ ed $m'$ possono al massimo diversi tra loro di 1, quindi:
$$\Delta\Phi\le 2-t+1=3-t$$
$$\hat{c}=t+1+3-t=4$$
Ottengo un valore costante, inoltre:
$$\Phi_0=2(k+1)$$
In questo caso perchè il costo ammortizzato vada bene deve essere maggiore o uguale del costo reale.
Prendiamo le operazioni di segno:
$$\hat{c}_i=c_i+\Phi_i-\Phi_{i-1}$$
$$\sum_{i=1}^n\hat{c}_i=\sum_{i=1}^n\hat{c}_i+\Phi_n+\Phi_0\le\sum_{i=0}{n}(\hat{c}_i-\frac{\Phi_0}{n})$$
$$\hat{c}_i=c_i+\frac{\Phi_0}{n}$$
Devo distribuire, il costo ammortizzato è quindi:
$$\hat{c}=4+\frac{2(k+1)}{n}$$
Se $n=\Omega(k) \Rightarrow \hat{c}=O(1)$