Esercizio 3invariante su matrice a colonne decrescenti

i <- 0; j <- 0
while (i < n) AND (j < m) do {
    if (A[i,j] <= 0) then j <- j + 1
    else i <- i + 1
}
return i

---

Richiami

Un invariante di ciclo vale prima del ciclo, si conserva a ogni iterazione e a fine ciclo implica la tesi (vedi Dimostrazioni, induzione e invariantiTecniche di dimostrazione (esempio, controesempio, assurdo), induzione con casi base multipli, invarianti di ciclo (inizializzazione, conservazione, uso alla fine), schema generale per provare la correttezza; esempi svolti su arrayMax, sequenza di bit e numeri di Fibonacci.Dimostrazioni, induzione e invarianti →).

Cosa fa l'algoritmo

Sia $c(j)$ il numero di valori positivi della colonna $j$. Poiché la colonna è decrescente, i valori positivi sono i primi $c(j)$ della colonna (dalla riga $0$): se $A[i, j] \le 0$ allora tutti i valori delle righe $i, i+1, \dots$ sono $\le 0$, e se $A[i, j] > 0$ allora lo sono tutti quelli delle righe $0, \dots, i$. Si cerca $M = \max_j c(j)$.

L'algoritmo percorre la matrice a "scala": se $A[i, j] \le 0$ la colonna $j$ ha al più $i$ valori positivi, quindi non può battere il valore $i$ già raggiunto e si passa alla colonna $j+1$; se $A[i, j] > 0$ la colonna $j$ ha almeno $i + 1$ valori positivi e si prova ad arrivare a $i + 1$.

Invariante

All'inizio di ogni iterazione (e quindi a ogni controllo della condizione del while):

$$\textbf{(a)}\ \ c(j') \le i \ \text{ per ogni colonna } j' < j; \qquad \textbf{(b)}\ \ \max_{j'} c(j') \ge i.$$

La (a) dice che le colonne già scartate non hanno più di $i$ valori positivi; la (b) che almeno una colonna ne ha $i$ o più (in particolare il valore $i$ è raggiungibile).

Verifica (pur senza richiedere la prova)

• Inizio: $i = j = 0$; la (a) è vuota e la (b) è $M \ge 0$.
• Conservazione. Se $A[i, j] \le 0$ si incrementa $j$: la colonna $j$ ha $c(j) \le i$, quindi la (a) vale anche per $j + 1$ ($i$ non cambia, quindi la (b) resta vera). Se $A[i, j] > 0$ si incrementa $i$: la colonna $j$ ha $c(j) \ge i + 1$, quindi $M \ge i + 1$ e la (b) vale con il nuovo $i$; la (a) resta vera perché $c(j') \le i < i + 1$.
• Uscita: si esce con $i = n$ o con $j = m$. Se $i = n$, dalla (b) $M \ge n$ e poiché $M \le n$ si ha $M = n = i$. Se $j = m$, dalla (a) ogni colonna ha $c \le i$ e dalla (b) $M \ge i$, quindi $M = i$. In entrambi i casi $i = M$, ed è ciò che restituisce l'algoritmo.
• Terminazione: a ogni iterazione cresce $i$ o $j$, e $i + j$ è limitato da $n + m$; le iterazioni sono al più $n + m$, quindi la complessità è $\Theta(n + m)$ (una colonna alla volta e una riga alla volta, mai all'indietro).

Esempio

$n = 3$, $m = 3$, colonne decrescenti:

$$A = \begin{pmatrix} 5 & 2 & -1 \\ 3 & 0 & -2 \\ -1 & -4 & -5 \end{pmatrix}, \qquad c = (2, 1, 0), \ M = 2.$$

Traccia $(i, j)$: $(0, 0)$ con $A[0,0] = 5 > 0$ $\to (1, 0)$; $A[1,0] = 3 > 0 \to (2, 0)$; $A[2,0] = -1 \le 0 \to (2, 1)$; $A[2,1] = -4 \le 0 \to (2, 2)$; $A[2,2] = -5 \le 0 \to (2, 3)$; $j = m$: esce e restituisce $2$. Ad ogni passo valgono (a) e (b): ad esempio a $(2, 1)$ la colonna $0$ ha $c(0) = 2 \le 2$ e $M = 2 \ge 2$. (L'invariante è stato controllato con $3000$ matrici casuali.)

Errori comuni

• Un invariante tipo "$i$ è il numero di positivi nella colonna $j$": falso, non c'è una colonna fissata.
• Dimenticare la parte (b), cioè che il valore $i$ è effettivamente raggiunto da qualche colonna: senza di essa dall'uscita con $j = m$ si dedurrebbe solo $M \le i$.
• Dimenticare l'ipotesi di decrescenza: senza di essa $A[i, j] \le 0$ non dice nulla sulle righe sotto.