Dimostrazioni, induzione e invarianti

Servono per le analisi di complessità e di correttezza (l'algoritmo termina e risolve il problema computazionale, vedi Problemi computazionali e algoritmiProblema computazionale come insieme di coppie (istanza, soluzione); algoritmo e modello di calcolo RAM; pseudocodice; taglia di un'istanza; ADT e struttura dati concreta; esempio svolto con ricerca lineare e binaria in un array ordinato.Problemi computazionali e algoritmi →).

Esempio, controesempio, assurdo

• Esempio: per dimostrare che $t_A(n) \in \Omega(n^2)$ basta mostrare che per ogni $n$ abbastanza grande esiste un'istanza che richiede almeno $c\,n^2$ operazioni (vedi Complessità in tempo e caso pessimoPerché lo studio sperimentale non basta; complessità al caso pessimo come massimo sul numero di operazioni tra le istanze di una data taglia; stima con limiti superiore e inferiore senza trovare l'istanza peggiore; esempi arrayMax, prefixAverages e InsertionSort; efficienza asintotica e limiti dell'analisi.Complessità in tempo e caso pessimo →).
• Controesempio: per confutare "$2^i - 1$ è primo per ogni $i \ge 1$" basta $2^4 - 1 = 15$.
• Assurdo: si nega la tesi e si ottiene una contraddizione. Se $ab$ è dispari, allora $a$ e $b$ sono dispari: se uno fosse pari, ad esempio $a = 2c$, allora $ab = 2cb$ sarebbe pari, contro l'ipotesi.

Induzione

Per provare che $Q(n)$ vale per ogni $n \ge n_0$:

1. si sceglie $k \ge 0$ (di solito $k = 0$);
2. base: si dimostra $Q(n_0), Q(n_0+1), \dots, Q(n_0+k)$;
3. passo: si fissa $n \ge n_0 + k$ arbitrario e, assumendo $Q(m)$ vera per ogni $m$ con $n_0 \le m \le n$ (ipotesi induttiva), si dimostra $Q(n+1)$.

Il passo deve valere per ogni $n \ge n_0 + k$. Servono più casi base quando il passo usa più valori precedenti (Fibonacci usa i due precedenti: $k = 1$).

Esempio 1. $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ per $n \ge 0$. Base $n = 0$: $0 = 0$. Passo: $\sum_{i=0}^{n+1} i = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$. ✓

Esempio 2 (Fibonacci). $F(0) = 0$, $F(1) = 1$, $F(n+1) = F(n) + F(n-1)$. Si prova $F(n) = \frac{1}{\sqrt 5}(\Phi^n - \hat\Phi^n)$ con $\Phi = \frac{1+\sqrt5}{2}$, $\hat\Phi = \frac{1-\sqrt5}{2}$. Base: $n = 0, 1$ (verifica diretta). Passo ($n \ge 1$): $F(n+1) = F(n) + F(n-1) = \frac{1}{\sqrt5}\big[(\Phi^n + \Phi^{n-1}) - (\hat\Phi^n + \hat\Phi^{n-1})\big]$. Si osserva $\Phi^n + \Phi^{n-1} = \Phi^{n-1}(\Phi + 1) = \Phi^{n-1}\Phi^2 = \Phi^{n+1}$, perché $\Phi + 1 = \frac{3+\sqrt5}{2} = \Phi^2$; allo stesso modo per $\hat\Phi$. Quindi $F(n+1) = \frac{1}{\sqrt5}(\Phi^{n+1} - \hat\Phi^{n+1})$. ✓ (Verificato numericamente: $0, 1, 1, 2, 3, 5, 8, 13, 21, 34$.)

Esempio 3. $Q(n)$: $\sum_{i=0}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} \in \Theta(n^3)$. Passo: $\frac{n(n+1)(2n+1)}{6} + (n+1)^2 = \frac{(n+1)\,[\,n(2n+1) + 6(n+1)\,]}{6} = \frac{(n+1)(2n^2 + 7n + 6)}{6} = \frac{(n+1)(n+2)(2n+3)}{6}$. ✓

Correttezza di un algoritmo

Schema generale: si individuano lo stato iniziale e quello finale desiderato, si scompone l'algoritmo in segmenti con uno stato atteso a fine segmento (checkpoint) e si prova che dallo stato iniziale si raggiungono in successione tutti i checkpoint; l'ultimo deve implicare lo stato finale. I segmenti notevoli sono i cicli. La terminazione si prova assicurandosi che cicli e ricorsione abbiano fine.

Invarianti di ciclo

Un invarianteProprietà sulle variabili del ciclo che descrive lo stato a ogni iterazione. è una proprietà delle variabili usate nel ciclo che:

1. vale all'inizio del ciclo, come conseguenza dello stato iniziale (inizializzazione);
2. vale alla fine di ogni iterazione, assumendo che valesse all'inizio di quella iterazione (conservazione);
3. alla fine dell'ultima iterazione, insieme alla condizione di uscita, implica la correttezza del ciclo (uso).

Un ciclo esegue $\ge 0$ iterazioni del corpo; for i <- 1 to n ne fa sempre $n$.

arrayMax. currMax <- A[0]; for i <- 1 to n-1 do currMax <- max(currMax, A[i]). Invariante: alla fine dell'iterazione $i$, $currMax = \max\{A[0], \dots, A[i]\}$. All'inizio ($i$ prima del ciclo) $currMax = A[0]$ = massimo di $A[0..0]$. Conservazione: il massimo di $A[0..i]$ è il massimo tra il massimo di $A[0..i-1]$ e $A[i]$. Alla fine ($i = n-1$) $currMax$ è il massimo di tutto l'array.

Il più lungo segmento di 1 in una sequenza di bit $S[1..n]$:

max <- 0; curr <- 0
for i <- 1 to n do
    if S[i] = 1 then
        curr <- curr + 1
        if curr > max then max <- curr
    else curr <- 0
return max

Invariante alla fine dell'iterazione $i$: (a) $curr$ è la lunghezza del segmento di 1 che termina in $S[i]$ (zero se $S[i] = 0$) e (b) $max$ è la lunghezza massima di un segmento di 1 in $S[1..i]$. Inizio ($i = 0$): sequenza vuota, entrambi $0$. Conservazione: se $S[i] = 1$ il segmento che termina in $i$ estende quello che terminava in $i-1$, quindi $curr$ cresce di 1 e $max$ viene aggiornato se lo supera; se $S[i] = 0$ il segmento si interrompe e $curr = 0$, mentre $max$ non cambia. Fine: per $i = n$ la (b) dà la risposta. (Controllato con un test casuale su sequenze di lunghezza $\le 15$.)

Cicli con due indici (esempio d'esame): in while (i < n) AND (j < m) su una matrice con colonne decrescenti, l'invariante lega il valore corrente a $i$ e $j$; si veda l'esercizio Esercizio 3 · invariante su matrice a colonne decrescenti.

Errori comuni

• Un invariante che vale solo alla fine (non è un invariante): deve valere anche all'inizio e dopo ogni iterazione.
• Un invariante troppo debole: non basta a concludere la correttezza all'uscita (es. "$currMax \in A$" non dice che sia il massimo).
• Nell'induzione: provare il passo solo per un $n$ specifico, o dimenticare uno dei casi base quando il passo usa due valori precedenti.
• Confondere ipotesi induttiva e tesi: nel passo si assume $Q(m)$ per $m \le n$ e si prova $Q(n+1)$.