Esercizio - prodotto di matrici complesse, ricorrenza e induzione parametrica (compito del 8 luglio 2024, es. 1)

Compito d'esame di Algoritmi per l'Ingegneria, Ing. Informatica UniPD, 8 luglio 2024, seconda parte, esercizio 1 (16 punti). Teoria usata: 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 →, Induzione parametrica - limitazioni esatte delle ricorrenzeL'induzione parametrica prova una limitazione T(n) <= cn+d (o >=) con costanti c e d incognite: si simula la verifica per induzione, si raccolgono i vincoli su c e d dalla base e dal passo HP => TH, e se l'intersezione non è vuota si sceglie la coppia migliore. Per MAX dà esattamente T(n) = n-1; può fallire anche con guess veri (si aggiunge un parametro o un termine di ordine inferiore).Induzione parametrica - limitazioni esatte delle ricorrenze →, 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 Numeri complessiI numeri complessi estendono i reali introducendo l'unità immaginaria $i$ ($i^2 = -1$) e possono essere rappresentati in forma algebrica, trigonometrica o polare. Tramite la formula di Eulero e le proprietà del modulo e dell'argomento, è possibile calcolare agilmente prodotti, potenze e radici ennesime.Numeri complessi →.

Testo

Sia $n \ge 1$ una potenza di due. Con riferimento all'algoritmo ricorsivo elementare per moltiplicare due matrici $n \times n$ ad elementi complessi rappresentati in forma cartesiana ($z = a + ib$), si vuole determinare il numero esatto $T(n)$ di operazioni tra numeri reali effettuato dall'algoritmo. Si ricorda che un'addizione complessa richiede $2$ addizioni reali, mentre una moltiplicazione complessa richiede $4$ moltiplicazioni e $2$ addizioni reali.

• 1.(a) [5 punti] Si scriva l'equazione di ricorrenza per $T(n)$ (non è necessario fornire lo pseudocodice).
• 1.(b) [8 punti] Si risolva l'equazione di ricorrenza scritta al punto precedente mediante induzione parametrica, ipotizzando che la soluzione sia un polinomio di terzo grado, $T(n) = an^3 + bn^2 + cn + d$.
• 1.(c) [3 punti] Si determini il numero $T_{MUL}(n)$ delle sole moltiplicazioni reali. Si scelga il metodo che viene più comodo, ma si giustifichi bene la risposta.

Punto (a): la ricorrenza

L'algoritmo ricorsivo elementare è RMUL (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 →): per $n = 1$ un prodotto tra scalari complessi; per $n > 1$ otto chiamate su matrici $\frac n2 \times \frac n2$ e quattro somme di matrici complesse $\frac n2 \times \frac n2$ (i quadranti $C_{ij} = A_{i1}B_{1j} + A_{i2}B_{2j}$).

Conteggio in operazioni reali:

• Caso base $n = 1$: una moltiplicazione complessa, cioè $4$ moltiplicazioni reali più $2$ addizioni reali: $T(1) = 6$. Per esempio $(a + ib)(c + id) = (ac - bd) + i(ad + bc)$: i prodotti $ac$, $bd$, $ad$, $bc$ ($4$) e la differenza $ac - bd$ e la somma $ad + bc$ ($2$).
• Conquer ($n > 1$): $4$ somme di matrici complesse $\frac n2 \times \frac n2$. Ogni somma ha $\left(\frac n2\right)^2 = \frac{n^2}{4}$ addizioni complesse, ognuna da $2$ addizioni reali: $4 \cdot \frac{n^2}{4} \cdot 2 = 2n^2$ operazioni reali. Il divide non costa (metacomando).

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

Punto (b): induzione parametrica con polinomio di terzo grado

Si pone la guess $T(n) = an^3 + bn^2 + cn + d$ con $a, b, c, d$ da determinare: l'induzione parametrica impone che il passo induttivo, con questa forma, funzioni come identità in $n$, e raccoglie i vincoli (Induzione parametrica - limitazioni esatte delle ricorrenzeL'induzione parametrica prova una limitazione T(n) <= cn+d (o >=) con costanti c e d incognite: si simula la verifica per induzione, si raccolgono i vincoli su c e d dalla base e dal passo HP => TH, e se l'intersezione non è vuota si sceglie la coppia migliore. Per MAX dà esattamente T(n) = n-1; può fallire anche con guess veri (si aggiunge un parametro o un termine di ordine inferiore).Induzione parametrica - limitazioni esatte delle ricorrenze →).

Caso base. $T(1) = a + b + c + d$ deve valere $6$:

$$a + b + c + d = 6. \tag{1}$$

Passo. Per $n > 1$ si suppone $T(\frac n2) = a\left(\frac n2\right)^3 + b\left(\frac n2\right)^2 + c\,\frac n2 + d$ e si calcola, sostituendo nella ricorrenza:

$$\begin{aligned} T(n) &= 8\,T\!\left(\tfrac n2\right) + 2n^2 \\ &= 8a\,\frac{n^3}{8} + 8b\,\frac{n^2}{4} + 8c\,\frac n2 + 8d + 2n^2 \\ &= an^3 + (2b + 2)n^2 + 4cn + 8d. \end{aligned}$$

Perché la guess sia valida deve valere $T(n) = an^3 + bn^2 + cn + d$ per ogni $n > 1$, cioè

$$an^3 + (2b + 2)n^2 + 4cn + 8d = an^3 + bn^2 + cn + d \quad \text{per infiniti valori di } n.$$

Due polinomi uguali in infiniti punti sono identici: i coefficienti dei monomi dello stesso grado coincidono.

• $n^3$: $a = a$, nessun vincolo.
• $n^2$: $2b + 2 = b$, quindi $b = -2$.
• $n^1$: $4c = c$, quindi $c = 0$.
• $n^0$: $8d = d$, quindi $d = 0$.

Sostituendo in (1): $a - 2 + 0 + 0 = 6$, quindi $a = 8$. Risultato:

$$\boxed{T(n) = 8n^3 - 2n^2.}$$

Verifica per induzione (ora con valori numerici, senza parametri). Base: $T(1) = 8 - 2 = 6$ ✓. Passo: se $T(\frac n2) = 8\frac{n^3}{8} - 2\frac{n^2}{4} = n^3 - \frac{n^2}{2}$ allora $T(n) = 8\left( n^3 - \frac{n^2}{2} \right) + 2n^2 = 8n^3 - 4n^2 + 2n^2 = 8n^3 - 2n^2$ ✓.

Controllo indipendente. L'algoritmo ricorsivo fa le stesse operazioni di quello iterativo ($2n^3 - n^2$ operazioni complesse; 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 →): $n^3$ moltiplicazioni complesse e $n^3 - n^2$ addizioni complesse. In operazioni reali: $n^3$ moltiplicazioni complesse da $6$ operazioni reali ciascuna ($6n^3$) e $n^3 - n^2$ addizioni complesse da $2$ ciascuna ($2n^3 - 2n^2$): $6n^3 + 2n^3 - 2n^2 = 8n^3 - 2n^2$ ✓. Per $n = 2$ il valore è $64 - 8 = 56$: otto prodotti complessi ($48$) e quattro somme complesse ($8$).

Punto (c): moltiplicazioni reali

Metodo 1, conteggio diretto. Il prodotto ricorsivo esegue tutti i prodotti $a_{ik}\,b_{kj}$ per $1 \le i, j, k \le n$, e nessun altro: $n^3$ moltiplicazioni complesse (le somme delle ricorsioni non contengono prodotti). Ognuna richiede $4$ moltiplicazioni reali:

$$T_{MUL}(n) = 4n^3.$$

Metodo 2, ricorrenza. Le moltiplicazioni reali soddisfano $T_{MUL}(1) = 4$ (una moltiplicazione complessa) e $T_{MUL}(n) = 8\,T_{MUL}(\frac n2)$ (le somme del conquer non contengono moltiplicazioni, quindi il lavoro dei nodi interni è $0$). Srotolando: $T_{MUL}(n) = 8^k \cdot 4 = n^3 \cdot 4 = 4n^3$ (con $n = 2^k$, $8^k = n^3$). I due metodi concordano.

Verifica con un programma. Un'implementazione dell'algoritmo ricorsivo su matrici a elementi complessi, con conteggio delle operazioni reali (un prodotto complesso vale $6$, una somma complessa $2$), per $n = 1, 2, \dots, 32$, dà $8n^3 - 2n^2$ operazioni e $4n^3$ moltiplicazioni reali; i risultati coincidono con il prodotto calcolato da numpy.