Diferenças entre edições de "Matrizes"

De GNU Octave
Ir para: navegação, pesquisa
(Propriedades do tabuleiro de sudoku)
(Exercícios)
(Há 15 edições intermédias do mesmo utilizador que não estão a ser apresentadas)
Linha 317: Linha 317:
 
\end{bmatrix}
 
\end{bmatrix}
 
</math>.
 
</math>.
 
==== Soma e produto escalar ====
 
 
==== Produto de matrizes ====
 
  
 
=== Exercícios ===
 
=== Exercícios ===
  
# Calcule A + B
+
# Calcule A + B. <p><math>
# Calcule A + A
+
A + B =
# Calcule o produto escalar 2 * B
+
\begin{bmatrix}
# Comprove que o número de colunas de A é igual ao número de linhas de B
+
  2 & 0 \\
# Calcule o produto A*B
+
  2 & 4
# Calcule o produto A*B*C
+
\end{bmatrix}
# Prove que o produto de matrizes é associativo (AB)C = A(BC)
+
</math>.</p>
# Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC
+
# Calcule A + A. <p><math>
# Prove que a matriz identidade é o elemento neutro para o produto AI = A e IA = A. Use <syntaxhighlight enclose="none">I = eye(2)</syntaxhighlight> para gerar a matriz I.
+
A + A =
 +
\begin{bmatrix}
 +
  2 & 4 \\
 +
  6 & 8
 +
\end{bmatrix}
 +
</math>.</p>
 +
# Calcule o produto escalar 2 * B. <p><math>
 +
2 * B =
 +
\begin{bmatrix}
 +
  2 & -4 \\
 +
  -2 & 0
 +
\end{bmatrix}
 +
</math>.</p>
 +
# Comprove que o número de colunas de A é igual ao número de linhas de B. <syntaxhighlight>size(A)(2) == size(B)(1)</syntaxhighlight>
 +
# Calcule o produto A*B. <p><math>
 +
A * B =
 +
\begin{bmatrix}
 +
  -1 & -2 \\
 +
  -1 & -6
 +
\end{bmatrix}
 +
</math>.</p>
 +
# Calcule o produto A*B*C. <p><math>
 +
A * B *C =
 +
\begin{bmatrix}
 +
  2 & -2 \\
 +
  10 & -10
 +
\end{bmatrix}
 +
</math>.</p>
 +
# Prove que o produto de matrizes é associativo (AB)C = A(BC). <p><syntaxhighlight enclose="none">(A*B)*C == A*(B*C)</syntaxhighlight> ou <syntaxhighlight enclose="none">all(all((A*B)*C == A*(B*C)))</syntaxhighlight></p>
 +
# Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC. <syntaxhighlight>A*(B+C) == A*B+A*C</syntaxhighlight>.
 +
# Prove que a matriz identidade é o elemento neutro para o produto AI = A e IA = A. Use <syntaxhighlight enclose="none">I = eye(2)</syntaxhighlight> para gerar a matriz I. <syntaxhighlight>A*I == A, I*A == A</syntaxhighlight>.
 
# Prove que a matriz nula é o elemento absorvente para o produto: OA == AO == O. Use <syntaxhighlight enclose="none">O = zeros(2)</syntaxhighlight> para gerar a matriz nula O. ''Neste exercício, use a letra ó maiúscula (O) para representar a matriz nula, e não o número zero (0). Se usar o número zero, em vez do ó maiúsculo (O), está a multiplicar o escalar zero por uma matriz, e não a matriz nula.''
 
# Prove que a matriz nula é o elemento absorvente para o produto: OA == AO == O. Use <syntaxhighlight enclose="none">O = zeros(2)</syntaxhighlight> para gerar a matriz nula O. ''Neste exercício, use a letra ó maiúscula (O) para representar a matriz nula, e não o número zero (0). Se usar o número zero, em vez do ó maiúsculo (O), está a multiplicar o escalar zero por uma matriz, e não a matriz nula.''
 
# Prove que <math>\alpha</math>(AB) = (<math>\alpha</math>A)B = A(<math>\alpha</math>B). Use um valor real qualquer como <math>\alpha</math>, à sua escolha.
 
# Prove que <math>\alpha</math>(AB) = (<math>\alpha</math>A)B = A(<math>\alpha</math>B). Use um valor real qualquer como <math>\alpha</math>, à sua escolha.
Linha 451: Linha 477:
  
 
<syntaxhighlight>
 
<syntaxhighlight>
>> facil([1:3], [7:9])
+
>> facil(1:3, 7:9)
 
ans =
 
ans =
  
Linha 459: Linha 485:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
==== Resolução do sudoku ====
+
[[Resolução do Sudoku]]
  
Os problemas do sudoku podem ser fáceis ou difíceis de resolver.
+
[[Como apresentar um tabuleiro de sudoku neste wiki]]
  
A função resolve aqui apresentada resolve os problemas fáceis de resolver. Isto é, resolver os problemas em que, olhando para a linha, para a coluna, e para a submatriz, conseguimos descobrir que número está em falta. Vamos percorrendo o tabuleiro várias vezes, preenchendo as casas que formos capazes de preencher.
+
=== Exercício adicional ===
  
Se não conseguirmos preencher nenhuma casa percorrendo todo o tabuleiro, então não adianta continuar a tentar. É porque o problema é mais complicado e exige outro algoritmo de resolução (mais complicado).
+
[[Gerar matrizes a partir de funções f(i,j)]]
 
+
<syntaxhighlight>
+
function res = resolve(m)
+
  res = m;
+
  do
+
    emfalta = length(res(res == 0));
+
    # printf('Faltam %d casas\n', emfalta);
+
    res = percorre(res);
+
    sofaltam = length(res(res == 0));
+
    # printf('Faltam %d casas\n', sofaltam);
+
  until (sofaltam == 0 | emfalta == sofaltam);
+
  if (emfalta == sofaltam)
+
    printf('Desisto! Demasiado complicado para mim.\n');
+
  endif
+
endfunction
+
 
+
function res = percorre (m)
+
  preenchidos = 0;
+
  res = m;
+
  for linha = 1:9,
+
    for coluna = 1:9,
+
      if (m(linha, coluna) == 0)
+
        % por preencher
+
        valor = calculaPossiveis(res, linha, coluna);
+
        if (valor > 0)
+
          res(linha, coluna) = valor;
+
        endif
+
      endif
+
    endfor
+
  endfor
+
endfunction
+
 
+
function numero = calculaPossiveis(tabuleiro, linha, coluna)
+
  faltanalinha = setdiff(1:9, tabuleiro(linha,:));
+
  faltanacoluna = setdiff(1:9, tabuleiro(:,coluna));
+
  faltanamatriz = setdiff(1:9, submatriz(tabuleiro, linha, coluna));
+
  falta = intersect(intersect(faltanalinha, faltanacoluna),faltanamatriz);
+
  if length(falta) == 1
+
    numero = falta(1);
+
  else
+
    numero = 0;
+
  endif
+
endfunction
+
 
+
function res = submatriz(m, linha, coluna)
+
  x = fix((linha-1)/3)*3+1;
+
  y = fix((coluna-1)/3)*3+1;
+
  res = m([x:x+2], [y:y+2]);
+
endfunction
+
</syntaxhighlight>
+
 
+
Para usar esta função, guarda-se o conteúdo anterior num documento '''resolve.m'''. Alternativamente pode descarregar o documento [http://octave.di.uminho.pt/images/files/resolve.m resolve.m]. Depois, aplica-se o mesmo a uma matriz, da seguinte forma:
+
 
+
<syntaxhighlight>
+
facil = [
+
0 7 2  0 0 1  8 0 5;
+
0 5 1  0 3 7  0 9 0;
+
4 0 0  2 0 8  1 0 7;
+
 
+
0 4 7  5 2 0  3 0 0;
+
0 2 6  7 0 0  5 0 1;
+
5 0 0  1 0 6  0 2 9;
+
 
+
2 9 0  3 7 0  0 1 0;
+
7 0 0  0 6 2  0 5 3;
+
3 0 8  0 1 0  2 7 0
+
];
+
>> resolve(facil)
+
ans =
+
 
+
          6          7          2          4          9          1          8          3          5
+
          8          5          1          6          3          7          4          9          2
+
          4          3          9          2          5          8          1          6          7
+
          1          4          7          5          2          9          3          8          6
+
          9          2          6          7          8          3          5          4          1
+
          5          8          3          1          4          6          7          2          9
+
          2          9          5          3          7          4          6          1          8
+
          7          1          4          8          6          2          9          5          3
+
          3          6          8          9          1          5          2          7          4
+
</syntaxhighlight>
+
 
+
===== Como apresentar um tabuleiro de sudoku neste wiki =====
+
 
+
Neste wiki, existe uma ''template'' para apresentar um tabuleiro de sudoku. Para apresentar um tabuleiro, basta escrever:
+
 
+
<pre>
+
{{Sudoku 9x9 grid}}
+
</pre>
+
 
+
Para se preencher o tabuleiro, escreve-se algo do género:
+
 
+
<pre>
+
{{Sudoku 9x9 grid|title=Tabuleiro inicial|s2=7|s3=2|s6=1|s7=8|s9=5|s11=5|s12=1|s14=3|s15=7|s17=9|s19=4|s22=2|s24=8|s25=1|s27=7|s29=4|s30=7|s31=5|s32=2|s34=3|s38=2|s39=6|s40=7|s43=5|s45=1|s46=5|s49=1|s51=6|s53=2|s54=9|s55=2|s56=9|s58=3|s59=7|s62=1|s64=7|s68=6|s69=2|s71=5|s72=3|s73=3|s75=8|s77=1|s79=2|s80=7}}
+
</pre>
+
 
+
Para tornar este processo mais fácil, escreveu-se uma função wikiprint que, dada uma matriz, escreve a mesma nesta sintaxe do wiki:
+
 
+
<syntaxhighlight>
+
function wikiprint(m)
+
  printf("{{Sudoku 9x9 grid|title=Tabuleiro|");
+
  for linha = 1:9
+
    for coluna = 1:9
+
      if (m(linha, coluna))
+
        printf("s%d=%d|", (linha-1)*9+coluna, m(linha, coluna));
+
      endif
+
    endfor
+
  endfor
+
  printf("}}");
+
endfunction
+
</syntaxhighlight>
+
  
 
=== Leitura adicional ===
 
=== Leitura adicional ===
  
 
Reveja os conceitos apresentados sobre matrizes e outros um pouco mais avançados em [http://en.wikibooks.org/wiki/Octave_Programming_Tutorial/Vectors_and_matrices Vectors and matrices, Octave Programming Tutorial].
 
Reveja os conceitos apresentados sobre matrizes e outros um pouco mais avançados em [http://en.wikibooks.org/wiki/Octave_Programming_Tutorial/Vectors_and_matrices Vectors and matrices, Octave Programming Tutorial].

Revisão das 15h43min de 17 de outubro de 2017

Notação matemática

A notação utilizada em matemática para matrizes introduz a noção de elemento, designado por a_{ij}, a matriz geralmente designada por uma letra maiúscula, A, por exemplo, e a geometria da matriz m \times n, se esta tiver m linhas por n colunas. Seja então a seguinte matriz:


 A_{m,n} =
 \begin{bmatrix}
  a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\
  a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\
  \vdots  & \vdots  & \ddots & \vdots  \\
  a_{m,1} & a_{m,2} & \cdots & a_{m,n}
 \end{bmatrix}

Notação do Octave

A matriz 
 A =
 \begin{bmatrix}
  1 & 2 & 3 & 4 \\
  5 & 4 & 6 & 8 \\
  9 & 10 & 12 & 12
\end{bmatrix}
representa-se em Octave como:

octave:3> A = [ 1, 2, 3, 4; 5, 4, 6, 8; 9, 10 , 12, 12]
A =
    1    2    3    4
    5    4    6    8
    9   10   12   12

O elemento da matriz na linha 2 e coluna 3 pode ser obtido utilizando a seguinte sintaxe:

octave:4> A(2,3)
ans =  6

Pode-se também obter toda uma linha, ou toda uma coluna. Toda a segunda linha obtém-se com:

octave:5> A(2,:)
ans =
   5   4   6   8

Toda a 4 coluna obtém-se com:

octave:6> A(:,4)
ans =
    4
    8
   12

A geometria da matriz, o número de linhas e de colunas, obtem-se com o operador size.

size(A)
ans =
   3   4

Exercícios

  1. Represente a matriz 
 B =
 \begin{bmatrix}
  0 & \frac{1}{2} & 2^2 \\
  1 & \sqrt(3) & \frac{\sqrt(3)}{3}
\end{bmatrix}
em Octave.
    octave:1> B = [0 1/2 2^2; 1 sqrt(3) sqrt(3)/3]
    B =
       0.00000   0.50000   4.00000
       1.00000   1.73205   0.57735
  2. Calcule o número de linhas da matriz. (Só o número de linhas, e não o número de linhas e colunas).
    octave:7> size(B)(1)
    ans =  2
  3. Apresente a matriz com mais casas decimais.
    octave:9> format long
    octave:10> B
    B =
       0.000000000000000   0.500000000000000   4.000000000000000
       1.000000000000000   1.732050807568877   0.577350269189626
  4. Crie uma nova matriz C com as colunas 1 e 3 de B.
    octave:11> C = B(:,[1 3])
    C =
       0.000000000000000   4.000000000000000
       1.000000000000000   0.577350269189626

Matrizes especiais

O comando diag pode criar uma matriz diagonal, se o argumento for o vetor que constitui a diagonal. Exemplo:

octave:22> diag([7 8 9])
ans =
Diagonal Matrix
   7   0   0
   0   8   0
   0   0   9

Repare que o argumento de diag é um vetor, no exemplo apresentado, e o resultado é uma matriz.

Alternativamente, o comando diag devolve o vetor da diagonal de uma matriz, se o argumento for uma matriz.

octave:18> A = [1 2 3; 4 5 6; 7 8 9]
A =
   1   2   3
   4   5   6
   7   8   9
octave:19> diag(A)
ans =
   1
   5
   9
Matriz identidade

A matriz identidade 
 I_n =
 \begin{bmatrix}
  1 & 0 & \cdots & 0 \\
  0 & 1 & \cdots & 0 \\
  \vdots  & \vdots  & \ddots & \vdots  \\
  0 & 0 & \cdots & 1
 \end{bmatrix}
é gerada com o comando eye(n).

octave:34> eye(3)
ans =
Diagonal Matrix
   1   0   0
   0   1   0
   0   0   1
Matriz nula

A matriz nula (com todos os elementos a zero) é gerada com o comando zeros.

>> zeros(2)
ans =
 
   0   0
   0   0
 
>> zeros(2,4)
ans =
 
   0   0   0   0
   0   0   0   0
 
>>
Matrizes com 1

De forma semelhante, pode-se gerar uma matriz só com 1 (com todos os elementos a 1) com o comando ones.

>> ones(3)
ans =
 
   1   1   1
   1   1   1
   1   1   1
 
>> ones(2,5)
ans =
 
   1   1   1   1   1
   1   1   1   1   1
 
>>

Obviamente que, com base nas matrizes geradas por zeros e ones se podem gerar outras matrizes com uma dada constante, como, por exemplo:

>> zeros(2,5)+7
ans =
 
   7   7   7   7   7
   7   7   7   7   7
 
>> ones(3)/4
ans =
 
   0.25000   0.25000   0.25000
   0.25000   0.25000   0.25000
   0.25000   0.25000   0.25000
 
>>

Exercícios

Considere a matriz 
 A =
 \begin{bmatrix}
  1 & 2 & 3 & 4 \\
  5 & 6 & 7 & 8 \\
  9 & 10 & 11 & 12
\end{bmatrix}

Verifique o resultado das seguintes expressões:

  1. Calcule diag(3:3:10)
    octave:28> diag(3:3:10)
    ans =
    Diagonal Matrix
       3   0   0
       0   6   0
       0   0   9
  2. Calcule diag(diag(A)).
    octave:30> A = [1 2 3 4; 5 6 7 8; 9 10 11 12]
    A =
        1    2    3    4
        5    6    7    8
        9   10   11   12
    octave:31> diag(diag(A))
    ans =
    Diagonal Matrix
        1    0    0
        0    6    0
        0    0   11
  3. Calcule sum(diag(eye(10))).
    octave:32> sum(diag(eye(10)))
    ans =  10

Operações sobre matrizes

Considere a matriz 
 A =
 \begin{bmatrix}
  1 & 2 \\
  3 & 4
\end{bmatrix}
, a matriz 
 B =
 \begin{bmatrix}
  1 & -2 \\
  -1 & 0
\end{bmatrix}
e a matriz 
 C =
 \begin{bmatrix}
  2 & -2 \\
  -2 & 2
\end{bmatrix}
.

Exercícios

  1. Calcule A + B.

    
 A + B =
 \begin{bmatrix}
  2 & 0 \\
  2 & 4
\end{bmatrix}
.

  2. Calcule A + A.

    
 A + A =
 \begin{bmatrix}
  2 & 4 \\
  6 & 8
\end{bmatrix}
.

  3. Calcule o produto escalar 2 * B.

    
 2 * B =
 \begin{bmatrix}
  2 & -4 \\
  -2 & 0
\end{bmatrix}
.

  4. Comprove que o número de colunas de A é igual ao número de linhas de B.
    size(A)(2) == size(B)(1)
  5. Calcule o produto A*B.

    
 A * B =
 \begin{bmatrix}
  -1 & -2 \\
  -1 & -6
\end{bmatrix}
.

  6. Calcule o produto A*B*C.

    
 A * B *C =
 \begin{bmatrix}
  2 & -2 \\
  10 & -10
\end{bmatrix}
.

  7. Prove que o produto de matrizes é associativo (AB)C = A(BC).

    (A*B)*C == A*(B*C) ou all(all((A*B)*C == A*(B*C)))

  8. Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC.
    A*(B+C) == A*B+A*C
    .
  9. Prove que a matriz identidade é o elemento neutro para o produto AI = A e IA = A. Use I = eye(2) para gerar a matriz I.
    A*I == A, I*A == A
    .
  10. Prove que a matriz nula é o elemento absorvente para o produto: OA == AO == O. Use O = zeros(2) para gerar a matriz nula O. Neste exercício, use a letra ó maiúscula (O) para representar a matriz nula, e não o número zero (0). Se usar o número zero, em vez do ó maiúsculo (O), está a multiplicar o escalar zero por uma matriz, e não a matriz nula.
  11. Prove que \alpha(AB) = (\alphaA)B = A(\alphaB). Use um valor real qualquer como \alpha, à sua escolha.

Mais operações

Transposta

A matriz transposta de A representa-se matematicamente como A^T. Por definição (A^T)_{ij} = (A)_{ji}.

Se A^T = A a matriz diz-se simétrica.

Em Octave, a matriz transposta representa-se por A'

Exercícios

  1. Prove que (A^T)^T = A
  2. Prove que (A + B)^T = A^T + B^T
  3. Prove que (\alpha A)^T = \alpha A^T
  4. Prove que (AB)^T = B^T A^T

Matrizes mágicas

Uma matriz de n por n contendo os números de 1 até n² diz-se uma matriz mágica, se cada uma das colunas, cada uma das linhas e as duas diagonais principais tiverem a mesma soma.

Considere a matriz M e a matriz N.


 M =
 \begin{pmatrix}
  8 & 1 & 6 \\
  3 & 5 & 7 \\
  4 & 9 & 2 
 \end{pmatrix},
 N =
 \begin{pmatrix}
  16 & 2 & 3 & 13 \\
  5 & 11 & 10 & 8 \\
  9 & 7 & 6 & 12 \\
  4 & 14 & 15 & 1
 \end{pmatrix}

A soma das linhas de M, das colunas e de cada uma das duas diagonais dá sempre 15. Da mesma forma, a soma das linhas de N, das colunas e das diagonais dá sempre 34. Ambas são matrizes mágicas.

Verifica-se o também a seguinte propriedade: a soma de cada linha, coluna ou diagonal é igual à soma de todos os elementos da matriz a dividir pela dimensão da mesma. Ou seja, na matriz M todas as linhas, colunas e diagonais somam 15 que é igual a 45 (soma de todos os elementos da matriz) a dividir por 3 (a dimensão da matriz). De igual modo, todos os elementos da matriz N somam 136, que dividindo por 4, dá 34, que é a soma das linhas, colunas e diagonais.

Verificar as propriedades das matrizes mágicas

  • a soma das colunas são todas iguais
range(sum(N)) == 0

ou

length(unique(sum(N))) == 1
  • a soma das colunas e a soma das linhas dão o mesmo valor

O predicado anterior tem que dar 1 (verdadeiro) aplicado a qualquer uma das matrizes anteriores M ou N.

Aplicado a uma matriz C = \begin{pmatrix} 5 & 5 \\ 5 & 3 \end{pmatrix}, tem que dar 0 (falso).

range([sum(N) sum(N')]) == 0

ou

length(unique([sum(N) sum(N')])) == 1

O jogo sudoku

O Sudoku é um quebra-cabeças popular, que consiste na preenchimento dos números em falta num tabuleiro de 9 matrizes de 3x3, colocadas de forma a formarem um grande tabuleiro de 9x9.

Apenas algumas casas começam por estar preenchidas, como ilustrado na seguinte figura.


Tabuleiro inicial
  7 2
  5 1
4    
    1
  3 7
2   8
8   5
  9  
1   7
  4 7
  2 6
5    
5 2  
7    
1   6
3    
5   1
  2 9
2 9  
7    
3   8
3 7  
  6 2
  1  
  1  
  5 3
2 7  

As regras de preenchimento são simples:

  • cada coluna tem que ter cada um dos algarismos de 1 a 9;
  • cada linha tem que ter cada um dos algarismos de 1 a 9;
  • cada algarismo só pode ocorrer 1 vez em cada linha e em cada coluna
  • cada matriz de 3x3 tem que ser preenchida com os algarismos de 1 a 9

O tabuleiro seguinte está preenchido de acordo com estas regras.


Tabuleiro resolvido
6 7 2
8 5 1
4 3 9
4 9 1
6 3 7
2 5 8
8 3 5
4 9 2
1 6 7
1 4 7
9 2 6
5 8 3
5 2 9
7 8 3
1 4 6
3 8 6
5 4 1
7 2 9
2 9 5
7 1 4
3 6 8
3 7 4
8 6 2
9 1 5
6 1 8
9 5 3
2 7 4

Propriedades do tabuleiro de sudoku

No Octave vamos representar o tabuleiro por uma matriz de 9x9, em que as casas por preencher ficam com o algarismo 0. As casas preenchidas têm um algarismo entre 1 e 9.

facil = [
0 7 2  0 0 1  8 0 5;
0 5 1  0 3 7  0 9 0;
4 0 0  2 0 8  1 0 7;
 
0 4 7  5 2 0  3 0 0;
0 2 6  7 0 0  5 0 1;
5 0 0  1 0 6  0 2 9;
 
2 9 0  3 7 0  0 1 0;
7 0 0  0 6 2  0 5 3;
3 0 8  0 1 0  2 7 0 
];

Dada a matriz anterior, podemos:

  • calcular o número de casas por preencher
>> length(facil(facil == 0))
ans =         36
  • isolar uma dada submatriz, por exemplo, a submatriz do canto superior direito
>> facil(1:3, 7:9)
ans =
 
           8           0           5
           0           9           0
           1           0           7

Resolução do Sudoku

Como apresentar um tabuleiro de sudoku neste wiki

Exercício adicional

Gerar matrizes a partir de funções f(i,j)

Leitura adicional

Reveja os conceitos apresentados sobre matrizes e outros um pouco mais avançados em Vectors and matrices, Octave Programming Tutorial.