Esercizio - elemento (h,k) di una matrice supercircolante (esercizi su supercircolanti e circolanti, es. SC 5)

Esercizio supplementare 5 sulle matrici supercircolanti, dalle note ed esercizi del corso di Algoritmi per l'Ingegneria (Ing. Informatica UniPD) su supercircolanti e circolanti. Teoria usata: Matrici circolanti e supercircolanti - algoritmi divide and conquerle matrici supercircolanti (quadranti alternati ricorsivi) hanno solo n valori distinti: somma in n operazioni, prodotto in 4n log2 n + n con il trucco (A1+A2)(B1+B2) e (A1-A2)(B1-B2) invece delle 4 chiamate (Theta(n^2)); gli autovalori sono la trasformata di Hadamard della prima riga (FHT, n log2 n) e il prodotto passa dalla base diagonalizzante; le matrici circolanti sono polinomi nella matrice di rotazione R, il loro prodotto è la convoluzione ciclica delle prime righe e si diagonalizzano con la matrice di Fourier: prodotto in O(n log n) con la FFT.Matrici circolanti e supercircolanti - algoritmi divide and conquer →, Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni → e 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 →.

Testo

Elemento $(h, k)$ di una matrice SC. Si proponga e si analizzi un algoritmo efficiente per determinare il valore dell'elemento $A_{hk}$ (dove $0 \le h, k < n$) di una matrice supercircolante $A$ di ordine $n = 2^p$, a partire dalla prima riga di $A$, vale a dire $[A_{00}, A_{01}, \dots, A_{0,n-1}]$. Ha senso definire $T(n)$ come il numero di operazioni sugli indici, anziché sui valori degli elementi di $A$. Nota: un algoritmo efficiente dovrebbe avere $T(n) = O(\log_2 n)$.

(Una matrice è supercircolante, SC, se $n = 1$ oppure $A = \begin{pmatrix} A_1 & A_2 \\ A_2 & A_1 \end{pmatrix}$ con $A_1, A_2$ SC di ordine $\frac n2$.)

Idea

Una SC è determinata dalla sua prima riga $r = [A_{00}, \dots, A_{0,n-1}]$, ma ha $n^2$ elementi: costruire tutta la matrice costerebbe $\Theta(n^2)$ assegnamenti. Si vuole invece leggere un solo valore della riga. La struttura ricorsiva dice dove: la posizione $(h, k)$ cade in uno dei quattro quadranti, e i quadranti sono solo di due tipi, $A_1$ e $A_2$, le cui prime righe sono le due metà di $r$.

Con indici da $0$ e $m = \frac n2$:

La matrice è $A_1$ quando $h$ e $k$ stanno nella stessa metà ($h < m$ equivale a $k < m$), è $A_2$ altrimenti. Dentro il quadrante la posizione diventa $(h \bmod m, k \bmod m)$. La prima riga di $A_1$ è $r[0..m-1]$ (prima metà di $r$), quella di $A_2$ è $r[m..n-1]$.

Algoritmo ricorsivo

ELEM(r, h, k)                       { r = prima riga, lunghezza n = 2^p }
  n <- length(r)
  if n = 1 then return r[0]
  m <- n / 2
  if (h < m) = (k < m)              { stessa metà: quadrante A1 }
    then return ELEM(r[0..m-1], h mod m, k mod m)
    else return ELEM(r[m..n-1], h mod m, k mod m)    { quadrante A2 }

(Per non copiare i sottovettori $r[0..m-1]$ e $r[m..n-1]$ basta passare un indice di partenza e la lunghezza: nel modello gli assegnamenti non si contano comunque, e la domanda è sulle operazioni sugli indici.)

Correttezza. Per induzione sull'esponente $p$ con $n = 2^p$. Per $n = 1$ la matrice è $[r_0]$ e l'unico elemento è $r_0$. Per $n > 1$, per la definizione di SC, $A_{hk}$ è l'elemento $(h \bmod m, k \bmod m)$ del quadrante in cui cade $(h, k)$; il quadrante è $A_1$ o $A_2$ secondo la tabella, ed è SC di ordine $m$ con prima riga la prima o la seconda metà di $r$; per ipotesi induttiva la chiamata ricorsiva restituisce proprio quell'elemento.

Analisi. Ogni chiamata fa un numero costante $c$ di operazioni sugli indici (due confronti $h < m$, $k < m$, un confronto tra i risultati, due resti: $c = 5$) e una chiamata su taglia $\frac n2$:

$$T(n) = \begin{cases} 0 & n = 1, \\ T\!\left(\frac n2\right) + c & n > 1. \end{cases}$$

Srotolando: $T(2^p) = c \cdot p = c \log_2 n$. Master Theorem (Master Theorem - enunciato, casi e applicazioniMaster Theorem per T(n) = aT(n/b) + w(n): si confronta w(n) con la funzione soglia n^(log_b a). Caso 1 (w minore di una potenza polinomiale): Theta(n^(log_b a)); caso 2 (w della stessa taglia): Theta(n^(log_b a) log n); caso 3 (w maggiore e regolare): Theta(w(n)). Prova completa dai livelli dell'albero, versione estesa (parti intere, n0 qualsiasi), esempi, e l'uso scorretto quando nessun caso si applica (w = n log n).Master Theorem - enunciato, casi e applicazioni →): $a = 1$, $b = 2$, soglia $n^0 = 1$, $w = c = \Theta(1)$, caso 2: $T(n) = \Theta(\log n) = O(\log_2 n)$, come richiesto. Con la convenzione $c = 5$, $T(n) = 5 \log_2 n$.

Esempio ($n = 8$, $r = (a, b, c, d, e, f, g, h)$, elemento $(5, 3)$). $m = 4$: $h = 5 \ge 4$ e $k = 3 < 4$, metà diverse, quadrante $A_2$ con prima riga $(e, f, g, h)$, nuova posizione $(5 \bmod 4, 3 \bmod 4) = (1, 3)$. Con $n = 4$, $m = 2$, $r = (e, f, g, h)$: $h = 1 < 2$ e $k = 3 \ge 2$, metà diverse, $A_2$ con prima riga $(g, h)$, posizione $(1 \bmod 2, 3 \bmod 2) = (1, 1)$. Con $n = 2$, $m = 1$, $r = (g, h)$: $h = 1 \ge 1$ e $k = 1 \ge 1$, stessa metà, $A_1$ con prima riga $(g)$, posizione $(0, 0)$. Con $n = 1$ restituisce $g$. La riga $5$ (la sesta) della SC di ordine $8$ è $(f, e, h, g, b, a, d, c)$, e l'elemento di colonna $3$ è $g$ ✓.

Algoritmo diretto con lo XOR

Guardando i bit di $h$ e $k$ si ottiene un'espressione chiusa.

Proposizione. $A_{hk} = r_{h \oplus k}$, dove $\oplus$ è lo XOR bit a bit.

Dimostrazione per induzione su $p$. Base $n = 1$: $h = k = 0$, $r_{0 \oplus 0} = r_0$ ✓. Passo: con $m = \frac n2 = 2^{p-1}$, il bit più significativo (peso $m$) di $h$ e di $k$ dice in quale metà cadono, e $h = h_t m + h'$, $k = k_t m + k'$ con $h_t, k_t \in \{0, 1\}$, $h' = h \bmod m$, $k' = k \bmod m$.

• Se $h_t = k_t$ (stessa metà), il quadrante è $A_1$ con prima riga $r[0..m-1]$: per ipotesi $A_{hk} = r_{h' \oplus k'}$; e $h \oplus k = h' \oplus k'$ perché i bit di peso $m$ si annullano ($h_t \oplus k_t = 0$).
• Se $h_t \ne k_t$ (metà diverse), il quadrante è $A_2$ con prima riga $r[m..n-1]$, cioè $r'_j = r_{m + j}$: per ipotesi $A_{hk} = r'_{h' \oplus k'} = r_{m + (h' \oplus k')}$; e $h \oplus k = m + (h' \oplus k')$ perché il bit di peso $m$ dello XOR vale $1$. $\blacksquare$

L'algoritmo è return r[h XOR k]: un'operazione sugli indici (nel modello in cui lo XOR di interi di $\log_2 n$ bit costa $O(1)$; se si contano le operazioni sui singoli bit, sono $\log_2 n$, lo stesso ordine di grandezza dell'algoritmo ricorsivo). Per $n = 8$, $(h, k) = (5, 3)$: $5 = 101_2$, $3 = 011_2$, $5 \oplus 3 = 110_2 = 6$ e $r_6 = g$ ✓. Le righe sono permutazioni della prima perché $k \mapsto h \oplus k$ è una permutazione di $\{0, \dots, n-1\}$ (è un'involuzione); la simmetria $A_{hk} = A_{kh}$ segue da $h \oplus k = k \oplus h$.

Confronto con le circolanti. Per una matrice circolante ($A_{hk} = r_{(k-h) \bmod n}$) l'elemento si calcola con una sottrazione e un resto, per ogni $n$ (anche non potenza di $2$).

Verifica con un programma. Costruita la matrice SC piena per $n = 1, 2, 4, \dots, 64$ da una prima riga casuale, per tutte le coppie $(h, k)$ il valore $A_{hk}$ coincide con ELEM$(r, h, k)$ e con $r_{h \oplus k}$.