⚡ Cap 11: Matrizes Multidimensionais, Row-Major Order e Álgebra Linear

Bem-vindo ao décimo primeiro capítulo da Especialização em Engenharia de Sistemas com Linguagem C (C17/C23)! ⚡

Na Engenharia de Sistemas, problemas como processamento digital de imagens, computação gráfica 3D, simulação física de partículas e redes neurais dependem fortemente de dados organizados em tabelas bidimensionais e volumes tridimensionais: as Matrizes (Multidimensional Arrays). Neste capítulo, você aprenderá como a memória RAM mapeia essas estruturas em Row-Major Order e como implementar algoritmos de Álgebra Matricial de alta performance.

Matrizes 2D/3D, Mapeamento Row-Major Order e Álgebra Matricial em C

🗺️ Mapa Conceitual do Capítulo

graph TD
    A["Matrizes em C (2D / 3D)"] --> B["1. Layout Físico Row-Major"]
    A --> C["2. Passagem para Funções"]
    A --> D["3. Álgebra Linear Aplicada"]
    A --> E["4. Otimização de Cache (L1/L2)"]

    B --> B1["Offset = (i * COLUNAS + j) * sizeof(T)"]
    C --> C1["Obrigatoriedade da dimensão de colunas: mat[][COLS]"]
    D --> D1["Soma, Matriz Transposta e Multiplicação O(N³)"]
    E --> E1["Localidade Espacial: Iteração por Linhas vs Cache Misses"]

📐 1. O Conceito de Matriz e o Mapeamento Row-Major Order

A memória física de um computador é um vetor linear unidimensional contínuo de bytes. Para representar uma matriz lógica $3 \times 3$ (int M[3][3]), a Linguagem C organiza os elementos em ordem de linhas sucessivas (Row-Major Order):

\[\text{Endereco}(M[i][j]) = \text{Endereco Base} + \Big( (i \times \text{COLUNAS} + j) \times \text{sizeof}(\text{tipo}) \Big)\]

$M[0][0], M[0][1], M[0][2] \rightarrow$ Linha 0 contígua na memória.
$M[1][0], M[1][1], M[1][2] \rightarrow$ Linha 1 contígua imediatamente após a Linha 0.
$M[2][0], M[2][1], M[2][2] \rightarrow$ Linha 2 contígua imediatamente após a Linha 1.

Assim como nos vetores 1D, o acesso a qualquer célula $M[i][j]$ ocorre em tempo constante e imediato $O(1)$!

⚠️ 2. Passagem de Matrizes para Funções

Ao passar uma matriz 2D para uma função, o compilador precisa saber exatamente quantas colunas cada linha possui para calcular a fórmula do deslocamento. Por isso, a especificação do número de colunas é obrigatória na assinatura da função:

#define COLS 4

// O número de colunas é OBRIGATÓRIO (a dimensão de linhas pode ficar em branco)
void zerarMatriz(int mat[][COLS], size_t linhas) {
    for (size_t i = 0; i < linhas; i++) {
        for (size_t j = 0; j < COLS; j++) {
            mat[i][j] = 0;
        }
    }
}

🧮 3. Algoritmos Clássicos de Álgebra Matricial

1. Matriz Transposta ($M^T$)

Inverte as linhas pelas colunas ($M^T[j][i] = M[i][j]$):

void transporMatriz(int lin, int col, const int A[lin][col], int T[col][lin]) {
    for (int i = 0; i < lin; i++) {
        for (int j = 0; j < col; j++) {
            T[j][i] = A[i][j];
        }
    }
}

2. Multiplicação de Matrizes ($A_{M \times K} \times B_{K \times N} = C_{M \times N}$)

Requer três laços aninhados, resultando em complexidade temporal cúbica $O(N^3)$:

void multiplicarMatrizes(int A[2][3], int B[3][2], int C[2][2]) {
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            C[i][j] = 0;
            for (int k = 0; k < 3; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
}

🚀 4. Arquitetura de Hardware: Localidade Espacial e Cache da CPU

[!IMPORTANT] Como iterar matrizes de forma Cache-Friendly: Quando a CPU busca um dado da RAM, ela carrega uma Linha de Cache inteira (64 bytes) com os dados vizinhos.

✅ Rápido (Cache-Friendly): Iterar linha por linha (mat[i][j]). Os elementos vizinhos já estão carregados na memória Cache L1!

❌ Lento (Cache-Unfriendly): Iterar coluna por coluna (mat[j][i]). Cada acesso salta uma linha inteira na RAM, gerando constantes falhas de cache (Cache Misses) que podem tornar o algoritmo até 10 vezes mais lento!

🔍 5. Diagnóstico & Resolução de Problemas (Troubleshooting)

Sintoma Observado	Causa Provável	Como Resolver
Erro de compilação: `array type has incomplete element type`	Omitida a quantidade de colunas na assinatura da função (ex: `void f(int m[][])`).	Informe obrigatoriamente a dimensão de colunas: `void f(int m[][COLS])`.
A multiplicação de matrizes produz valores incorretos	Esquecimento de zerar o acumulador `C[i][j] = 0;` antes do terceiro laço `k`.	Sempre inicialize a célula resultante com zero antes do somatório.
O algoritmo roda extremamente lento em matrizes gigantes	O laço de iteração está invertido (colunas no laço externo `j` e linhas no interno `i`).	Alinhe os laços com a ordem de memória: laço de linhas `i` por fora, laço de colunas `j` por dentro.

🏆 6. Desafio Prático de Consolidação

Enunciado do Desafio: Desenvolva um programa em C chamado filtro_imagem_convolucao.c que simule um filtro de detecção de bordas em uma imagem em escala de cinza $4 \times 4$:

Crie uma matriz $4 \times 4$ de pixels (uint8_t de 0 a 255).
Implemente a função de cálculo da Matriz Transposta para rotacionar a imagem em 90 graus.
Calcule o brilho médio de cada linha e de cada coluna da matriz.
Exiba a imagem original, a imagem transposta e os vetores de médias perfeitamente alinhados no console.

🔍 Ver Solução Comentada do Desafio

#include <stdio.h>

#define N 3

void multiplicarMatrizes(const int A[N][N], const int B[N][N], int C[N][N]) {
    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];
            }
        }
    }
}

int main(void) {
    int A[N][N] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} };
    int B[N][N] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1} }; // Identidade
    int C[N][N];

    multiplicarMatrizes(A, B, C);

    printf("Resultado de A x I (Identidade):\n");
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            printf("%3d ", C[i][j]);
        }
        printf("\n");
    }

    return 0;
}

🧭 Navegação Rápida

🧭 Navegação do Capítulo: ⬅️ Capítulo Anterior · 📚 Sumário do Módulo · ➡️ Próximo Capítulo