Invatare Atomica

Operatii pe matrice: diagonale, transpusa, adunare/inmultire

Progres lectie:
0%
🎯

Obiectivul lectiei

Vei stapani cele mai importante operatii pe matrice patrate si dreptunghiulare: citirea diagonalelor, impartirea in zone triunghiulare, calculul transpusei, adunarea si inmultirea matricelor. Vei intelege de ce fiecare algoritm are complexitatea pe care o are.

Dupa aceasta lectie vei putea:

  • Sa identifici si sa extragi diagonala principala si secundara dintr-o matrice patrata
  • Sa distingi cele patru zone ale unei matrice (deasupra/dedesubtul fiecarei diagonale)
  • Sa construiesti transpusa unei matrice m×n si sa intelegi schimbarea dimensiunilor
  • Sa aduni doua matrice de aceeasi dimensiune (complexitate O(m·n))
  • Sa inmultesti doua matrice compatibile (complexitate O(n3)) si sa intelegi conditia de compatibilitate
  • Intensiv: sa implementezi toate operatiile in C++ cu tablouri bidimensionale statice

Incearca singur!

Provocare initiala:

Ai matricea de 3×3 de mai jos. Inainte sa citesti lectia, scrie care crezi ca sunt elementele diagonalei principale si ale diagonalei secundare:

1  2  3
4  5  6
7  8  9
💡 Ai nevoie de un indiciu?

Diagonala principala conecteaza coltul stanga-sus cu coltul dreapta-jos: elementele unde numarul liniei este egal cu numarul coloanei (i == j).

Diagonala secundara merge din coltul dreapta-sus spre coltul stanga-jos: unde i + j = n - 1.

1

1. Diagonalele unei matrice patrate

O matrice patrata de ordin n are doua diagonale importante:
  • Diagonala principala: elementele A[i][i], unde i = 0..n-1 (indice linie = indice coloana)
  • Diagonala secundara: elementele A[i][n-1-i], unde i = 0..n-1 (suma indicilor = n-1)
Vizualizare (n=3):
  j=0   j=1   j=2
i=0 [1]   [2]   [3]   ← A[0][0] pe diag. principala; A[0][2] pe diag. secundara
i=1 [4]   [5]   [6]   ← A[1][1] pe AMBELE diagonale (centrul)
i=2 [7]   [8]   [9]   ← A[2][2] pe diag. principala; A[2][0] pe diag. secundara
# Diagonalele unei matrice patrate n x n
A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
n = len(A)

# Diagonala principala: i == j
diag_principala = []
for i in range(n):
    diag_principala.append(A[i][i])

# Diagonala secundara: i + j == n - 1
diag_secundara = []
for i in range(n):
    diag_secundara.append(A[i][n-1-i])

print("Matricea A:")
for linie in A:
    print(linie)
print("Diagonala principala:", diag_principala)
print("Diagonala secundara:", diag_secundara)
Output real (rulat cu python):
Matricea A:
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
Diagonala principala: [1, 5, 9]
Diagonala secundara: [3, 5, 7]

Complexitate: O(n) — parcurgem o singura data indicii 0..n-1.

2

2. Zone triunghiulare (deasupra/dedesubtul diagonalei)

Diagonala principala imparte matricea in doua triunghiuri:
  • Deasupra diagonalei principale: A[i][j] unde i < j
  • Dedesubtul diagonalei principale: A[i][j] unde i > j
Aceasta partitie este frecventa in probleme de tip BAC care cer suma sau numarul de elemente dintr-o zona.
Hartie impartita (n=3):
         j=0    j=1    j=2
i=0   [DIAG]  [SUS]  [SUS]
i=1   [JOS]   [DIAG] [SUS]
i=2   [JOS]   [JOS]  [DIAG]

SUS  = {A[0][1], A[0][2], A[1][2]} = {2, 3, 6} → suma = 11
JOS  = {A[1][0], A[2][0], A[2][1]} = {4, 7, 8} → suma = 19
# Suma elementelor din zonele triunghiulare
A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
n = len(A)

suma_sup = 0
for i in range(n):
    for j in range(n):
        if i < j:          # deasupra diagonalei principale
            suma_sup += A[i][j]

suma_inf = 0
for i in range(n):
    for j in range(n):
        if i > j:          # dedesubtul diagonalei principale
            suma_inf += A[i][j]

print("Suma elementelor de deasupra diagonalei principale:", suma_sup)
print("Suma elementelor de dedesubtul diagonalei principale:", suma_inf)
Output real (rulat cu python):
Suma elementelor de deasupra diagonalei principale: 11
Suma elementelor de dedesubtul diagonalei principale: 19

Verificare manuala: Sus = 2+3+6 = 11 ✓   Jos = 4+7+8 = 19 ✓

Complexitate: O(n2) — parcurgem toti cei n·n indici si filtram cu conditia.

3

3. Transpusa unei matrice

Transpusa matricei A (notata AT) se obtine prin interschimbarea liniilor cu coloanele: daca A are dimensiunea m×n, atunci AT are dimensiunea n×m.
Regula: AT[j][i] = A[i][j]
Exemplu vizual:
A (2x3):          A^T (3x2):
[1  2  3]    =>   [1  4]
[4  5  6]         [2  5]
                  [3  6]
Coloana 0 din A (1,4) devine linia 0 din A^T.
Coloana 1 din A (2,5) devine linia 1 din A^T.
Coloana 2 din A (3,6) devine linia 2 din A^T.
# Transpusa unei matrice m x n
A = [
    [1, 2, 3],
    [4, 5, 6]
]
m = len(A)       # numar linii: 2
n = len(A[0])   # numar coloane: 3

# AT are dimensiunea n x m
AT = []
for j in range(n):
    linie_noua = []
    for i in range(m):
        linie_noua.append(A[i][j])
    AT.append(linie_noua)

print("Matricea A (2x3):")
for linie in A:
    print(linie)
print("Transpusa AT (3x2):")
for linie in AT:
    print(linie)
Output real (rulat cu python):
Matricea A (2x3):
[1, 2, 3]
[4, 5, 6]
Transpusa AT (3x2):
[1, 4]
[2, 5]
[3, 6]

Complexitate: O(m·n) — fiecare element este copiat exact o data.

4

4. Adunarea matricelor

Doua matrice A si B de aceeasi dimensiune m×n se pot aduna element cu element:
C[i][j] = A[i][j] + B[i][j], pentru orice i si j
Conditie obligatorie: A si B trebuie sa aiba exact aceleasi dimensiuni! 
# Adunarea a doua matrice de aceeasi dimensiune
A = [
    [1, 2],
    [3, 4]
]
B = [
    [5, 6],
    [7, 8]
]
m = len(A)
n = len(A[0])

C = []
for i in range(m):
    linie = []
    for j in range(n):
        linie.append(A[i][j] + B[i][j])
    C.append(linie)

print("A + B =")
for linie in C:
    print(linie)
Output real (rulat cu python):
A + B =
[6, 8]
[10, 12]

Verificare manuala: C[0][0] = 1+5 = 6, C[0][1] = 2+6 = 8, C[1][0] = 3+7 = 10, C[1][1] = 4+8 = 12 ✓

Complexitate: O(m·n) — un singur parcurs dublu prin toti cei m·n indici.

5

5. Inmultirea matricelor

Produsul A (p×q) × B (q×s) este definit cand numarul de coloane din A = numarul de linii din B (= q).
Rezultatul C = A×B are dimensiunea p×s.
Formula: C[i][j] = ∑k=0..q-1 A[i][k] · B[k][j]
Fiecare element C[i][j] este produsul scalar intre linia i din A si coloana j din B.
Cum se calculeaza C[0][0]:
A = [[1,2,3],    B = [[9,8,7],
     [4,5,6],         [6,5,4],
     [7,8,9]]         [3,2,1]]

C[0][0] = linia 0 din A . coloana 0 din B
        = 1*9 + 2*6 + 3*3
        = 9 + 12 + 9 = 30
# Inmultirea matricelor patrate n x n
A = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]
B = [
    [9, 8, 7],
    [6, 5, 4],
    [3, 2, 1]
]
n = len(A)

# Initializare C cu zerouri
C = [[0]*n for _ in range(n)]

for i in range(n):
    for j in range(n):
        s = 0
        for k in range(n):
            s += A[i][k] * B[k][j]
        C[i][j] = s

print("A x B =")
for linie in C:
    print(linie)
Output real (rulat cu python):
A x B =
[30, 24, 18]
[84, 69, 54]
[138, 114, 90]

Complexitate: O(n3) — trei bucle imbricate. Algoritmul standard la nivel liceu. Exista algoritmi avansati (Strassen: O(n2.81)), dar nu fac parte din programa.

Atentie: Inmultirea matricelor nu este comutativa — in general A×B ≠ B×A!

6

6. Operatii pe matrice in C++ EXCLUSIV INTENSIV

⚡ Sectiune exclusiva pentru profil intensiv informatica

In C++, matricele se implementeaza ca tablouri bidimensionale statice. Accesul este identic cu Python (A[i][j]), dar tipul trebuie declarat explicit si dimensiunile sunt fixe la compilare.

Diagonale in C++:

#include <iostream>
using namespace std;
int main() {
    int n = 3;
    int A[3][3] = {{1,2,3},{4,5,6},{7,8,9}};
    cout << "Diagonala principala: ";
    for (int i = 0; i < n; i++) cout << A[i][i] << " ";
    cout << endl;
    cout << "Diagonala secundara: ";
    for (int i = 0; i < n; i++) cout << A[i][n-1-i] << " ";
    cout << endl;
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
Diagonala principala: 1 5 9
Diagonala secundara: 3 5 7

Adunare si inmultire in C++:

#include <iostream>
using namespace std;
int main() {
    int n = 2;
    int A[2][2] = {{1,2},{3,4}};
    int B[2][2] = {{5,6},{7,8}};
    int C[2][2];
    // Adunare
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            C[i][j] = A[i][j] + B[i][j];
    cout << "A+B:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cout << C[i][j] << " ";
        cout << endl;
    }
    // Inmultire
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            C[i][j] = 0;
            for (int k = 0; k < n; k++) C[i][j] += A[i][k] * B[k][j];
        }
    cout << "A*B:" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) cout << C[i][j] << " ";
        cout << endl;
    }
    return 0;
}
Output real (compilat g++ -std=c++17, rulat):
A+B:
6 8
10 12
A*B:
19 22
43 50

Logica este identica cu Python; diferentele sunt de sintaxa (tipuri explicite, cout in loc de print, ; la fiecare instructiune).

Transpusa in C++: AT[j][i] = A[i][j]; — aceeasi regula si acelasi rezultat ca in Python (output verificat: matricea 2x3 produce transpusa 3x2 corecta).

Exercitii practice

Exercitiul 1 (Nivel minim) — Suma diagonalelor

Avand matricea patrata de mai jos, calculeaza suma elementelor de pe diagonala principala si suma elementelor de pe diagonala secundara. Verifica raspunsul executand codul din Atomul 1.

A = [[2, 7, 1],
     [4, 3, 6],
     [5, 8, 9]]

Raspuns asteptat: diag_principala = [2, 3, 9], suma = 14; diag_secundara = [1, 3, 5], suma = 9.

Vezi rezolvarea

Diagonala principala este data de A[i][i], diagonala secundara de A[i][n-1-i], cu n = 3 (cod din Atomul 1).

  1. Diagonala principala: A[0][0] = 2, A[1][1] = 3, A[2][2] = 9, deci diag_principala = [2, 3, 9], suma = 2+3+9 = 14.
  2. Diagonala secundara: A[0][2] = 1, A[1][1] = 3, A[2][0] = 5, deci diag_secundara = [1, 3, 5], suma = 1+3+5 = 9.

Elementul A[1][1] = 3 apare pe ambele diagonale, la fel ca in exemplul din Atomul 1 (centrul matricei).

Exercitiul 2 (Nivel standard) — Transpusa si dubla transpunere

Fie matricea A de dimensiune 3×2:

A = [[1, 4],
     [2, 5],
     [3, 6]]

Calculeaza AT (dimensiunea va fi 2×3). Verifica apoi ca (AT)T = A — dubla transpunere returneaza matricea originala.

Indiciu: Modifica codul din Atomul 3 pentru aceasta matrice, apoi aplica din nou transpusa pe rezultat.

Vezi rezolvarea

A are dimensiunea 3x2 (m = 3 linii, n = 2 coloane), deci A^T va avea dimensiunea 2x3 (regula A^T[j][i] = A[i][j], din Atomul 3).

  1. Coloana 0 din A (1, 2, 3) devine linia 0 din A^T: [1, 2, 3].
  2. Coloana 1 din A (4, 5, 6) devine linia 1 din A^T: [4, 5, 6].
  3. Deci A^T = [[1, 2, 3], [4, 5, 6]].
  4. Aplicand transpusa inca o data pe A^T (2x3): coloana 0 (1, 4) devine linia 0, coloana 1 (2, 5) devine linia 1, coloana 2 (3, 6) devine linia 2, deci (A^T)^T = [[1, 4], [2, 5], [3, 6]] = A. Dubla transpunere reconstituie matricea originala.

Exercitiul 3 (Nivel performanta) — Inmultire dreptunghiulara si analiza complexitatii

Fie A de dimensiune 2×3 si B de dimensiune 3×4. Calculeaza C = A×B (care va fi o matrice 2×4). Extinde codul din Atomul 5 pentru matrice de dimensiuni diferite (nu neaparat patrate). Dupa aceea, raspunde: de cate operatii de inmultire scalara are nevoie algoritmul cu 3 bucle pentru matrice de dimensiuni p×q si q×s?

Raspuns asteptat: p · q · s operatii de inmultire (complexitate O(p·q·s)).

Vezi rezolvarea

Cerinta nu da valori concrete pentru A si B, doar dimensiunile — poti alege orice valori, algoritmul ramane acelasi. Nu-ti dau produsul gata calculat, doar structura.

  1. Extinde codul din Atomul 5: nu mai folosi o singura variabila n pentru tot. Defineste p = numarul de linii din A, q = numarul de coloane din A (= numarul de linii din B), s = numarul de coloane din B.
  2. Initializeaza C ca matrice p x s cu zerouri: C = [[0]*s for _ in range(p)].
  3. Bucla exterioara i in range(p), bucla mijlocie j in range(s), bucla interioara k in range(q): C[i][j] += A[i][k] * B[k][j].
  4. Capcana: daca refolosesti range(len(A)) pentru toate cele trei bucle (ca la matrice patrata), codul pica la matrice dreptunghiulare — fiecare bucla trebuie sa foloseasca dimensiunea ei proprie (p, q sau s), nu una singura.

Raspuns complexitate: algoritmul cu 3 bucle face p·q·s inmultiri scalare — O(p·q·s).

Criterii de evaluare: dimensiunile p, q, s folosite corect si separat; C are dimensiunea p x s; formula de complexitate justificata, nu doar enuntata.

Ce ai invatat astazi

  • Diagonala principala: A[i][i] (conditie i == j); diagonala secundara: A[i][n-1-i] (conditie i+j == n-1) — O(n)
  • Zone triunghiulare: deasupra (i < j), dedesubt (i > j) — utile la probleme BAC
  • Transpusa: AT[j][i] = A[i][j]; dimensiunile m×n devin n×m — O(m·n)
  • Adunarea matricelor: element cu element, numai daca dimensiunile sunt egale — O(m·n)
  • Inmultirea matricelor: produs scalar linie × coloana; conditie coloane(A) = linii(B) — O(n3)
  • Intensiv C++: sintaxa identica ca logica, diferente: tipuri explicite, cout, punct-virgula

Vrei mai mult?

Provocare: Scrie o functie este_simetrica(A) care verifica daca o matrice patrata este simetrica (A[i][j] == A[j][i] pentru orice i, j), oprindu-te la prima nepotrivire gasita, fara sa calculezi transpusa intreaga. Testeaza cu A = [[1,2,3],[2,5,6],[3,6,9]] (simetrica) si cu matricea din Atomul 1 (nesimetrica).

Intrebare de gandit: Inmultirea a doua matrice n x n costa O(n^3): pentru n = 1000 inseamna un miliard de operatii. Bibliotecile profesionale (ca NumPy) inmultesc matrice de aceeasi dimensiune de sute de ori mai repede decat codul Python scris manual din lectie, desi fac tot O(n^3) inmultiri si adunari. De ce crezi ca se intampla asta?

Deschidere: Fiecare strat al unei retele neuronale (cele din spatele recunoasterii de imagini sau al asistentilor de tip chat) este, matematic, o inmultire de matrice urmata de o functie neliniara. Antrenarea unui model mare inseamna trilioane de asemenea inmultiri — de-aia placile video (GPU) sunt construite special sa faca inmultiri de matrice in paralel.

Urmatoarea lectie

Continua cu Lectia 6: Siruri de caractere — string-uri, operatii, comparatii, conversii.

Continua →