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

De GNU Octave
Ir para: navegação, pesquisa
(Exercício 1)
Linha 455: Linha 455:
 
</syntaxhighlight>
 
</syntaxhighlight>
  
==== Resolução do sudoku ====
+
[[Resolução do Sudoku]]
  
Os problemas do sudoku podem ser fáceis ou difíceis de resolver.
 
  
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.
 
 
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).
 
 
<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 =====
 
===== Como apresentar um tabuleiro de sudoku neste wiki =====

Revisão das 15h00min 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
  2. Calcule A + A
  3. Calcule o produto escalar 2 * B
  4. Comprove que o número de colunas de A é igual ao número de linhas de B
  5. Calcule o produto A*B
  6. Calcule o produto A*B*C
  7. Prove que o produto de matrizes é associativo (AB)C = A(BC)
  8. Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC
  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.
  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

Neste wiki, existe uma template para apresentar um tabuleiro de sudoku. Para apresentar um tabuleiro, basta escrever:

{{Sudoku 9x9 grid}}

Para se preencher o tabuleiro, escreve-se algo do género:

{{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}}

Para tornar este processo mais fácil, escreveu-se uma função wikiprint que, dada uma matriz, escreve a mesma nesta sintaxe do wiki:

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

Ficha de Álgebra Linear e Geometria Analítica

Exercício 1

As três matrizes A, B e C são 4x4.

Começamos por criar duas matrizes, uma LINHAS e uma COLUNAS com os índices linhas e colunas, que serão usadas como argumentos para funções.

>> x=0:3; y=0:3;
>> [COLUNAS,LINHAS] = meshgrid(x,y)
COLUNAS =
   0   1   2   3
   0   1   2   3
   0   1   2   3
   0   1   2   3
LINHAS =
   0   0   0   0
   1   1   1   1
   2   2   2   2
   3   3   3   3

O nosso objetivo é criar as novas matrizes, aplicando uma função que vai buscar os valores às matrizes LINHAS e COLUNAS.

Vamos escrever 3 funções, de acordo com a respetiva definição:

function res = funA(i, j)
if (i>j)
	res = -1;
endif
if (i == j)
	res = 0;
endif
if (i<j)
	res = 1;
endif
endfunction
function res = funB(i, j)
if (i+j > 5)
	res = 1;
endif
if (i+j <= 5)
	res = 0;
endif
endfunction
function res = funC(i, j)
	res = (-1)^(i-j);
endfunction

Para gerar a matriz A, teríamos que fazer:

>> A = arrayfun(@(a,b)funA(a,b),LINHAS,COLUNAS)
A =
   0   1   1   1
  -1   0   1   1
  -1  -1   0   1
  -1  -1  -1   0

Para gerar a matriz B, teríamos que fazer:

>> B = arrayfun(@(a,b)funB(a,b),LINHAS,COLUNAS)
B =
   0   0   0   0
   0   0   0   0
   0   0   0   0
   0   0   0   1

Para gerar a matriz C, teríamos que fazer:

>> C = arrayfun(@(a,b)funC(a,b),LINHAS,COLUNAS)
C =
   1  -1   1  -1
  -1   1  -1   1
   1  -1   1  -1
  -1   1  -1   1

Leitura adicional

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