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 →). Le tecniche sono quelle di Analisi 1 (Tecniche di dimostrazioneDimostrazione diretta, per contronominale e per assurdo di un teorema del tipo ipotesi implica tesi.Tecniche di dimostrazione →, Principio di induzionePer dimostrare una proprietà per ogni n basta il passo base e il passo induttivo da n a n+1.Principio di induzione →, Logica e quantificatoriProposizioni, connettivi, predicati e quantificatori (per ogni, esiste), con le regole per negarli.Logica e quantificatori →): qui si applicano agli algoritmi. In particolare gli enunciati "per ogni $n$ abbastanza grande" e "esiste un'istanza" delle analisi di complessità sono quantificatori $\forall$ ed $\exists$, e il modo di provarli è diverso: un $\forall$ richiede una dimostrazione valida per ogni caso, un $\exists$ si prova esibendo un caso.

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$" (un enunciato $\forall$) basta un solo caso in cui è falso: $2^4 - 1 = 15 = 3 \cdot 5$. I casi $i=2,3$ ($3$ e $7$) non lo smentiscono, ma non lo dimostrano nemmeno: verificare esempi non è una dimostrazione.
• 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$ (un numero è pari se è multiplo di $2$), allora $ab = 2cb = 2(cb)$ sarebbe pari, contro l'ipotesi che $ab$ sia dispari. La contraddizione dice che la negazione della tesi era impossibile.

Induzione

Teorema (principio di 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$ (sommatorie: SommatorieIl simbolo di sommatoria, le sue proprietà (linearità, additività, cambio di indice) e le somme notevoli di Gauss e geometrica.Sommatorie →). Base $n = 0$: a sinistra c'è la somma del solo termine $i=0$, cioè $0$; a destra $\frac{0\cdot1}{2}=0$. Passo: si suppone vera la formula per $n$ e si scrive la somma fino a $n+1$ isolando l'ultimo termine, $$\sum_{i=0}^{n+1} i = \underbrace{\sum_{i=0}^{n} i}_{\text{ipotesi induttiva}} + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2},$$ dove si è messo a denominatore comune $2$ e raccolto $(n+1)$. L'ultimo membro è proprio la formula con $n+1$ al posto di $n$. ✓

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): per $n=0$, $\frac{1}{\sqrt5}(\Phi^0-\hat\Phi^0)=\frac{1-1}{\sqrt5}=0=F(0)$; per $n=1$, $\Phi-\hat\Phi=\frac{1+\sqrt5}{2}-\frac{1-\sqrt5}{2}=\sqrt5$, e $\frac{\sqrt5}{\sqrt5}=1=F(1)$. Servono due casi base perché il passo usa i due valori precedenti $F(n)$ ed $F(n-1)$. 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$: infatti $\Phi^2 = \frac{(1+\sqrt5)^2}{4} = \frac{1 + 2\sqrt5 + 5}{4} = \frac{6+2\sqrt5}{4} = \frac{3+\sqrt5}{2}$. Allo stesso modo per $\hat\Phi$: $\hat\Phi + 1 = \frac{3-\sqrt5}{2} = \hat\Phi^2$ (i due numeri sono le radici di $x^2 = x + 1$). 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)$. Base $n=0$: $0=0$. Passo (si somma $(n+1)^2$ a entrambi i membri dell'ipotesi, poi si raccoglie $(n+1)$, che compare in entrambi i termini): $\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}$, dove l'ultimo passo è la scomposizione $2n^2+7n+6=(n+2)(2n+3)$ (verifica: $(n+2)(2n+3)=2n^2+3n+4n+6$). Il risultato è la formula con $n+1$ al posto di $n$, perché $2(n+1)+1=2n+3$. ✓

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

Definizione (invariante 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).

Esempio. In arrayMax l'invariante «alla fine dell'iterazione $i$, $currMax=\max\{A[0],\dots,A[i]\}$» vale all'inizio ($currMax=A[0]$), si conserva a ogni passo e a fine ciclo ($i=n-1$) dà il massimo dell'intero array.

Un ciclo esegue $\ge 0$ iterazioni del corpo; for i <- 1 to n ne fa sempre $n$. Il legame con l'induzione è stretto: "vale all'inizio" è il caso base, "si conserva a ogni iterazione" è il passo induttivo, e le iterazioni successive sono il $n$ che cresce di $1$.

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. Traccia su $A=[3,7,2,9,4]$:

Le due colonne finali coincidono a ogni riga: è ciò che afferma l'invariante.

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$.) Traccia su $S=[1,1,0,1,1,1,0]$:

Alla fine $max=3$, la lunghezza del segmento $S[4..6]$.

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)$.