Diferenças entre edições de "Matrizes"
(→Exercícios) |
(→Exercício 1) |
||
(Há 24 edições intermédias do mesmo utilizador que não estão a ser apresentadas) | |||
Linha 20: | Linha 20: | ||
\begin{bmatrix} | \begin{bmatrix} | ||
1 & 2 & 3 & 4 \\ | 1 & 2 & 3 & 4 \\ | ||
− | 5 & | + | 5 & 4 & 6 & 8 \\ |
− | 9 & 10 & | + | 9 & 10 & 12 & 12 |
\end{bmatrix} | \end{bmatrix} | ||
</math> | </math> | ||
Linha 69: | Linha 69: | ||
=== Exercícios === | === Exercícios === | ||
− | + | <ol> | |
+ | <li><div class="mw-collapsible mw-collapsed">Represente a matriz <math> | ||
B = | B = | ||
\begin{bmatrix} | \begin{bmatrix} | ||
Linha 76: | Linha 77: | ||
\end{bmatrix} | \end{bmatrix} | ||
</math> em Octave. | </math> em Octave. | ||
− | + | <div class="mw-collapsible-content"> | |
− | + | <syntaxhighlight> | |
− | + | 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 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | <li> | ||
+ | <div class="mw-collapsible mw-collapsed">Calcule o número de linhas da matriz. (Só o número de linhas, e não o número de linhas e colunas). | ||
+ | <div class="mw-collapsible-content"> | ||
+ | <syntaxhighlight> | ||
+ | octave:7> size(B)(1) | ||
+ | ans = 2 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | <li> | ||
+ | <div class="mw-collapsible mw-collapsed">Apresente a matriz com mais casas decimais. | ||
+ | <div class="mw-collapsible-content"> | ||
+ | <syntaxhighlight> | ||
+ | octave:9> format long | ||
+ | octave:10> B | ||
+ | B = | ||
+ | 0.000000000000000 0.500000000000000 4.000000000000000 | ||
+ | 1.000000000000000 1.732050807568877 0.577350269189626 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | <li> | ||
+ | <div class="mw-collapsible mw-collapsed">Crie uma nova matriz C com as colunas 1 e 3 de B. | ||
+ | <div class="mw-collapsible-content"> | ||
+ | <syntaxhighlight> | ||
+ | octave:11> C = B(:,[1 3]) | ||
+ | C = | ||
+ | 0.000000000000000 4.000000000000000 | ||
+ | 1.000000000000000 0.577350269189626 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | </ol> | ||
=== Matrizes especiais === | === Matrizes especiais === | ||
− | O comando diag pode criar uma matriz diagonal, se o argumento for o vetor que constitui a diagonal. Exemplo: | + | O comando <syntaxhighlight enclose="none">diag</syntaxhighlight> pode criar uma matriz diagonal, se o argumento for o vetor que constitui a diagonal. Exemplo: |
<syntaxhighlight> | <syntaxhighlight> | ||
Linha 93: | Linha 137: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
− | Alternativamente, o | + | Repare que o argumento de <syntaxhighlight enclose="none">diag</syntaxhighlight> é um vetor, no exemplo apresentado, e o resultado é uma matriz. |
+ | |||
+ | Alternativamente, o comando <syntaxhighlight enclose="none">diag</syntaxhighlight> devolve o vetor da diagonal de uma matriz, se o argumento for uma matriz. | ||
<syntaxhighlight> | <syntaxhighlight> | ||
− | octave: | + | 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 = | ans = | ||
− | + | 1 | |
− | + | 5 | |
− | + | 9 | |
</syntaxhighlight> | </syntaxhighlight> | ||
− | A matriz identidade é gerada com o comando eye. | + | ===== Matriz identidade ===== |
+ | |||
+ | A matriz identidade | ||
+ | <math> | ||
+ | I_n = | ||
+ | \begin{bmatrix} | ||
+ | 1 & 0 & \cdots & 0 \\ | ||
+ | 0 & 1 & \cdots & 0 \\ | ||
+ | \vdots & \vdots & \ddots & \vdots \\ | ||
+ | 0 & 0 & \cdots & 1 | ||
+ | \end{bmatrix} | ||
+ | </math> | ||
+ | é gerada com o comando <syntaxhighlight enclose="none">eye(n)</syntaxhighlight>. | ||
<syntaxhighlight> | <syntaxhighlight> | ||
Linha 112: | Linha 175: | ||
0 1 0 | 0 1 0 | ||
0 0 1 | 0 0 1 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===== Matriz nula ===== | ||
+ | |||
+ | A matriz nula (com todos os elementos a zero) é gerada com o comando <syntaxhighlight enclose="none">zeros</syntaxhighlight>. | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> zeros(2) | ||
+ | ans = | ||
+ | |||
+ | 0 0 | ||
+ | 0 0 | ||
+ | |||
+ | >> zeros(2,4) | ||
+ | ans = | ||
+ | |||
+ | 0 0 0 0 | ||
+ | 0 0 0 0 | ||
+ | |||
+ | >> | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ===== Matrizes com 1 ===== | ||
+ | |||
+ | De forma semelhante, pode-se gerar uma matriz só com 1 (com todos os elementos a 1) com o comando <syntaxhighlight enclose="none">ones</syntaxhighlight>. | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | |||
+ | >> | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Obviamente que, com base nas matrizes geradas por <syntaxhighlight enclose="none">zeros</syntaxhighlight> e <syntaxhighlight enclose="none">ones</syntaxhighlight> se podem gerar outras matrizes com uma dada constante, como, por exemplo: | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | |||
+ | >> | ||
</syntaxhighlight> | </syntaxhighlight> | ||
=== Exercícios === | === Exercícios === | ||
+ | |||
+ | Considere a matriz | ||
+ | <math> | ||
+ | A = | ||
+ | \begin{bmatrix} | ||
+ | 1 & 2 & 3 & 4 \\ | ||
+ | 5 & 6 & 7 & 8 \\ | ||
+ | 9 & 10 & 11 & 12 | ||
+ | \end{bmatrix} | ||
+ | </math> | ||
Verifique o resultado das seguintes expressões: | Verifique o resultado das seguintes expressões: | ||
− | + | <ol> | |
− | + | <li><div class="mw-collapsible mw-collapsed">Calcule <syntaxhighlight enclose="none">diag(3:3:10)</syntaxhighlight> | |
− | + | <div class="mw-collapsible-content"> | |
+ | <syntaxhighlight> | ||
+ | octave:28> diag(3:3:10) | ||
+ | ans = | ||
+ | Diagonal Matrix | ||
+ | 3 0 0 | ||
+ | 0 6 0 | ||
+ | 0 0 9 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | <li> | ||
+ | <div class="mw-collapsible mw-collapsed">Calcule <syntaxhighlight enclose="none">diag(diag(A))</syntaxhighlight>. | ||
+ | <div class="mw-collapsible-content"> | ||
+ | <syntaxhighlight> | ||
+ | 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 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | <li> | ||
+ | <div class="mw-collapsible mw-collapsed">Calcule <syntaxhighlight enclose="none">sum(diag(eye(10)))</syntaxhighlight>. | ||
+ | <div class="mw-collapsible-content"> | ||
+ | <syntaxhighlight> | ||
+ | octave:32> sum(diag(eye(10))) | ||
+ | ans = 10 | ||
+ | </syntaxhighlight> | ||
+ | </div> | ||
+ | </div> | ||
+ | </li> | ||
+ | </ol> | ||
=== Operações sobre matrizes === | === Operações sobre matrizes === | ||
Linha 143: | Linha 317: | ||
\end{bmatrix} | \end{bmatrix} | ||
</math>. | </math>. | ||
− | |||
− | |||
− | |||
− | |||
=== Exercícios === | === Exercícios === | ||
Linha 158: | Linha 328: | ||
# Prove que o produto de matrizes é associativo (AB)C = A(BC) | # Prove que o produto de matrizes é associativo (AB)C = A(BC) | ||
# Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC | # Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC | ||
− | # Prove que a matriz identidade é o elemento neutro para o produto AI = A e IA = A | + | # 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. |
− | # Prove que a matriz nula é o elemento absorvente para o produto: | + | # 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> | + | # 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. |
=== Mais operações === | === Mais operações === | ||
Linha 168: | Linha 338: | ||
A matriz transposta de A representa-se matematicamente como <math>A^T</math>. Por definição <math>(A^T)_{ij} = (A)_{ji}</math>. | A matriz transposta de A representa-se matematicamente como <math>A^T</math>. Por definição <math>(A^T)_{ij} = (A)_{ji}</math>. | ||
− | Se <math>A^T = A</math> | + | Se <math>A^T = A</math> a matriz diz-se simétrica. |
− | Em Octave, a matriz transposta representa-se por <syntaxhighlight>A'</syntaxhighlight> | + | Em Octave, a matriz transposta representa-se por <syntaxhighlight enclose="none">A'</syntaxhighlight> |
=== Exercícios === | === Exercícios === | ||
Linha 178: | Linha 348: | ||
# Prove que <math>(\alpha A)^T = \alpha A^T</math> | # Prove que <math>(\alpha A)^T = \alpha A^T</math> | ||
# Prove que <math>(AB)^T = B^T A^T</math> | # Prove que <math>(AB)^T = B^T A^T</math> | ||
+ | |||
+ | === 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. | ||
+ | |||
+ | <math> | ||
+ | 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} | ||
+ | </math> | ||
+ | |||
+ | 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'' | ||
+ | |||
+ | <syntaxhighlight>range(sum(N)) == 0</syntaxhighlight> | ||
+ | |||
+ | ou | ||
+ | |||
+ | <syntaxhighlight>length(unique(sum(N))) == 1</syntaxhighlight> | ||
+ | |||
+ | * ''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 <math>C = \begin{pmatrix} 5 & 5 \\ 5 & 3 \end{pmatrix}</math>, tem que dar 0 (falso). | ||
+ | |||
+ | <syntaxhighlight>range([sum(N) sum(N')]) == 0</syntaxhighlight> | ||
+ | |||
+ | ou | ||
+ | |||
+ | <syntaxhighlight>length(unique([sum(N) sum(N')])) == 1</syntaxhighlight> | ||
+ | |||
+ | === O jogo sudoku === | ||
+ | |||
+ | O [http://pt.wikipedia.org/wiki/Sudoku 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. | ||
+ | |||
+ | {{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}} | ||
+ | |||
+ | 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. | ||
+ | |||
+ | {{Sudoku 9x9 grid|title=Tabuleiro resolvido|s1=6|s2=7|s3=2|s4=4|s5=9|s6=1|s7=8|s8=3|s9=5|s10=8|s11=5|s12=1|s13=6|s14=3|s15=7|s16=4|s17=9|s18=2|s19=4|s20=3|s21=9|s22=2|s23=5|s24=8|s25=1|s26=6|s27=7|s28=1|s29=4|s30=7|s31=5|s32=2|s33=9|s34=3|s35=8|s36=6|s37=9|s38=2|s39=6|s40=7|s41=8|s42=3|s43=5|s44=4|s45=1|s46=5|s47=8|s48=3|s49=1|s50=4|s51=6|s52=7|s53=2|s54=9|s55=2|s56=9|s57=5|s58=3|s59=7|s60=4|s61=6|s62=1|s63=8|s64=7|s65=1|s66=4|s67=8|s68=6|s69=2|s70=9|s71=5|s72=3|s73=3|s74=6|s75=8|s76=9|s77=1|s78=5|s79=2|s80=7|s81=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. | ||
+ | |||
+ | <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 | ||
+ | ]; | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Dada a matriz anterior, podemos: | ||
+ | |||
+ | * calcular o número de casas por preencher | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> length(facil(facil == 0)) | ||
+ | ans = 36 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | * isolar uma dada submatriz, por exemplo, a submatriz do canto superior direito | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> facil(1:3, 7:9) | ||
+ | ans = | ||
+ | |||
+ | 8 0 5 | ||
+ | 0 9 0 | ||
+ | 1 0 7 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | ==== 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 ===== | ||
+ | |||
+ | 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> | ||
+ | |||
+ | === 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. | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | function res = funA(i, j) | ||
+ | if (i>j) | ||
+ | res = -1; | ||
+ | endif | ||
+ | if (i == j) | ||
+ | res = 0; | ||
+ | endif | ||
+ | if (i<j) | ||
+ | res = 1; | ||
+ | endif | ||
+ | endfunction | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | function res = funB(i, j) | ||
+ | if (i+j > 5) | ||
+ | res = 1; | ||
+ | endif | ||
+ | if (i+j <= 5) | ||
+ | res = 0; | ||
+ | endif | ||
+ | endfunction | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | function res = funC(i, j) | ||
+ | res = (-1)^(i-j); | ||
+ | endfunction | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Para gerar a matriz A, teríamos que fazer: | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Para gerar a matriz B, teríamos que fazer: | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | Para gerar a matriz C, teríamos que fazer: | ||
+ | |||
+ | <syntaxhighlight> | ||
+ | >> 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 | ||
+ | </syntaxhighlight> | ||
+ | |||
+ | === 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]. |
Revisão das 16h05min de 22 de outubro de 2015
Índice
Notação matemática
A notação utilizada em matemática para matrizes introduz a noção de elemento, designado por , a matriz geralmente designada por uma letra maiúscula, , por exemplo, e a geometria da matriz , se esta tiver linhas por colunas. Seja então a seguinte matriz:
Notação do Octave
A matriz 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
- Represente a matriz 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
-
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
-
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
-
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 é 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
Verifique o resultado das seguintes expressões:
- Calcule diag(3:3:10)
octave:28> diag(3:3:10) ans = Diagonal Matrix 3 0 0 0 6 0 0 0 9
-
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
-
Calcule sum(diag(eye(10))).
octave:32> sum(diag(eye(10))) ans = 10
Operações sobre matrizes
Considere a matriz , a matriz e a matriz .
Exercícios
- Calcule A + B
- Calcule A + A
- Calcule o produto escalar 2 * B
- Comprove que o número de colunas de A é igual ao número de linhas de B
- Calcule o produto A*B
- Calcule o produto A*B*C
- Prove que o produto de matrizes é associativo (AB)C = A(BC)
- Prove que o produto de matrizes é distributivo em relação à soma A(B + C) = AB + AC
- 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.
- 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.
- Prove que (AB) = (A)B = A(B). Use um valor real qualquer como , à sua escolha.
Mais operações
Transposta
A matriz transposta de A representa-se matematicamente como . Por definição .
Se a matriz diz-se simétrica.
Em Octave, a matriz transposta representa-se por A'
Exercícios
- Prove que
- Prove que
- Prove que
- Prove que
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.
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 , 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.
|
|
| |||||||||||||||||||||||||||
|
|
| |||||||||||||||||||||||||||
|
|
|
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.
|
|
| |||||||||||||||||||||||||||
|
|
| |||||||||||||||||||||||||||
|
|
|
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
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).
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
Para usar esta função, guarda-se o conteúdo anterior num documento resolve.m. Alternativamente pode descarregar o documento resolve.m. Depois, aplica-se o mesmo a uma matriz, da seguinte forma:
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
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.