L'induzione ordinaria usa solo il caso precedente: da P(k) si ricava P(k + 1). Molti problemi però si scompongono in casi più piccoli che non sono necessariamente «il precedente»: un numero si fattorizza in due numeri qualsiasi più piccoli, un albero si divide in sottoalberi di dimensioni diverse. Per questi casi esistono varianti dell'induzione più flessibili. E la stessa idea, applicata ai cicli di un programma, prende il nome di invariante di ciclo, lo strumento principale per dimostrare che un algoritmo iterativo fa ciò che promette.
Induzione forte
Nell'induzione forte (o completa) il passo induttivo può usare l'ipotesi che la proprietà valga per tutti i valori da n₀ fino a k, non solo per k:
- Caso base: si dimostra P(n₀) (a volte servono più casi base).
- Passo: supponendo P(n₀), P(n₀ + 1), …, P(k), si dimostra P(k + 1).
Esempio: fattorizzazione in primi
Enunciato: ogni intero n ≥ 2 è un numero primo oppure un prodotto di numeri primi.
Caso base: 2 è primo.
Passo: consideriamo k + 1 e supponiamo che l'enunciato valga per tutti gli interi da 2 a k. Se k + 1 è primo, abbiamo finito. Altrimenti k + 1 = a · b con 2 ≤ a, b ≤ k. Per ipotesi induttiva sia a sia b sono prodotti di primi, e quindi lo è anche il loro prodotto.
Esempio: francobolli da 4 e 5
Enunciato: ogni affrancatura di n ≥ 12 centesimi si può comporre con francobolli da 4 e da 5.
Casi base: 12 = 4 + 4 + 4; 13 = 4 + 4 + 5; 14 = 4 + 5 + 5; 15 = 5 + 5 + 5.
Passo: per k + 1 ≥ 16, il valore k + 1 − 4 = k − 3 è almeno 12 e quindi, per ipotesi, componibile. Aggiungendo un francobollo da 4 si ottiene k + 1.
Qui servono quattro casi base, perché il passo «salta indietro» di quattro.
Induzione strutturale
Molti oggetti dell'informatica sono definiti ricorsivamente: liste, alberi, espressioni, formule logiche. L'induzione strutturale dimostra una proprietà per tutti gli oggetti di questo tipo:
- si dimostra la proprietà per gli oggetti di base (la lista vuota, una foglia);
- si dimostra che, se vale per le componenti, vale per l'oggetto costruito a partire da esse.
Esempio: in ogni albero binario in cui ogni nodo interno ha esattamente due figli, il numero di foglie supera di uno quello dei nodi interni. Una singola foglia ha 1 foglia e 0 nodi interni. Un albero costruito da una radice con due sottoalberi, che per ipotesi hanno fᵢ = iᵢ + 1 foglie ciascuno, ha f₁ + f₂ = i₁ + i₂ + 2 foglie e i₁ + i₂ + 1 nodi interni: la differenza è ancora 1.
Invarianti di ciclo
Un invariante di ciclo è una proprietà che vale prima di entrare in un ciclo e che ogni iterazione mantiene. Si dimostra come un'induzione sul numero di iterazioni, in tre parti:
- Inizializzazione: l'invariante vale prima della prima iterazione.
- Mantenimento: se vale all'inizio di un'iterazione, vale anche alla fine.
- Conclusione: quando il ciclo termina, l'invariante unito alla condizione di uscita implica il risultato voluto.
A queste si aggiunge la dimostrazione di terminazione, di solito trovando una quantità intera non negativa che diminuisce strettamente a ogni giro.
Esempio: il massimo di un array
def massimo(a):
m = a[0]
i = 1
while i < len(a):
if a[i] > m:
m = a[i]
i += 1
return m
Invariante: all'inizio di ogni iterazione, m è il massimo di a[0], …, a[i − 1].
- Inizializzazione: con i = 1, m = a[0] è il massimo del solo a[0].
- Mantenimento: se m è il massimo dei primi i elementi, dopo il confronto con a[i] è il massimo dei primi i + 1; poi i aumenta di 1 e l'invariante torna a valere.
- Conclusione: il ciclo termina con i = len(a), quindi m è il massimo di tutto l'array.
- Terminazione: la quantità len(a) − i diminuisce di 1 a ogni giro e non può scendere sotto zero.
Esempio: potenza veloce
def potenza(b, e):
r = 1
while e > 0:
if e % 2 == 1:
r = r * b
b = b * b
e = e // 2
return r
Chiamiamo B ed E i valori iniziali. L'invariante è r · bᵉ = Bᴱ. All'inizio r = 1 e il prodotto vale Bᴱ. Se e è pari, b diventa b² ed e si dimezza: b²⁽ᵉ/²⁾ = bᵉ, invariato. Se e è dispari, r assorbe un fattore b, poi b² elevato a (e − 1)/2 compensa il resto. Alla fine e = 0, quindi r = Bᴱ. Il numero di iterazioni è proporzionale al numero di bit di E, che è il motivo per cui questo algoritmo è alla base dell'esponenziazione modulare in crittografia.
Perché vale la pena
Quando un ciclo non funziona, il difetto è quasi sempre un invariante che si rompe ai bordi: il primo elemento, l'ultimo, l'array vuoto. Scriverlo in un'asserzione costa poco e previene molti errori.
In sintesi
- L'induzione forte usa l'ipotesi su tutti i valori più piccoli, non solo sul precedente.
- Quando il passo salta indietro di più posizioni servono più casi base.
- L'induzione strutturale dimostra proprietà di liste, alberi e formule definiti ricorsivamente.
- Un invariante di ciclo si dimostra con inizializzazione, mantenimento e conclusione, più la terminazione.
- Gli errori nei cicli sono spesso invarianti che si rompono ai bordi.
