Matrizes: Definição, Tipos e Operações

Matrizes

Definição

• Uma matriz $A_{m \times n}$ é uma tabela com $m \cdot n$ elementos organizados em $m$ linhas e $n$ colunas.
• O elemento $a_{ij}$ está localizado na $i$-ésima linha e $j$-ésima coluna da matriz $A$.

Tipos de Matrizes

• Matriz Quadrada: Possui o mesmo número de linhas e colunas ($m = n$).
• Matriz Diagonal: É uma matriz quadrada onde todos os elementos fora da diagonal principal são zero ($a_{ij} = 0$ para $i \neq j$).
• Matriz Identidade: É uma matriz diagonal com todos os elementos da diagonal principal iguais a um ($a_{ii} = 1$).
• Matriz Transposta: É a matriz obtida trocando as linhas pelas colunas da matriz original ($A^T$).
• Matriz Simétrica: É uma matriz quadrada idêntica à sua transposta ($A = A^T$).

Operações com Matrizes

• Adição de Matrizes: A soma de duas matrizes $A$ e $B$ da mesma ordem $(m \times n)$ é obtida somando os elementos correspondentes: $(A + B){ij} = a{ij} + b_{ij}$.
• Multiplicação por um Escalar: A multiplicação de uma matriz $A$ por um escalar $k$ é obtida multiplicando cada elemento da matriz por $k$: $(kA){ij} = k \cdot a{ij}$.
• Multiplicação de Matrizes: O produto de duas matrizes $A_{m \times p}$ e $B_{p \times n}$ é uma matriz $C_{m \times n}$, onde cada elemento $c_{ij}$ é calculado como: $c_{ij} = \sum_{k=1}^{p} a_{ik} \cdot b_{kj}$.

Determinante

• É uma função que associa um número real a uma matriz quadrada.
• Cálculo do Determinante:
  • Matriz de ordem 2: $\det(A) = \begin{vmatrix} a & b \ c & d \end{vmatrix} = ad - bc$.
  • Matriz de ordem 3 (Regra de Sarrus): Repete as duas primeiras colunas à direita da matriz e calcula a soma dos produtos das diagonais principais menos a soma dos produtos das diagonais secundárias.

Propriedades do Determinante

• Se uma matriz tem uma linha ou coluna de zeros, seu determinante é zero.
• Se duas linhas ou colunas são iguais, o determinante é zero.
• $\det(A^T) = \det(A)$.
• $\det(A \cdot B) = \det(A) \cdot \det(B)$.

Inversa de uma Matriz

• A matriz inversa de uma matriz quadrada $A$ (se existir) é uma matriz $A^{-1}$ tal que $A \cdot A^{-1} = A^{-1} \cdot A = I$, onde $I$ é a matriz identidade.
• Cálculo da Inversa: $A^{-1} = \frac{1}{\det(A)} \cdot \text{adj}(A)$, onde $\text{adj}(A)$ é a matriz adjunta de $A$.

Aplicações

• Resolução de sistemas de equações lineares.
• Transformações lineares em geometria.
• Modelagem de problemas em física e engenharia.

Estruturas de Dados e Algoritmos

Complexidade de Tempo e Espaço

Complexidade de Tempo

• Tempo que um algoritmo leva para executar em função do tamanho da entrada.
• Notação Big O: Classifica algoritmos pelo crescimento do tempo de execução ou requisitos de espaço conforme o tamanho da entrada aumenta.
  • O(1): Tempo constante.
  • O(log n): Tempo logarítmico.
  • O(n): Tempo linear.
  • O(n log n): Tempo linearítmico.
  • O(n^2): Tempo quadrático.
  • O(2^n): Tempo exponencial.
  • O(n!): Tempo fatorial.

Complexidade de Espaço

• Quantidade de espaço de memória que um algoritmo usa para executar em função do tamanho da entrada.
• Considerações : Inclui espaço para dados de entrada e espaço auxiliar.

Estruturas de Dados Comuns

Arrays (Vetores)

• Uma coleção de elementos, cada um acessado por um índice ou chave.
• Características:
  • Localizações de memória contíguas.
  • Acesso aleatório aos elementos.
• Operações:
  • Acesso: O(1)
  • Busca: O(n) (não ordenado), O(log n) (ordenado)
  • Inserção: O(n)
  • Remoção: O(n)

Listas Encadeadas

• Uma coleção linear de elementos de dados, cuja ordem não é determinada por sua posição física na memória.
• Tipos: Simplesmente, Duplamente, Circular.
• Operações:
  • Acesso: O(n)
  • Busca: O(n)
  • Inserção: O(1)
  • Remoção: O(1)

Pilhas (Stacks)

• Uma coleção de elementos que segue o princípio LIFO (Last In, First Out - Último a Entrar, Primeiro a Sair).
• Operações:
  • Push: O(1)
  • Pop: O(1)
  • Peek: O(1)

Filas (Queues)

• Uma coleção de elementos que segue o princípio FIFO (First In, First Out - Primeiro a Entrar, Primeiro a Sair).
• Operações:
  • Enqueue: O(1)
  • Dequeue: O(1)
  • Peek: O(1)

Tabelas Hash

• Implementa um tipo de dado abstrato de array associativo com mapeamento de chaves para valores.
• Usa uma função hash para calcular um índice em um array de buckets ou slots.
• Operações (Caso Médio):
  • Inserção: O(1)
  • Remoção: O(1)
  • Busca: O(1)

Árvores

• Uma estrutura de dados hierárquica com nós conectados por arestas.
• Tipos: Árvore Binária, Árvore de Busca Binária (BST), Árvore AVL, Árvore Rubro-Negra.
• Operações da Árvore de Busca Binária (BST):
  • Inserção: O(log n) (médio), O(n) (pior)
  • Remoção: O(log n) (médio), O(n) (pior)
  • Busca: O(log n) (médio), O(n) (pior)

Grafos

• Uma estrutura de dados com vértices (nós) e arestas que conectam os vértices.
• Tipos: Direcionado, Não Direcionado, Ponderado.
• Representações: Matriz de Adjacência, Lista de Adjacência.

Heaps

• Uma estrutura de dados baseada em árvore que satisfaz a propriedade heap, onde a chave(A) é ordenada em relação à chave(B) com a mesma ordenação em todo o heap, se A é um nó pai de B.
• Tipos: Min Heap, Max Heap.
• Operações:
  • Inserção: O(log n)
  • Remoção: O(log n)
  • Peek: O(1)

Algoritmos Comuns

Algoritmos de Ordenação

• Uma tabela compara a complexidade de tempo (melhor, médio e pior caso) e a complexidade de espaço para Bubble Sort, Insertion Sort, Selection Sort, Merge Sort, Quick Sort e Heap Sort.

Algoritmos de Busca

• Busca Linear: Complexidade de Tempo: O(n).
• Busca Binária: Complexidade de Tempo: O(log n) (requer dados ordenados).

Algoritmos de Grafos

• Busca em Largura (BFS): Complexidade de Tempo: O(V + E).
• Busca em Profundidade (DFS): Complexidade de Tempo: O(V + E).
• Algoritmo de Dijkstra (Caminho Mais Curto): Complexidade de Tempo: O(E + V log V).
• Algoritmo de Bellman-Ford (Caminho Mais Curto com Pesos Negativos): Complexidade de Tempo: O(V * E).

Programação Dinâmica

• Uma técnica algorítmica que resolve problemas de otimização ao dividi-los em subproblemas mais simples, utilizando o fato de que a solução ótima para o problema geral depende da solução ótima de seus subproblemas.
• Técnicas:
  • Memoização (Top-Down)
  • Tabulação (Bottom-Up)

Algoritmos Gananciosos

• Um paradigma algorítmico que segue a heurística de fazer a escolha localmente ótima em cada etapa, esperando encontrar um ótimo global.

Conceitos Adicionais

• Recursão: Um método de solucionar um problema onde a solução depende de soluções para instâncias menores do mesmo problema.
• Dividir e Conquistar: Um paradigma de design de algoritmo baseado em recursão multi-ramificada.
• Backtracking: Um algoritmo geral para encontrar todas (ou algumas) soluções para alguns problemas computacionais por construção incremental de candidatos para as soluções, e abandona um candidato (“backtracks”) assim que determina que o candidato possivelmente não pode ser completado para uma solução válida.
• Manipulação de Bits: A ação de manipular algoritmicamente bits ou outras peças de dados menores que uma palavra.

Fórmulas Importantes

• Soma dos primeiros n números naturais: $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$$
• Soma dos quadrados dos primeiros n números naturais: $$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$$
• Soma dos cubos dos primeiros n números naturais: $$\sum_{i=1}^{n} i^3 = \left(\frac{n(n+1)}{2}\right)^2$$

Aula 24: 5 de Dezembro

Prova do Lema 12

• Lema 12: $f$ é um polinômio $\Rightarrow \exists x_0 \in \mathbb{C}$ tal que $f(x_0)=0$.
  • Assumindo $f(x) = \sum_{i=0}^{n} a_i x^i$, onde $a_i \in \mathbb{C}$ e $a_n \neq 0$.
  • Assumindo $f(x) \neq 0$ para todo $x \in \mathbb{C}$, então $g(z) = \frac{1}{f(z)}$ é uma função inteira.
  • Como $\lim_{z \to \infty} |f(z)| = \infty$, existe $R$ tal que $|f(z)| > 1$ se $|z| > R$. Assim, $|g(z)| < 1$ se $|z| > R$.
  • Em $D = { z \in \mathbb{C} : |z| \leq R }$, $|g(z)|$ é contínua e limitada, então existe $M$ tal que $|g(z)| \leq M$ para todo $z \in D$.
  • Portanto, $|g(z)| \leq \max{1, M }$ para todo $z \in \mathbb{C}$, o que significa que $g(z)$ é uma função inteira limitada.
  • Pelo Teorema de Liouville, $g(z)$ é constante, o que implica que $f(z)$ é constante, levando a uma contradição.

Teorema 13

• Teorema 13: Se $f \in \mathcal{H}(\mathbb{C})$ e $f(\mathbb{C}) \subseteq \mathbb{R}$ (isto é, $f(z) \in \mathbb{R}$ para todo $z \in \mathbb{C}$), então $f$ é constante.
  • Se $f(x + iy) = u(x, y) + i v(x, y)$ e $f(\mathbb{C}) \subseteq \mathbb{R}$, então $v(x, y) = 0$ para todos $x$ e $y$.
  • As equações de Cauchy-Riemann implicam que $u_x = v_y = 0$ e $u_y = -v_x = 0$.
  • Portanto, $u_x = u_y = 0$, o que significa que $u$ é constante, e consequentemente, $f$ é constante.

Teorema 14

• Teorema 14: Se $f \in \mathcal{H}(\mathbb{C})$ e $f(\mathbb{C}) \subseteq { z \in \mathbb{C} : |z| = 1 }$, então $f$ é constante.
  • Se $|f(z)| = 1$ para todo $z \in \mathbb{C}$, então $f(z) \neq 0$ para todo $z \in \mathbb{C}$.
  • Se $g(z) = \frac{1}{f(z)}$, então $g(z)$ é uma função inteira.
  • $|g(z)| = \left| \frac{1}{f(z)} \right| = \frac{1}{|f(z)|} = 1$ para todo $z \in \mathbb{C}$, então $g(z)$ é uma função inteira limitada.
  • Pelo Teorema de Liouville, $g(z)$ é constante, o que implica que $f(z)$ é constante.

Lema 15

• Lema 15: Se $f \in \mathcal{H}(G)$, onde $G$ é uma região, e existe $z_0 \in G$ tal que $|f(z)| \geq |f(z_0)|$ para todo $z \in G$, então $f$ é constante.

Teorema 16: Princípio do Módulo Máximo

• Teorema 16: Seja $G$ uma região limitada em $\mathbb{C}$. Suponha que $f \in \mathcal{H}(G)$ e $f$ seja contínua em $\overline{G} = G \cup \partial G$. Então $\max_{z \in \overline{G}} |f(z)| = \max_{z \in \partial G} |f(z)|$. Ou seja, o máximo de $|f(z)|$ em $\overline{G}$ é atingido em $\partial G$.
  • Como $|f(z)|$ é contínuo no conjunto compacto $\overline{G}$, existe $z_0 \in \overline{G}$ tal que $|f(z_0)| \geq |f(z)|$ para todo $z \in \overline{G}$.
  • Se $z_0 \in \partial G$, então o teorema está provado.
  • Se $z_0 \in G$, então pelo Lema 15, $f$ é constante, o que implica que $|f(z)|$ é constante em $\overline{G}$. Portanto, $\max_{z \in \overline{G}} |f(z)| = \max_{z \in \partial G} |f(z)|$.

Estatísticas Descritivas

Definições

• População: Conjunto total de indivíduos ou objetos de interesse em um estudo estatístico.
• Amostra: Um subconjunto representativo da população.
• Variável: Uma característica ou atributo que é medido ou observado em cada indivíduo ou objeto na população ou amostra.
  • Quantitativa: Uma variável que pode ser medida numericamente.
    • Discreta: Assume valores isolados (ex: número de filhos).
    • Contínua: Assume qualquer valor dentro de um intervalo (ex: altura).
  • Qualitativa: Uma variável que não pode ser medida numericamente.
    • Nominal: Não possui ordem inerente (ex: cor dos olhos).
    • Ordinal: Possui uma ordem definida (ex: nível de satisfação).
• Parâmetro: Uma medida numérica que descreve uma característica da população.
• Estatística: Uma medida numérica que descreve uma característica da amostra.

Medidas de Tendência Central

• Média: A soma de todas as observações dividida pelo número de observações.
  • Média da população: $\mu = \frac{\sum_{i=1}^{N} x_i}{N}$.
  • Média da amostra: $\bar{x} = \frac{\sum_{i=1}^{n} x_i}{n}$.
• Mediana: O valor que divide um conjunto de dados ordenado em duas partes iguais.
• Moda: O valor que ocorre com maior frequência em um conjunto de dados.

Medidas de Dispersão

• Amplitude: A diferença entre o valor máximo e o valor mínimo em um conjunto de dados.
• Variância: A média dos quadrados das diferenças entre cada observação e a média.
  • Variância da população: $\sigma^2 = \frac{\sum_{i=1}^{N} (x_i - \mu)^2}{N}$.
  • Variância da amostra: $s^2 = \frac{\sum_{i=1}^{n} (x_i - \bar{x})^2}{n-1}$.
• Desvio Padrão: A raiz quadrada da variância.
  • Desvio padrão da população: $\sigma = \sqrt{\sigma^2}$.
  • Desvio padrão da amostra: $s = \sqrt{s^2}$.
• Coeficiente de Variação: A razão entre o desvio padrão e a média.
  • Coeficiente de variação da população: $CV = \frac{\sigma}{\mu}$.
  • Coeficiente de variação da amostra: $CV = \frac{s}{\bar{x}}$.

Medidas de Posição

• Quartis: Valores que dividem um conjunto de dados ordenado em quatro partes iguais.
  • $Q_1$: Primeiro quartil (25% dos dados são menores que $Q_1$).
  • $Q_2$: Segundo quartil (50% dos dados são menores que $Q_2$) (mediana).
  • $Q_3$: Terceiro quartil (75% dos dados são menores que $Q_3$).
• Percentis: Valores que dividem um conjunto de dados ordenado em cem partes iguais.
  • $P_k$: k-ésimo percentil (k% dos dados são menores que $P_k$).

Representações Gráficas

• Diagrama de Barras: Usado para variáveis qualitativas ou quantitativas discretas.
• Histograma: Usado para variáveis quantitativas contínuas.
• Boxplot (Diagrama de Caixa): Representa a distribuição dos dados usando quartis e valores extremos.

Matriisilaskenta, primavera 2024 (Cálculo Matricial, Primavera de 2024)

Ajankohtaista (Atualidades)

• Luennot (Palestras): Terças das 14h-16h na sala M1 (Otakaari 1) e Quintas das 12h-14h na sala M1 (Otakaari 1).
• Laskuharjoitukset (Exercícios):
  • A: Terças das 16h-18h na sala T3 (Otakaari 1).
  • B: Quintas das 14h-16h na sala T3 (Otakaari 1).
• Luentomateriaalit (Materiais da Palestra) estarão disponíveis na página do curso, o mais tardar, no dia seguinte à palestra.

Luennot (Palestras)

Ensimmäinen luento (8.1.2024) (Primeira palestra, 8 de Janeiro de 2024)

• Vektoriavaruudet (Espaços vetoriais):
  • Määritelmä (Definição): um conjunto $V$ com soma e multiplicação escalar definidas, que satisfazem certas condições.
  • Esimerkkejä (Exemplos): $\mathbb{R}^n$, $\mathbb{C}^n$, conjunto de polinômios $\mathbb{P}$.
  • Aliavaruus (Subespaço): um subconjunto de um espaço vetorial que também é um espaço vetorial.
  • Virittäminen (Gerar): o subespaço gerado pelos vetores $v_1, \dots, v_n$ é $\text{span}(v_1, \dots, v_n) = {c_1v_1 + \dots + c_nv_n \mid c_1, \dots, c_n \in \mathbb{R}}$.
  • Lineaarinen riippumattomuus (Independência Linear): vetores $v_1, \dots, v_n$ são linearmente independentes se $c_1v_1 + \dots + c_nv_n = 0$ implica que $c_1 = \dots = c_n = 0$.
  • Kanta (Base): uma base de um espaço vetorial é um conjunto linearmente independente de vetores que gera todo o espaço vetorial.
  • Dimension (Dimensão): a dimensão de um espaço vetorial é o tamanho de sua base.
• Lineaarikuvaukset (Transformações Lineares):
  • Määritelmä (Definição): uma transformação $T: V \to W$ que satisfaz $T(u + v) = T(u) + T(v)$ e $T(cv) = cT(v)$ para todos $u, v \in V$ e $c \in \mathbb{R}$.
  • Ydin (Núcleo): $\text{ker}(T) = {v \in V \mid T(v) = 0}$.
  • Kuva (Imagem): $\text{im}(T) = {T(v) \mid v \in V}$.
  • Injektiivisyys (Injetividade): $T$ é injetiva se $T(u) = T(v)$ implica $u = v$.
  • Surjektiivisyys (Sobrejetividade): $T$ é sobrejetiva se $\text{im}(T) = W$.
  • Isomorfismi (Isomorfismo): $T$ é um isomorfismo se é tanto injetiva quanto sobrejetiva.

Toinen luento (11.1.2024) (Segunda Palestra, 11 de Janeiro de 2024)

• Matriisit (Matrizes):
  • Määritelmä (Definição): uma matriz $m \times n$ é uma tabela retangular com $m$ linhas e $n$ colunas.
  • Matriisien yhteenlasku ja skalaarikertolasku (adição de matrizes e multiplicação escalar).
  • Matriisien kertolasku (multiplicação de matrizes): $(AB){ij} = \sum{k=1}^n A_{ik}B_{kj}$.
  • Transpoosi (Transposta): $A^T$ é a matriz cujas linhas são as colunas de $A$.
  • Käänteismatriisi (Matriz Inversa): $A^{-1}$ é a matriz que satisfaz $AA^{-1} = A^{-1}A = I$.

Determinantit (Determinantes):

• Määritelmä (Definição): um determinante é um valor escalar que pode ser calculado para uma matriz quadrada.
• $2 \times 2$ matriisin determinantti (determinante de uma matriz $2 \times 2$): $\det \begin{pmatrix} a & b \ c & d \end{pmatrix} = ad - bc$.
• Determinantin ominaisuuksia (Propriedades do Determinante):
  • $\det(A^T) = \det(A)$.
  • $\det(AB) = \det(A)\det(B)$.
  • Jos $A$:lla on nollarivi tai -sarake, niin $\det(A) = 0$ (Se $A$ tem uma linha ou coluna nula, então $\det(A) = 0$).
  • Jos $A$:lla on kaksi samaa riviä tai saraketta, niin $\det(A) = 0$ (Se $A$ tem duas linhas ou colunas iguais, então $\det(A) = 0$).
  • Jos $A$:n kaksi riviä tai saraketta vaihdetaan, niin determinantin merkki muuttuu (Se duas linhas ou colunas de $A$ são trocadas, o sinal do determinante muda).
  • Jos $A$:han lisätään rivin tai sarakkeen monikerta, niin determinantti ei muutu (Se um múltiplo de uma linha ou coluna é adicionado a $A$, o determinante não muda).
  • $\det(A) \neq 0$ jos ja vain jos $A$ on kääntyvä ( $\det(A) \neq 0$ se e somente se $A$ é invertível).

Laskuharjoitukset (Exercícios)

Ensimmäiset laskuharjoitukset (16.1.2024 ja 18.1.2024) (Primeiros exercícios, 16 de Janeiro de 2024 e 18 de Janeiro de 2024):

• Vektoriavaruudet ja lineaarikuvaukset (espaços vetoriais e transformações lineares).
• Matriisit ja determinantit (matrizes e determinantes).

Muuta

• Kurssin vastuuhenkilö: [nome]
• Kurssin assistentti: [nome]