Esercizio - matrici RCA, somma e prodotto matrice-vettore (compito del 18 giugno 2026, es. 1)

Compito d'esame di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 18 giugno 2026, seconda parte, esercizio 1 (17 punti). 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 → (stessa tecnica delle supercircolanti), Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchimodello di costo sulle matrici n x n (operazioni tra scalari, taglia n oppure N = n^2); somma in n^2 operazioni (ottima); prodotto righe per colonne iterativo con costo esatto 2n^3 - n^2; proprietà frattale del prodotto a blocchi dimostrata sugli indici; algoritmo ricorsivo RMUL con T(n) = 8T(n/2) + n^2, Theta(n^3) e soluzione esatta 2n^3 - n^2 per induzione e per srotolamento: fa le stesse operazioni dell'iterativo.Prodotto di matrici - algoritmo iterativo e ricorsivo a blocchi →, 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 → e Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →.*

Testo

Sia $n \ge 1$ una potenza di due. Una matrice $T \in \mathbb R^{n \times n}$ si dice Ricorsivamente Centralmente Antisimmetrica di ordine $n$ ($n$-RCA, in breve) se $n = 1$, oppure, per $n > 1$,

$$T = \begin{pmatrix} A & B \\ -B & -A \end{pmatrix},$$

con $A, B$ matrici $\frac n2$-RCA.

• 1.(a) [4 punti] Si dimostri che, se $T$ e $V$ sono $n$-RCA, allora $T + V$ e $T - V$ sono $n$-RCA.
• 1.(b) [6 punti] Date due matrici $n$-RCA $T$ e $V$, si descrivano (senza necessariamente fornire lo pseudocodice) e si analizzino algoritmi ricorsivi RCA_SUM$(T, V)$ e RCA_SUB$(T, V)$ che restituiscano, rispettivamente, $T + V$ e $T - V$. Si esprima la complessità di tali algoritmi in funzione del numero di operazioni aritmetiche tra scalari reali eseguite. (Attenzione: dato lo scalare $x$, si assuma che il calcolo dello scalare $-x$ abbia costo nullo.)
• 1.(c) [7 punti] Si scriva e si analizzi lo pseudocodice di un algoritmo ricorsivo RCA_MV_MUL$(T, x)$ che, data una matrice $n$-RCA $T$ e un vettore $x \in \mathbb R^n$, calcoli il prodotto matrice-vettore $Tx$. (Suggerimento: un algoritmo efficiente deve utilizzare opportune, semplici combinazioni lineari dei quadranti di $T$ e dei due sottovettori $u, v \in \mathbb R^{n/2}$ tali che $x = \binom{u}{v}$.)

Attenzione: per ottenere punteggio pieno, ciascuno dei tre algoritmi deve eseguire $o(n^2)$ operazioni tra scalari reali.

Come si legge la struttura

Una $n$-RCA ha $n^2$ elementi ma solo $n$ valori indipendenti: i quadranti in basso sono determinati da quelli in alto ($-B$ e $-A$), e ricorsivamente $A$ e $B$ hanno $\frac n2$ valori indipendenti ciascuna. Per $n = 2$:

$$T = \begin{pmatrix} a & b \\ -b & -a \end{pmatrix}, \qquad n = 4: \quad T = \begin{pmatrix} a & b & c & d \\ -b & -a & -d & -c \\ -c & -d & -a & -b \\ d & c & b & a \end{pmatrix}$$

con $A = \begin{pmatrix} a & b \\ -b & -a \end{pmatrix}$ e $B = \begin{pmatrix} c & d \\ -d & -c \end{pmatrix}$, $-B$ in basso a sinistra e $-A$ in basso a destra. La prima riga $(a, b, c, d)$ determina tutta la matrice. L'idea è la stessa delle supercircolanti: lavorare solo sui due quadranti in alto e ottenere gli altri con un cambio di segno, che qui costa $0$.

Punto (a): chiusura per somma e differenza

Induzione su $k \ge 0$ con $n = 2^k$ (l'induzione vera è su $k$; 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 →).

• Base ($n = 1$): ogni matrice $1 \times 1$ è $1$-RCA per definizione, e somma e differenza di due scalari sono scalari.
• Ipotesi: somma e differenza di due matrici $\frac n2$-RCA sono $\frac n2$-RCA.
• Passo: siano $T$ e $V$ $n$-RCA, con $n > 1$,

$$T = \begin{pmatrix} A & B \\ -B & -A \end{pmatrix}, \qquad V = \begin{pmatrix} C & D \\ -D & -C \end{pmatrix}, \quad A, B, C, D \;\; \tfrac n2\text{-RCA}.$$

Si somma o sottrae quadrante per quadrante (la somma di matrici ha la proprietà frattale: si può fare per blocchi). Con il segno $\pm$ preso uguale in tutti i quadranti:

$$T \pm V = \begin{pmatrix} A \pm C & B \pm D \\ -B \mp D & -A \mp C \end{pmatrix} = \begin{pmatrix} A \pm C & B \pm D \\ -(B \pm D) & -(A \pm C) \end{pmatrix}.$$

Il secondo passaggio raccoglie il segno meno: $-B \mp D = -(B \pm D)$ e $-A \mp C = -(A \pm C)$. Il quadrante in alto a sinistra $A \pm C$ è l'opposto di quello in basso a destra, e quello in alto a destra $B \pm D$ è l'opposto di quello in basso a sinistra, come richiede la definizione. Inoltre $A \pm C$ e $B \pm D$ sono somme o differenze di matrici $\frac n2$-RCA, quindi per ipotesi sono $\frac n2$-RCA. Allora $T \pm V$ ha la forma $\begin{pmatrix} A' & B' \\ -B' & -A' \end{pmatrix}$ con $A', B'$ $\frac n2$-RCA: è $n$-RCA. $\blacksquare$

Osservazione. La stessa cosa non vale per il prodotto: per $n = 2$, $T = \begin{pmatrix} 1 & 2 \\ -2 & -1 \end{pmatrix}$ e $V = \begin{pmatrix} 3 & 4 \\ -4 & -3 \end{pmatrix}$ danno $TV = \begin{pmatrix} -5 & -2 \\ -2 & -5 \end{pmatrix}$, che non è RCA (la diagonale principale non è l'opposto dell'antidiagonale). Per questo l'esercizio chiede solo somma, differenza e prodotto matrice-vettore.

Punto (b): RCA_SUM e RCA_SUB

Dal punto (a): i due quadranti in alto di $T \pm V$ sono $A \pm C$ e $B \pm D$, e gli altri due sono i loro opposti.

• Base $n = 1$: una sola operazione (una somma o una sottrazione tra scalari).

• Caso $n > 1$: due chiamate ricorsive su matrici $\frac n2$-RCA per i quadranti in alto,

  • RCA_SUM: $A + C$ e $B + D$;
  • RCA_SUB: $A - C$ e $B - D$.

  I quadranti in basso si ottengono scambiando i quadranti in alto e cambiando il segno di ogni elemento: costo nullo per l'ipotesi del testo. Il lavoro dei nodi interni è quindi $0$.

Ricorrenza (la stessa per le due procedure):

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

Srotolando: $T(n) = 2T(\frac n2) = 4T(\frac n4) = \dots = 2^k T(1) = n$ (con $n = 2^k$). La formula generale (Albero della ricorrenza e formula generale per le ricorrenzeL'albero della ricorrenza ha la forma dell'albero delle chiamate dell'istanza peggiore e T(n) è la somma dei lavori dei nodi. Per la famiglia T(n) = s(n)T(f(n)) + w(n) con base T0 per n <= n0, contando i nodi per livello con le iterate di f e il livello f*(n,n0) si ottiene la formula chiusa T(n) = somma_l [prodotto_j s(f^(j)(n))] w(f^(l)(n)) + [prodotto s] T0, verificata per induzione e applicata a esempi (merge sort, Hanoi, ricorrenze con radice).Albero della ricorrenza e formula generale per le ricorrenze →) dà lo stesso risultato: $s = 2$, $w = 0$, restano solo le $2^k = n$ foglie da costo $1$. Quindi

$$T_{RCA\_SUM}(n) = T_{RCA\_SUB}(n) = n = o(n^2).$$

È il minimo possibile: le matrici hanno $n$ valori indipendenti e ognuno del risultato richiede la propria somma. (Se invece si usassero le matrici dense, sarebbero $n^2$ somme.)

Punto (c): RCA_MV_MUL

Caso base $n = 1$: $T = [t_{11}]$ e $Tx = [t_{11} x_1]$, una moltiplicazione.

Passo. Per $n > 1$ si scrivono

$$T = \begin{pmatrix} A & B \\ -B & -A \end{pmatrix}, \qquad x = \begin{pmatrix} u \\ v \end{pmatrix}, \; u, v \in \mathbb R^{n/2}, \qquad Tx = \begin{pmatrix} Au + Bv \\ -Bu - Av \end{pmatrix}.$$

La definizione porterebbe a $4$ prodotti matrice-vettore su taglia $\frac n2$ ($Au, Bv, Bu, Av$) e quindi $T(n) = 4T(\frac n2) + \Theta(n)$, cioè $\Theta(n^2)$: non basta. Il suggerimento propone le combinazioni lineari dei quadranti e dei sottovettori:

$$X = A + B, \quad W = A - B, \qquad r = u + v, \quad s = u - v,$$

dove $X$ e $W$ sono $\frac n2$-RCA per il punto (a). Due soli prodotti ricorsivi:

$$y = Xr = (A + B)(u + v) = Au + Av + Bu + Bv,$$ $$z = Ws = (A - B)(u - v) = Au - Av - Bu + Bv.$$

Si sommano e si sottraggono (i termini misti $Av + Bu$ cambiano segno, gli altri no):

$$y + z = 2(Au + Bv), \qquad z - y = -2(Av + Bu).$$

Quindi

$$Tx = \begin{pmatrix} Au + Bv \\ -Bu - Av \end{pmatrix} = \begin{pmatrix} \frac 12 (y + z) \\ \frac 12 (z - y) \end{pmatrix}.$$

Questa è la proprietà di sottostruttura: un prodotto matrice-vettore di taglia $n$ si riduce a due di taglia $\frac n2$ (entrambe su matrici RCA e vettori di $\mathbb R^{n/2}$), più combinazioni lineari.

RCA_MV_MUL(T, x)
  n <- T.rows
  if n = 1 then return (t11 * x1)
  * T = [A B; -B -A],  x = [u; v] *
  X <- RCA_SUM(A, B)                     { n/2 operazioni }
  W <- RCA_SUB(A, B)                     { n/2 operazioni }
  for i <- 1 to n/2 do
    r[i] <- u[i] + v[i]                  { n/2 operazioni }
    s[i] <- u[i] - v[i]                  { n/2 operazioni }
  y <- RCA_MV_MUL(X, r)
  z <- RCA_MV_MUL(W, s)
  for i <- 1 to n/2 do
    m[i]       <- (y[i] + z[i]) / 2      { 2 operazioni }
    m[i + n/2] <- (z[i] - y[i]) / 2      { 2 operazioni }
  return m

Correttezza: per induzione su $k$. Per $n = 1$ è immediata. Per $n > 1$, $X$ e $W$ sono $\frac n2$-RCA (punto (a)) e il costo $0$ del cambio di segno permette di tenere implicite le metà in basso; $r, s \in \mathbb R^{n/2}$; per ipotesi induttiva le chiamate restituiscono $y = Xr$ e $z = Ws$; l'identità sopra mostra che $m = Tx$.

Analisi. Lavoro dei nodi interni, in numero di operazioni tra scalari reali:

La ricorrenza è

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

Soluzione esatta con la formula generale: $s = 2$, $f(n) = \frac n2$, $w(n) = 4n$, $n_0 = 1$, $T_0 = 1$, $k = \log_2 n$ livelli interni. Al livello $\ell$ ci sono $2^\ell$ nodi su taglia $\frac{n}{2^\ell}$, ciascuno con lavoro $4 \frac{n}{2^\ell}$: ogni livello costa $4n$. Le foglie sono $2^k = n$ da costo $1$:

$$T(n) = \sum_{\ell=0}^{k-1} 2^\ell \cdot 4\,\frac{n}{2^\ell} + 2^k \cdot 1 = 4nk + n = 4n \log_2 n + n = \Theta(n \log n) = o(n^2).$$

Per il 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 = 2$, $b = 2$, soglia $n$, $w = 4n = \Theta(n)$: caso 2, $\Theta(n \log n)$.

Esempio ($n = 2$). $T = \begin{pmatrix} 1 & 2 \\ -2 & -1 \end{pmatrix}$ e $x = \binom{3}{5}$: $Tx = \binom{3 + 10}{-6 - 5} = \binom{13}{-11}$. Con l'algoritmo: $A = [1]$, $B = [2]$, $u = [3]$, $v = [5]$; $X = 3$, $W = -1$; $r = 8$, $s = -2$; $y = 24$, $z = 2$; $m = \bigl(\frac{24 + 2}{2}, \frac{2 - 24}{2}\bigr) = (13, -11)$. Le operazioni sono $4 \cdot 2 \cdot 1 + 2 = 10$: $X, W$ ($2$), $r, s$ ($2$), $y, z$ ($2$ moltiplicazioni), $m$ ($4$).

Verifica con un programma. Un'implementazione di RCA_SUM e RCA_MV_MUL che conta le operazioni e confronta il risultato con $Tx$ calcolato dalla matrice piena, per $n = 1, 2, \dots, 256$, dà conteggi uguali a $n$ e a $4n \log_2 n + n$. La soluzione del corso riporta $T(n) = 4n \log_2 n + n$, lo stesso valore.