Esercizio - domande di prima parte su moltiplicazione di matrici (simulazioni d'esame)

Domande della prima parte (risposta unica o scelta multipla, senza procedimento) delle simulazioni d'esame di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, sull'argomento moltiplicazione di matrici. Teoria: 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 →, Algoritmo di Strassen e ibridazioneStrassen calcola il prodotto n x n con 7 chiamate ricorsive invece di 8, usando 10 somme/sottrazioni nel divide e 8 nel conquer: T(n) = 7T(n/2) + (9/2)n^2, Theta(n^(log2 7)) con soluzione esatta 7n^(log2 7) - 6n^2; la costante 7 è più che tripla di quella dell'iterativo (2) e Strassen batte l'iterativo solo da n = 655 (per le potenze di 2, da 1024). L'ibridazione cambia il caso base (iterativo per n <= n0): costo n^(log2 7)(2n0+5)/n0^(log2 7 - 2) - 6n^2, minimo per n0 = 8 con costante ~3.92.Algoritmo di Strassen e ibridazione →, 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 → e Esponenziazione veloce per quadrature successivepotenza x^n con un operatore associativo con elemento neutro, costo = numero di applicazioni dell'operatore; STUPID_POWER costa n-1, la sottostruttura x^n = (x^floor(n/2))^2 (per n dispari per x) dà POWER con T(n) = floor(log2 n) + (numero di bit a 1 di n) - 1, Theta(log n) (caso peggiore 2 floor(log2 n), n = 2^t - 1); versioni iterative POWER2 e POWER3 dalla rappresentazione binaria di n; esempio con la matrice di Fibonacci; il modello a costo unitario vale solo se l'operatore non fa crescere gli operandi.Esponenziazione veloce per quadrature successive →.

Nelle simulazioni (2023-24 e 2025-26) la prima parte ha dieci domande; una sola riguarda questo argomento. Le altre sono su problemi computazionali, ricorrenze e conteggi, DFT, programmazione dinamica e greedy, e si trovano nelle pagine degli altri argomenti. Dopo la domanda originale ci sono domande di allenamento nello stesso stile sui temi di questa parte (non sono testi d'esame), con risposta e procedimento controllati con un programma che conta le operazioni.

Domanda della simulazione d'esame

Domanda. Si determini il numero $T_m(n)$ di operazioni tra scalari effettuato dall'algoritmo di prodotto righe per colonne ricorsivo basato sulla definizione per moltiplicare due matrici quadrate $n \times n$, quando $n = 8$.

Risposta: $960$.

Procedimento. L'algoritmo basato sulla definizione esegue:

• $n^3$ prodotti $a_{ik}b_{kj}$, per $1 \le i, j, k \le n$;
• $n^3 - n^2$ somme: ogni prodotto va sommato in $c_{ij}$, tranne i prodotti $a_{i1}b_{1j}$ (uno per ogni coppia $(i, j)$, quindi $n^2$).

Il totale è $T_m(n) = 2n^3 - n^2$, e per $n = 8$: $2 \cdot 512 - 64 = 960$. L'algoritmo ricorsivo a blocchi (ricorrenza $T(n) = 8T(\frac n2) + n^2$, $T(1) = 1$) ha la stessa soluzione esatta, perché fa le stesse operazioni in ordine diverso (vedi 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 →). Controllo con la ricorrenza: $T(2) = 8 + 4 = 12$, $T(4) = 8 \cdot 12 + 16 = 112$, $T(8) = 8 \cdot 112 + 64 = 960$ ✓.

Domande di allenamento nello stesso stile

1. Numero di operazioni tra scalari del prodotto ricorsivo basato sulla definizione per $n = 16$. Risposta: $7936$. Procedimento: $2 \cdot 16^3 - 16^2 = 8192 - 256 = 7936$; con la ricorrenza $T(16) = 8 \cdot 960 + 256 = 7936$.

2. Quante chiamate ricorsive su matrici $\frac n2 \times \frac n2$ e quante somme/sottrazioni di matrici $\frac n2 \times \frac n2$ (divide più conquer) esegue l'algoritmo di Strassen per $n > 1$? Risposta: $7$ chiamate e $18$ somme/sottrazioni ($10$ nel divide, $8$ nel conquer). Il lavoro dei nodi interni è $18 \cdot \frac{n^2}{4} = \frac 92 n^2$.

3. Numero di operazioni tra scalari dell'algoritmo di Strassen puro (caso base $n = 1$) per $n = 4$. Risposta: $247$. Procedimento: $T(1) = 1$; $T(2) = 7 \cdot 1 + \frac 92 \cdot 4 = 25$; $T(4) = 7 \cdot 25 + \frac 92 \cdot 16 = 175 + 72 = 247$. Con la formula chiusa $7n^{\log_2 7} - 6n^2 = 7 \cdot 49 - 6 \cdot 16 = 247$ ✓.

4. Scegli un'alternativa. Qual è il primo $n$ (potenza di $2$) per cui Strassen puro esegue meno operazioni dell'algoritmo iterativo?

• $\bigcirc$ $n = 16$
• $\bigcirc$ $n = 128$
• $\bigcirc$ $n = 512$
• $\bigcirc$ $n = 1024$

Risposta: $n = 1024$. Procedimento: la disuguaglianza $7n^{\log_2 7} - 6n^2 < 2n^3 - n^2$ vale da $n \approx 655$; per $n = 512$ Strassen fa $280\,902\,385$ operazioni contro $268\,173\,312$ dell'iterativo (perde), per $n = 1024$ fa $1\,971\,035\,287$ contro $2\,146\,435\,072$.

5. Con la versione ibrida dell'algoritmo di Strassen (caso base: iterativo per $n \le n_0$) e $n_0 = 8$, quante operazioni si eseguono per $n = 16$? Risposta: $7872$. Procedimento: $T(16, 8) = 7\,T(8, 8) + \frac 92 \cdot 16^2 = 7 \cdot 960 + 1152 = 7872$, dove $T(8, 8) = 2 \cdot 8^3 - 8^2 = 960$ è il costo dell'iterativo. (Meno dell'iterativo puro, $7936$.)

6. Qual è il valore intero $n_0$ potenza di $2$ che minimizza la costante $g(n_0) = \dfrac{2n_0 + 5}{n_0^{\log_2 7 - 2}}$ del termine dominante dell'algoritmo ibrido, e quanto vale (due cifre decimali)? Risposta: $n_0 = 8$, $g(8) \approx 3.92$. Procedimento: $g$ decresce fino a $n_0 \approx 10.48$ e poi cresce; tra le potenze di $2$ si confrontano $g(8) \approx 3.918$ e $g(16) \approx 3.945$.

7. Quante somme servono (modello a costo unitario per le operazioni tra scalari, assegnamenti gratuiti) per sommare due matrici supercircolanti di ordine $16$ con l'algoritmo specializzato? Risposta: $16$. Procedimento: $T(1) = 1$, $T(n) = 2T(\frac n2)$, quindi $T(n) = n$ (una per elemento della prima riga).

8. Numero di operazioni dell'algoritmo di prodotto di matrici supercircolanti con le due chiamate $U = (A_1 + A_2)(B_1 + B_2)$, $V = (A_1 - A_2)(B_1 - B_2)$ per $n = 8$ (con $T(n) = 2T(\frac n2) + 4n$, $T(1) = 1$). Risposta: $104$. Procedimento: $T(2) = 2 \cdot 1 + 8 = 10$, $T(4) = 2 \cdot 10 + 16 = 36$, $T(8) = 2 \cdot 36 + 32 = 104$; formula $4n\log_2 n + n = 4 \cdot 8 \cdot 3 + 8 = 104$ ✓.

9. Numero di applicazioni di $\circ$ eseguite dall'algoritmo ricorsivo di esponenziazione per quadrature successive POWER$(x, n)$ con $n = 100$. Risposta: $8$. Procedimento: $100 \to 50 \to 25 \to 12 \to 6 \to 3 \to 1$: gli esponenti dispari sono $25$ e $3$ (costano $2$), gli esponenti pari $100, 50, 12, 6$ costano $1$: $4 \cdot 1 + 2 \cdot 2 = 8$. Con la formula $\lfloor \log_2 100 \rfloor + \nu(100) - 1 = 6 + 3 - 1 = 8$ ($100 = 1100100_2$).

10. Complessità, in funzione di $n$, di POWER$(x, n)$ nel modello a costo unitario per ogni applicazione di $\circ$. Risposta: $\Theta(\log n)$, dalla ricorrenza $T(n) \le T(\lfloor \frac n2 \rfloor) + 2$, soglia $n^0 = 1$, caso 2 del Master Theorem. STUPID_POWER, basato sulla definizione, ne esegue $n - 1$, $\Theta(n)$.