FormularioAlgoritmi per l'Ingegneria: definizioni, teoremi e formule delle note, in ordine di capitolo

1. Problemi computazionali e analisi degli algoritmi

Problemi computazionali - istanze, soluzioni, correttezza e complessità

Definizione (algoritmo). Un algoritmoProcedura finita e deterministica: sequenza di passi elementari di un modello di calcolo. è una procedura computazionale finita e deterministica, specificata come sequenza di passi elementari (istruzioni) di un dato modello computazionale, che trasforma un ingresso in una e una sola uscita. Dal punto di vista insiemistico un algoritmo è una funzione $$A : \mathcal{I} \to \mathcal{O}$$ dall'insieme degli ingressi a quello delle uscite. La particolare funzione realizzata è descritta dalla sequenza finita di istruzioni.

Definizione (problema computazionale). Un problema computazionale è una specifica astratta della relazione tra un insieme di istanze $I$ e un insieme di soluzioni $S$: $$\Pi \subseteq I \times S, \qquad \Pi = \{(i_1, s_1), (i_2, s_2), \dots\}.$$ Si scrive anche $i \,\Pi\, s$ per $(i, s) \in \Pi$. La relazione deve essere:

1. totale: ogni istanza ha almeno una soluzione, $\forall i \in I,\ \exists s \in S : (i,s) \in \Pi$;
2. non necessariamente univoca: possono esistere $s_1 \neq s_2$ con $i \,\Pi\, s_1$ e $i \,\Pi\, s_2$.

Definizione (algoritmo che risolve un problema). Un algoritmo $A_\Pi : \mathcal{I} \to \mathcal{O}$ risolve $\Pi$ se $\mathcal{I} = I$, $\mathcal{O} = S$ e $$\forall i \in I : \quad A_\Pi(i) = s \ \Longrightarrow\ i \,\Pi\, s.$$

Definizione (correttezza). Provare che $A_\Pi$ è corretto per $\Pi$ significa dimostrare $$\forall i \in I : A_\Pi(i) = s \ \Longrightarrow\ i \,\Pi\, s.$$ Informalmente: la funzione di ingresso e uscita realizzata dall'algoritmo è coerente con la specifica.

Definizione (modello di costo). Un modello di costo associa a ogni istruzione del modello computazionale un costo non negativo $c_{\text{istr}} \in \mathbb{R}^+ \cup \{0\}$. Il costo dell'esecuzione di $A_\Pi$ sull'istanza $i$ è $$t_{A_\Pi, i} = \sum_{\text{istruzioni eseguite da } A_\Pi(i)} c_{\text{istr}}.$$

Definizione (taglia). La taglia di un'istanza, $\lvert i\rvert \in \mathbb{N}$, è una misura intera non negativa ragionevolmente rappresentativa della grandezza della codifica dell'istanza.

Definizione (tre complessità).

• Caso peggiore: $T_A(n) = \sup_{i \in I_n} t_{A,i}$.
• Caso migliore: $T_A(n) = \inf_{i \in I_n} t_{A,i}$.
• Caso medio: $T_A(n) = \mathbb{E}[t_{A,i}]$, media rispetto a una distribuzione fissata su $I_n$.

2. Il paradigma divide & conquer

Divide and conquer - proprietà di sottostruttura e albero delle chiamate

Definizione (proprietà di sottostruttura). Per $\Pi \subseteq I \times S$ è una terna $(n_0, D, C)$:

• una soglia $n_0 \in \mathbb{N}$ e la descrizione esplicita delle soluzioni delle istanze di base, cioè con $\lvert i\rvert \le n_0$;
• una funzione di Divide $D : I \to I^\star$, che a un'istanza $i$ con $\lvert i\rvert > n_0$ associa una sequenza di sottoistanze $\langle i_1, \dots, i_k\rangle$;
• una funzione di Conquer $C : S^\star \to S$, che da una sequenza di soluzioni ne costruisce una.

Devono valere, per ogni istanza non di base $i$ con $D(i) = \langle i_1, \dots, i_k\rangle$:

1. $\lvert i_j\rvert < \lvert i\rvert$ per $1 \le j \le k$ (le sottoistanze sono strettamente più piccole);
2. se $s_1, \dots, s_k \in S$ sono tali che $i_1 \,\Pi\, s_1, \dots, i_k \,\Pi\, s_k$, allora $i \,\Pi\, C(\langle s_1, \dots, s_k\rangle)$.

Teorema. Un albero binario pieno con $n$ foglie ha sempre $n - 1$ nodi interni.

Albero della ricorrenza e formula generale per le ricorrenze

Formula generale. $$T(n) = \sum_{\ell=0}^{f^\ast(n,n_0)} \left[\prod_{j=0}^{\ell-1} s\bigl(f^{(j)}(n)\bigr)\right] w\bigl(f^{(\ell)}(n)\bigr) \;+\; \left[\prod_{j=0}^{f^\ast(n,n_0)} s\bigl(f^{(j)}(n)\bigr)\right] T_0.$$

Master Theorem - enunciato, casi e applicazioni

Teorema (Master Theorem). La soluzione di $(\ast)$ soddisfa $$T(n) = \begin{cases} > \Theta\bigl(n^{\log_b a}\bigr) & \text{se } \exists\,\varepsilon > 0 : w(n) = O\bigl(n^{\log_b a - \varepsilon}\bigr) \quad \text{(Caso 1)} \\[4pt] > \Theta\bigl(n^{\log_b a}\log n\bigr) & \text{se } w(n) = \Theta\bigl(n^{\log_b a}\bigr) \quad \text{(Caso 2)} \\[4pt] > \Theta\bigl(w(n)\bigr) & \text{se } \begin{cases} \exists\,\varepsilon > 0 : w(n) = \Omega\bigl(n^{\log_b a + \varepsilon}\bigr) \\ \exists\,c \in \mathbb{R},\ 0 < c < 1 : \forall n \quad a\,w(n/b) \le c\,w(n) \end{cases} \quad \text{(Caso 3)} > \end{cases}$$

3. Moltiplicazione di matrici

Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi

Teorema (proprietà frattale del prodotto). I quadranti di $C = A \times B$ si ottengono con la stessa formula del prodotto righe per colonne di matrici $2 \times 2$, dove al posto degli scalari ci sono i quadranti: per $1 \le i, j \le 2$

$$C_{ij} = \sum_{k=1}^{2} A_{ik} B_{kj} = A_{i1} B_{1j} + A_{i2} B_{2j}.$$

Proposizione. $T(n) = 2n^3 - n^2$ per ogni $n = 2^k$: RMUL esegue esattamente le stesse operazioni di MUL, solo in ordine diverso.

Algoritmo di Strassen e ibridazione

Definizione (ibridazione). Dati due algoritmi $A_1$ e $A_2$ per lo stesso problema, con $T_{A_1}(n) = o(T_{A_2}(n))$ ma con costanti moltiplicative più alte per $A_1$ nell'espressione esatta, l'ibridazione li combina in un algoritmo che ha lo stesso andamento asintotico del migliore ma, se possibile, costanti più basse.

Matrici circolanti e supercircolanti - algoritmi divide and conquer

Definizione. Una matrice $A$ di ordine $n = 2^k$ è supercircolante (SC) se: $n = 1$ (ogni scalare è SC di ordine $1$); oppure $n > 1$ e

$$A = \begin{pmatrix} A_1 & A_2 \\ A_2 & A_1 \end{pmatrix}$$

con $A_1, A_2$ matrici SC di ordine $\frac n2$ (quadranti alternati).

Teorema. Per ogni SC $A$ di ordine $n$ e ogni $v \in \mathcal B(n)$ vale $Av = \alpha v$ con $\alpha = r(A) \cdot v$ (prodotto scalare della prima riga con $v$).

Teorema. Se $A, B$ sono SC e $c(A), c(B), c(C)$ sono le prime righe viste come vettori colonna ($c(A) = r(A)^T$), il prodotto $C = AB$ soddisfa

$$c(C) = H(n)^{-1} \bigl[ (H(n)\,c(A)) \otimes (H(n)\,c(B)) \bigr],$$

dove $\otimes$ è il prodotto componente per componente.

Definizione. Una matrice $n \times n$ è circolante (CR) se ogni riga è la rotazione di una posizione verso destra della precedente, cioè $A_{(h+\ell) \bmod n,\,(k+\ell) \bmod n} = A_{h,k}$ per ogni $h, k, \ell$.

Teorema (convoluzione ciclica, forma matriciale). Per due CR $A, B$ di ordine $n$:

$$r(C)^T = \bigl(F^{(n)}\bigr)^{-1} \bigl[ \bigl(F^{(n)} r(A)^T\bigr) \otimes \bigl(F^{(n)} r(B)^T\bigr) \bigr].$$

Esponenziazione veloce per quadrature successive

Definizione (potenza). Per $x \in D$ e $n \in \mathbb N$:

$$x^n = \begin{cases} e & n = 0, \\ x \circ x^{n-1} = x^{n-1} \circ x & n > 0. \end{cases}$$

Per $n \ge 1$, $x^n = x \circ x \circ \dots \circ x$ ($n$ fattori), senza parentesi per l'associatività.

Proprietà. Sia $k = \lfloor \frac n2 \rfloor$.

• Se $n = 2k$ è pari: $x^n = x^k \circ x^k$.
• Se $n = 2k + 1$ è dispari: $x^n = x^k \circ x^k \circ x$.

4. Polinomi e FFT

Polinomi - rappresentazione per coefficienti e per valori e convoluzione

Definizione (polinomio di grado limitato da $n$). Il polinomio $$p(x)=\sum_{i=0}^{n-1}a_i x^i=a_0+a_1x+\dots+a_{n-1}x^{n-1}$$ è rappresentato con $n$ coefficienti dal vettore $\mathbf a=(a_0,\dots,a_{n-1})\in\mathbb C^n$ e si scrive $p(x)\equiv\mathbf a$. Il numero $n$ è il limite di grado (degree bound); il grado effettivo è $\max\{i:a_i\neq 0\}\le n-1$.

Teorema (interpolazione). Date $n$ coppie $(x_i,y_i)\in\mathbb C\times\mathbb C$ con $x_i\ne x_j$ per $i\ne j$, esiste uno e un solo polinomio $p$ di grado limitato da $n$ tale che $p(x_i)=y_i$ per $0\le i\le n-1$.

Definizione (rappresentazione per valori). Dato $\mathbf x\in\mathbb C^n$ a componenti distinte (la base), il polinomio $p$ di grado limitato da $n$ è rappresentato dalla coppia $(\mathbf x,\mathbf y)$ con $y_i=p(x_i)$. Basi diverse danno rappresentazioni diverse. L'unicità è garantita dal teorema.

Definizione (convoluzione lineare). Per $\mathbf a,\mathbf b\in\mathbb C^n$, il vettore $\mathbf c=\mathbf a\star\mathbf b\in\mathbb C^{2n-1}$ ha componenti $$c_j=\sum_{k=\max\{0,\,j-n+1\}}^{\min\{j,\,n-1\}}a_k\,b_{j-k},\qquad 0\le j\le 2n-2.$$ Se $p\equiv\mathbf a$ e $q\equiv\mathbf b$ allora $p(x)\,q(x)\equiv\mathbf a\star\mathbf b$. Con vettori di lunghezza $m$ e $n$ il risultato ha lunghezza $m+n-1$.

Teorema (costo della convoluzione per definizione). Calcolare $\mathbf a\star\mathbf b$ con $\mathbf a,\mathbf b\in\mathbb C^n$ richiede $n^2$ prodotti e $(n-1)^2$ somme, in tutto $2n^2-2n+1=\Theta(n^2)$ operazioni.

DFT, matrice di Fourier e radici n-esime dell'unità

Definizione (radice principale). La radice $n$-esima principale dell'unità è $\omega_n=e^{2\pi i/n}$. Le radici $n$-esime dell'unità sono le sue prime $n$ potenze, $\omega_n^0,\omega_n^1,\dots,\omega_n^{n-1}$, e formano il vettore $\Omega_n=(\omega_n^0,\dots,\omega_n^{n-1})$. Poiché $\omega_n^n=1$, vale $\omega_n^k=\omega_n^{\,k\bmod n}$ per ogni $k\in\mathbb Z$ (aritmetica modulare sugli esponenti; $\omega_n^{-1}=\omega_n^{n-1}$).

Definizione (DFT). La trasformata discreta di Fourier di ordine $n$ è la funzione $\mathrm{DFT}_n:\mathbb C^n\to\mathbb C^n$ che a $\mathbf a$ (coefficienti di $p$) associa le valutazioni di $p$ sulle radici $n$-esime dell'unità: $$y_i=p(\omega_n^i)=\sum_{j=0}^{n-1}a_j\,\omega_n^{ij},\qquad 0\le i\le n-1.$$ La coppia $(\Omega_n,\mathbf y)$ è una rappresentazione per valori di $p$ (le radici sono distinte, quindi vale il teorema di interpolazione).

Lemma di cancellazione. Per $n,d$ interi positivi e $k\in\mathbb Z$: $\omega_{dn}^{dk}=\omega_n^k$.

Lemma di dimezzamento. Per $n>0$ pari, i quadrati $(\omega_n^i)^2$, $0\le i\le n-1$, coincidono a coppie: per $0\le i\le n/2-1$ vale $$(\omega_n^i)^2=(\omega_n^{\,i+n/2})^2=\omega_{n/2}^{\,i}.$$ Elevando al quadrato le $n$ radici $n$-esime si ottengono quindi le $n/2$ radici $n/2$-esime, ciascuna due volte.

Lemma di somma. Per $n>1$ e $k\ge0$ interi: $$\sum_{j=0}^{n-1}\bigl(\omega_n^k\bigr)^j=\begin{cases}n&\text{se }k\text{ è multiplo di }n,\\0&\text{altrimenti.}\end{cases}$$

Teorema (convoluzione lineare). Siano $\mathbf a,\mathbf b\in\mathbb C^n$ e $\mathbf c=\mathbf a\star\mathbf b\in\mathbb C^{2n-1}$. Allora $$(\mathbf c\,|\,0)=\mathrm{DFT}^{-1}_{2n}\Bigl(\mathrm{DFT}_{2n}\bigl((\mathbf a|\mathbf 0_n)\bigr)\odot\mathrm{DFT}_{2n}\bigl((\mathbf b|\mathbf 0_n)\bigr)\Bigr),$$ dove $|$ indica la concatenazione (padding con zeri), $\odot$ il prodotto componente per componente.

Fast Fourier Transform - algoritmo ricorsivo e trasformata inversa

Teorema (sottostruttura). Siano $\mathbf y=\mathrm{DFT}_n(\mathbf a)$, $\mathbf y^{[0]}=\mathrm{DFT}_{n/2}(\mathbf a^{[0]})$, $\mathbf y^{[1]}=\mathrm{DFT}_{n/2}(\mathbf a^{[1]})$. Per $0\le i\le n/2-1$: $$y_i=y^{[0]}_i+\omega_n^i\,y^{[1]}_i,\qquad y_{i+n/2}=y^{[0]}_i-\omega_n^i\,y^{[1]}_i.$$

Teorema (matrice inversa di Fourier). $\bigl[F_n^{-1}\bigr]_{ij}=\dfrac1n\,\omega_n^{-ij}$ per $0\le i,j\le n-1$.

Trasformate notevoli ed esponenziazione di polinomi con la FFT

Definizione. Siano $n$ e $k$ potenze di due, $1\le k\le n$. Un vettore $\mathbf x\in\mathbb C^n$ è $(n,k)$-sparso se $x_i=0$ per ogni indice $i$ con $i\bmod k\ne0$.

5. Programmazione dinamica

Programmazione dinamica - Fibonacci, memoizzazione e schema del paradigma

Definizione. Si pone $F_0 = F_1 = 1$ e $F_n = F_{n-1} + F_{n-2}$ per $n > 1$. I primi valori sono $1, 1, 2, 3, 5, 8, 13, 21, \dots$

Definizione (sottostruttura ottima). Un problema di ottimizzazione ha la proprietà di sottostruttura ottima se una soluzione ottima di un'istanza si ottiene da soluzioni ottime di istanze più piccole.

Longest Common Subsequence - ricorrenza, tabella e ricostruzione

Definizione (LCS). Date $X = \langle x_1, \dots, x_m \rangle$ e $Y = \langle y_1, \dots, y_n \rangle$, determinare una stringa $Z = \langle z_1, \dots, z_k \rangle$ di lunghezza massima che sia sottosequenza sia di $X$ sia di $Y$.

Teorema (sottostruttura della LCS). Siano $X_i$, $Y_j$ prefissi di $X$ e $Y$ e sia $Z = \langle z_1, \dots, z_k \rangle$ una LCS di $X_i$ e $Y_j$.

1. Se $i = 0$ o $j = 0$, allora $Z = \varepsilon$.
2. Se $i > 0$ e $j > 0$:
   • (a) se $x_i = y_j$, allora $z_k = x_i = y_j$ e $Z_{k-1} = \langle z_1, \dots, z_{k-1} \rangle$ è una LCS di $X_{i-1}$ e $Y_{j-1}$;
   • (b) se $x_i \ne y_j$, allora $Z$ è una LCS di $X_{i-1}, Y_j$ oppure di $X_i, Y_{j-1}$, e quindi è la più lunga tra le due.

Matrix Chain Multiplication - parentesizzazione ottima

Definizione (MCM). Dato $p \in (\mathbb{N}^+)^{n+1}$, determinare la parentesizzazione della catena associata che richiede il minimo numero di prodotti tra scalari.

Teorema. $P(n) \ge \dfrac{2^{n-1}}{n}$ per ogni $n \ge 1$.

Teorema (sottostruttura ottima). Sia $i < j$ e sia $T^*_{i..j}$ un albero ottimo per $\langle A_i, \dots, A_j \rangle$. Allora esiste $k^*$ con $i \le k^* < j$ tale che la radice ha come sottoalberi due alberi ottimi $T^*_{i..k^*}$ e $T^*_{k^*+1..j}$, e $$c(T^*_{i..j}) = c(T^*_{i..k^*}) + c(T^*_{k^*+1..j}) + p_{i-1}\, p_{k^*}\, p_j,$$ dove $k^*$ è un indice che minimizza $c(T^*_{i..k}) + c(T^*_{k+1..j}) + p_{i-1} p_k p_j$ su $i \le k < j$.

6. Programmazione dinamica su stringhe

Allineamento di stringhe e sottosequenza palindroma più lunga

Definizione (allineamento). Date $X = \langle x_1, \dots, x_m \rangle$ e $Y = \langle y_1, \dots, y_n \rangle$ su $\Sigma_{DNA}$, un allineamento di lunghezza $k$ è una coppia di stringhe $Z^X = \langle z^X_1, \dots, z^X_k \rangle$, $Z^Y = \langle z^Y_1, \dots, z^Y_k \rangle$ su $\Sigma^E_{DNA}$, con $k \ge \max\{m, n\}$, tali che:

1. $X$ è sottosequenza di $Z^X$ e $Y$ è sottosequenza di $Z^Y$ (esistono $1 \le i_1 < \dots < i_m \le k$ con $X = \langle z^X_{i_1}, \dots, z^X_{i_m} \rangle$, e analogamente per $Y$);
2. le posizioni che non realizzano caratteri di $X$ (rispettivamente $Y$) contengono solo $-$;
3. in ogni posizione $r$ non ci sono due $-$: $(z^X_r \in \Sigma_{DNA}) \lor (z^Y_r \in \Sigma_{DNA})$.

Definizione. Una stringa $Z = \langle z_1, \dots, z_m \rangle$ è palindroma se $z_{1+h} = z_{m-h}$ per $0 \le h \le m - 1$, cioè $Z$ è uguale alla stringa letta al contrario. La stringa vuota è palindroma ($m = 0$). Esistono palindrome di lunghezza pari ($\langle A, C, C, A \rangle$) e dispari ($\langle A, I, A \rangle$).

Memoizzazione di ricorrenze triangolari - conteggio esatto e diagonali costanti

Proposizione. Per ogni $1 \le \ell \le n$, tutti gli elementi $M(i, j)$ con $j - i + 1 = \ell$ valgono uno stesso numero $V(\ell)$, dove $$V(\ell) = \begin{cases} 1 & \ell = 1 \\ 2 & \ell = 2 \\ V(\ell - 1)^2 \cdot V(\ell - 2) & \ell \ge 3 \end{cases}$$

7. Il paradigma greedy

Paradigma greedy - scelta golosa, sottostruttura e selezione delle attività

Proprietà di scelta greedy. Esiste sempre una soluzione ottima che contiene la scelta greedy. Garantisce che la scelta incauta non compromette l'ottimalità.

Proprietà di sottostruttura ottima. Esiste una soluzione ottima che, oltre alla scelta greedy, contiene una soluzione ottima della sottoistanza residua.

Teorema (schema di correttezza). Se un algoritmo greedy compie ogni volta la scelta greedy, fa il clean-up e risolve ricorsivamente la residua, e valgono le due proprietà, allora ritorna una soluzione ottima.

Dimostrazione. Per induzione sulla taglia dell'istanza. Base: istanza vuota, la soluzione vuota è ottima. Passo: si assume l'algoritmo corretto sulle istanze più piccole, in particolare sulla residua, che è strettamente più piccola. Per le due proprietà esiste un ottimo $A^\star$ composto dalla scelta greedy e da una soluzione ottima della residua. L'algoritmo ritorna la scelta greedy più la soluzione che l'ipotesi induttiva garantisce ottima per la residua: ha lo stesso costo di $A^\star$, quindi è ottima. $\square$

Definizione. Due attività $a_i$ e $a_j$ sono compatibili se gli intervalli sono disgiunti, $[s_i, f_i) \cap [s_j, f_j) = \emptyset$, cioè se $$s_j \ge f_i \quad\text{oppure}\quad s_i \ge f_j .$$ Un sottoinsieme è mutuamente compatibile se lo sono tutte le coppie. Il problema (activity selection) chiede un sottoinsieme mutuamente compatibile di cardinalità massima.

Codifica di Huffman - codici prefissi, algoritmo e ottimalità

Definizione (codice prefisso). Una codifica è libera da prefissi (prefix-code) se nessuna parola è prefisso di un'altra.

Teorema. Un codice prefisso è invertibile sulle stringhe, e si decodifica con una sola scansione leggendo i bit fino a incontrare una parola.

Dimostrazione. Si legge dall'inizio il minimo numero di bit che forma una parola: questa è l'unica parola con tale inizio, perché una seconda parola, essendo anch'essa un inizio della stessa sequenza, sarebbe prefisso della prima o viceversa. Il primo carattere è dunque determinato; si ripete dal bit successivo. $\square$

Definizione (costo di un trie). $B(T) = \displaystyle\sum_{c \in C} d_T(c)\, f(c)$ (lunghezza media in bit per carattere).

Lemma di scambio. Siano $a, b$ due foglie di un trie $T$ con $f(a) \le f(b)$ e $d_T(a) \le d_T(b)$ e sia $T'$ il trie ottenuto scambiando i caratteri $a$ e $b$. Allora $B(T') \le B(T)$.

Dimostrazione. Dopo lo scambio $a$ sta alla profondità di $b$ e viceversa, e gli altri caratteri non si muovono: $$B(T') - B(T) = f(a) d_T(b) + f(b) d_T(a) - f(a) d_T(a) - f(b) d_T(b) = \big(f(a) - f(b)\big)\big(d_T(b) - d_T(a)\big) \le 0,$$ perché i due fattori sono entrambi $\le 0$. $\square$