BCM0505-15 - Processamento da Informação

Laboratório L04 – 12/05

Instruções

• Membros das turmas NA1 e NB{4,5} deverão submeter códigos em Python para todos os exercícios nesta página em um único arquivo .py via Tidia até 26/05 às 19h – sob a entrada E8.

Exercícios

• (01) Norma de Frobënius.
  Seja $A\in\mathbb{R}^{m\times n}$ uma matriz de pontos flutuantes. A norma de Frobënius de $A$ é dada por $$\|A\|_F := \left(\sum_{i=1}^{m}\sum_{j=1}^{n} \big(A[i][j]\big)^2\right)^{1/2}.$$ Escreva uma função que recebe $A$ e devolve $\|A\|_F$.

  Solução:
  

  from math import sqrt
  
  def frobenius_norm (A: [[float]]) -> float:
    return sqrt (sum (sum (aij*aij for aij in ai) for ai in A))
  

  $\square$

• (02) Matriz Ortogonal.
  Uma matriz quadrada $A\in\mathbb{R}^{n\times n}$ de reais é ortogonal se suas colunas e linhas forem vetores ortogonais. De outra forma, $A$ é ortogonal se $$A\cdot A^\top = I_n,$$ em que $I_n$ é a matriz identidade $n\times n$. Escreva uma função que recebe $A$ e determina se ela é ortogonal.

  Solução:
  Uma solução consiste em usar as funções da aula A06 para transpor matriz, multiplicar matrizes, e verificar se uma matriz é identidade. A título de exemplo, fornecemos este código abaixo.

  def is_orthogbad (A: [[float]]) -> bool:
    return matrix_is_identity (matrix_product (A, matrix_trasnpose (A)))
  

  Observe que duas matrizes novas são criadas nesta solução: a transposta de $A$, e a produto de $A$ com $A^\top$. Com um pouco de reflexão, percebe-se que isto é desnecessário (e, portanto, ineficiente). O próximo código realiza a tarefa sem criar nenhuma matriz temporária / adicional.

  def is_orthogonal (A: [[float]]) -> bool:
    n = len (A)
    for i in range (n):
      for j in range (n):
        if sum (A[i][k] * A[j][k] for k in range (n)) != (1 if i == j else 0):
          return False
    return True
  

  $\square$

• (03) Matriz Triangular Superior.
  Uma matriz de pontos flutuantes $A\in\mathbb{R}^{n\times n}$ é triangular superior se $$A[i][j] == 0 \qquad\text{para todo}\qquad i> j.$$ Escreva uma função que recebe $A$ e determina se ela é triangular superior.

  Solução:
  

  def is_upper_triangular (A: [[float]]) -> bool:
    for i in range (len (A)):
      for j in range (i):
        if A[i][j] != 0: 
          return False
    return True
  

  $\square$

• (04) Sistema Linear Triangular Superior.
  Dada uma matriz triangular superior $U\in\mathbb{R}^{n\times n}$ tal que $U[i][i]\neq 0$ e um vetor $b\in\mathbb{R}^n$, determine um vetor $x\in\mathbb{R}^n$ tal que $$Ux=b.$$

  Solução:
  

  def linsys_upper_triangular (U: [[float]], b: [float]) -> [float]:
    x = [0] * (n := len (U))
    for i in reversed (range (n)):
      x[i] = (b[i] - sum (U[i][j]*x[j] for j in range (i+1, n))) / U[i][i]
    return x
  

  $\square$

• (05) Quadrado Latino.
  Uma matriz de inteiros $A\in\mathbb{Z}^{n\times n}$, com $n\geq 0$ é um quadrado latino se os números do conjunto $\{1,2,\ldots,n\}$ ocorrem em todas as linhas e em todas as colunas de $A$. Por exemplo, a matriz abaixo é um quadrado latino. $$ \left(\begin{array}{rrrr} 1 & 4 & 3 & 2\\ 2 & 3 & 4 & 1\\ 3 & 1 & 2 & 4\\ 4 & 2 & 1 & 3 \end{array}\right) $$ Escreva uma função que recebe uma matriz $n\times n$ de inteiros $A$ e determina se $A$ é um quadrado latino.

  Solução:
  Cada linha e cada coluna devem somar $1+2+\cdots+n=n(n+1)/2$. Esse teste simples é necessário, mas não é suficiente: $$1+2+3+4=1+3+3+3.$$ É preciso verificar a ocorrência de cada valor em cada linha e cada coluna.

  def is_latin_square (A: [[int]) -> bool:
    for i in range (n):
      lin = [False] * n
      col = [False] * n
      for j in range (n):
        lin [A[i][j]-1] = True
        col [A[j][i]-1] = True
      if not all (lin) or not all (col):
        return False
    return True
  

  $\square$