Matrizes

O que o código abaixo imprime?

def mostrar_matriz(matriz):
    for linha in matriz:
        for celula in linha:
            print(celula, end=' ')
        print()

def main():
    matriz = [
        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
        [10, 11, 12, 13, 14, 15, 16, 17, 18, 19],
        [20, 21, 22, 23, 24, 25, 26, 27, 28, 29],
        [30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
        [40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
        [50, 51, 52, 53, 54, 55, 56, 57, 58, 59]
    ]
    mostrar_matriz(matriz)
    return

main()

Escreva uma função iterativa para decidir se uma matriz é simétrica.
Escreva uma função iterativa que, dada uma matriz real, calcule a matriz transposta.
Escreva uma função iterativa que, dada uma matriz complexa, calcule a matriz conjugada transposta.
Escreva uma função que calcule o determinante de uma matriz $3 \times 3$. (Iremos ver um algoritmo para calcular o determinante de uma matriz $n\times n$ em geral depois, mas um algoritmo mais eficiente é conteúdo de disciplinas de Álgebra Linear.)
Escreva um algoritmo que lê uma matriz $M$ e calcula as somas:

a) da primeira coluna

b) da diagonal principal

c) da diagonal secundária

d) de todos os elementos da matriz M
Projete uma função que receba uma matriz $M$ representada como lista de listas e um valor $a$. A função deve devolver uma nova matriz obtida pelo produto escalar de $a$ por $M$, i.e., $aM$.

a) Escreva uma versão em que a matriz de saída é representada de maneira convencional, usando uma lista de linhas.

b) Escreva uma versão em que a matriz de saída é representada usando lista de colunas.

c) Escreva uma versão em que a matriz de saída é representada por uma única lista de escalares, i.e., se a matriz tem dimensões $m \times n$, então a lista de escalares correspondente terá tamanho $m \cdot n$. A lista deve respeitar a ordem da matriz quando a percorremos linha a linha.
Escreva uma função que receba um número inteiro $a$ e uma matriz $M$.

a) E conte quantos valores iguais a $a$ estão na matriz.

b) E devolva uma nova matriz indicadora, isso é, uma matriz de mesma dimensão, mas com $1$ nas posições em que $M$ tem $a$ e $0$ nas demais.
Um elemento $A_{ij}$ de uma matriz $A$ é dito ponto de sela da matriz $A$ se, e somente se, $A_{ij}$ for ao mesmo tempo o menor elemento da linha $i$ e o maior elemento da coluna $j$. Faça uma função que verifique se a matriz possui ponto de sela e devolva uma tupla $(i,j)$ com sua localização, ou None caso não possua.
Uma matriz $A$ quadrada $n \times n$ é chamada de:
- triangular superior sempre que $a_{ij} = 0$ para todo $i > j$;
- triangular inferior sempre que $a_{ij} = 0$ para todo $i < j$;
- diagonal sempre que for triangular superior e inferior.
Faça uma função que classifique uma matriz.
Uma matriz de elementos inteiros é um quadrado mágico se a soma dos elementos de cada linha, a soma dos elementos de cada coluna e a soma dos elementos das diagonais principal e secundária são todas iguais. Exemplo: a matriz abaixo é um quadrado mágico.

$$ A = \begin{bmatrix} 8 & 0 & 7\\
4 & 5 & 6\\
3 & 10 & 2\\
\end{bmatrix} $$

Escreva uma função que verifique se uma matriz de inteiros é um quadrado mágico.
Escreva um programa que leia um tabuleiro de jogo da velha e verifique o status do jogo. O tabuleiro é composto de caracteres, de forma que o um caractere o representa o jogador bola, um caractere x representa um jogador cruz e um caracter _ repesenta uma posição não preenchida. Seu programa deve dizer se x ou o é o vencedor, se deu velha, ou se a partida está indefinida.
Sudoku é jogado numa malha de 9x9 quadrados, dividida em sub-malhas de 3x3 quadrados, chamada “quadrantes”. O objetivo do jogo é preencher os quadrados com números entre 1 e 9 de acordo com as seguintes regras:
- Cada número pode aparecer apenas uma vez em cada linha.
- Cada número pode aparacer apenas uma vez em cada coluna.
- Cada número pode aparecer apenas uma vez em cada quadrante.
Exemplo:

Escreva um programa que lê um jogo de Sodoku (matriz 9x9, toda preenchida com números de 1 a 9) e verifica se é um jogo respeita as três regras acima.
Vamos fazer pixel art!

a) Desenhar é fácil. Escolha duas figuras favoritas da lista abaixo ou outras figuras de sua preferência. Para cada uma, faça uma função que recebe os parâmetros da figura e devolve uma matriz de caracteres com esse desenho.

b) Reconhecer é difícil. Escreva uma função que receba uma matriz preenchida por uma das duas funções acima e identifica qual é o desenho correspondente.

Retângulo de altura = 3 e largura = 7:
```
#######
#     #
#######
```
Triângulo retângulo de lado = 7:
```
#
##
# #
#  #
#   #
#    #
#######
```
Triângulo isósceles de altura = 5:
```
     #
    # #
   #   #
  #     #
 #########
```
Hexágono de lado = 3:
```
  ###
 #   #
#     #
 #   #
  ###
```
Quadriculado de lado = 4, largura = 4 e altura = 3
```
#############
#  #  #  #  #
#  #  #  #  #
#############
#  #  #  #  #
#  #  #  #  #
#############
#  #  #  #  #
#  #  #  #  #
#############
```
Permutações

a) Faça uma função que receba como parâmetros uma matriz quadrada de largura $n$ e dois inteiros $i,j$. A função deve trocar os conteúdos das linhas $i$ e $j$ desta matriz entre si. Esta é uma operação de matrizes conhecida como permutação de linhas.

b) A matriz identidade $I$ é uma matriz quadrada cujos elementos da diagonal valem $1$ e os demais valem $0$. Assim, multiplicando-se $I \times A$, obtemos a própria matriz $A$. Modifique a matriz $I$ de forma a obter uma matriz $P$ tal que $P \times A$ é a matriz $A$ com as linhas $i$ e $j$ trocadas.

c) De maneira geral, uma matriz $P$ quadrada que só contém $0$ e $1$ tal que cada linha ou coluna só contenha um elemento não nulo é chamada de matriz de permutação. Crie uma função que receba $P$ e $A$ e calcule o produto $P \times A$. Use o fato de que $P$ é matriz de permutação para evitar fazer calculo de somas e produtos.

Arquivos de texto

Faça um programa que leia um arquivo texto contendo números inteiros, um número por linha, ordene os inteiros e escreva o resultado da ordenação em um arquivo texto novo, um número por linha.
Escreva um programa que leia um arquivo chamado palavras.txt e escreva as palavras que terminam com "s" em um arquivo chamado plurais.txt e as demais em um arquivo chamado singulares.txt.
Escreva um programa que leia um arquivo que contém uma sequência de números naturais. O arquivo deverá fazer contagem de cada número e gerar um arquivo de saída como no exemplo.

Entrada:
```
10
1 2 1 3 2 2 6 2 1 6
```
Saída
```
Número de vezes 1: 3
Número de vezes 2: 4
Número de vezes 3: 1
Número de vezes 6: 2
```
Escreva um programa que leia dois arquivos de inteiros ordenados e escreva um novo arquivo com todos os inteiros ordenados. Depois responda.

a) Vale a pena colocar o conteúdo dos arquivos de entrada em duas listas?

b) O que você faria se tivesse quatro arquivos de inteiros ordenados.
A cifra de César é um esquema de criptografia, em que cada letra de uma mensagem é trocada pela letra a sucede em $k$ posições. A correspondência entre as letras é determinada utilizando duas rodas como da figura.

Para encriptar uma mensagem, primeiro alinhamos as letras da roda interna com a roda externa, de depois giramos a roda interna em $k$ posições para a direita. Finalmente, substituímos cada letra da roda interna pela letra correspondente na roda externa. Somente quem conhece o segredo, o número $k$, poderá recuperar a mensagem original.

Nessa foto, temos $k = 13$, assim a palavra "AJUDA" seria transformada em "NETKN".

a) Escreva uma função cifrar_cesar(arquivo_mensagem, arquivo_cifrado, k) que leia um arquivo texto e escreva a cifra de César correspondente em um outro arquivo texto.

b) Escreva uma função decifrar_cesar(arquivo_cifrado, arquivo_mensagem, k) que realize a operação inversa.

c) Um problema desse esquema é que como só há $26$ valores possíveis para $k$, não parece muito difícil decifrar uma mensagem. Como você faria isso?

Exercícios criativos

Os gifs animados fizeram a alegria do início da Web e voltaram a fazer sucesso nos dias de hoje! Na sua forma mais simples, os gifs são uma sequência imagens bitmaps. Vamos implementar um efeito de máscara sobre um gif.

a) Descreva uma estrutura para representar um gif.

b) Escreva uma função que leia um gif do teclado (número de imagens, largura e altura e sequência de pixels de cada imagem) devolva um ponteiro para um gif alocado dinamicamente.

c) Escreva uma função para liberar a memória alocada para um gif.

d) Escreva uma função que receba uma imagem e uma máscara (imagem binária em branco e preto do mesmo tamanho) e aplique a máscara na imagem. A imagem deve ser alterada para manter apenas a parte correspondente aos pixels brancos da máscara, como no exemplo.

e) Escreva uma função para aplicar uma máscara em um gif.
Um arquivo do tipo CSV (comma separated values) é um formato não padronizado para armazenar uma tabela em um arquivo de texto. Cada linha da tabela é uma linha do arquivo e os elementos de uma linha são separados por um caractere especial. Dependendo da aplicação, a especificação do formato muda, mas muitas vezes a primeira linha contém os títulos das colunas e o separador utilizado é uma vírgula.

a) Suponha que nos é dado um arquivo lista_compras.csv
```
Item,Categoria,Quantidade,Valor unitário
banana,alimentação,1,3.5
carne,alimentação,0.5,25.7
sabão em pó,limpeza,1,10.0
álcool em gel,limpeza,2,5.0
sandálias,vestuário,1,15.0
```
Crie um programa que leia um arquivo CSV como acima e calcule o valor total por categoria. Enquanto nessa questão você irá interpretar o arquivo CSV diretamente, normalmente utilizamos um módulo especializado já pronto, como o módulo csv.

b) Analise o arquivo csv de casos do novo Coronavírus. Você pode abrir esse arquivo usando um editor de texto ou um editor de planilhas. Depois crie um programa que descubra todos os países que têm mais casos por habitante do que o Brasil até determinada data. Se desejar, utilize o módulos csv para ler o arquivo e o módulo datetime para tratar e comparar datas.

Um desafio: Um quadrado latino de ordem $n$ é uma matriz em que cada elemento é um número de $1$ até $n$ e cada número aparece no máximo uma vez por linha e no máximo uma vez por coluna.

10     1     9     2     8     3     7     4     6     5
 7     8     6     9     5    10     4     1     3     2
 9    10     8     1     7     2     6     3     5     4
 5     6     4     7     3     8     2     9     1    10
 1     2    10     3     9     4     8     5     7     6
 2     3     1     4    10     5     9     6     8     7
 8     9     7    10     6     1     5     2     4     3
 3     4     2     5     1     6    10     7     9     8
 4     5     3     6     2     7     1     8    10     9
 6     7     5     8     4     9     3    10     2     1

a) É fácil verificar se uma matriz é um quadrado latino. O que parece não ser tão fácil é construir um quadrado latino. Faça uma função que receba uma inteiro $n$ e devolva um quadrado latino de tamanho $n \times n$.

b) Uma vez que você obteve um quadrado latino, encontrar outro é bem mais fácil. Faça uma função que receba uma matriz quadrada $n \times n$ totalmente preenchida com zeros, com exceção de duas posições. Essas posições foram copiadas de algum quadrado latino. Seu desafio é descobrir algum quadrado latino que tenha respeite essas posições. Por exemplo, se a entrada for a matriz

 0     0     0     0     0     0     0     0     0     0
 0     0     0     0     0     0     0     0     0     0
 0     0     0     0     0     0     0     0     0     0
 0     0     0     0     0     0     0     0     0     0
 0     0     0     0     0     0     0     0     0     0
 0     0     0     0     0     0     0     0     0     0
 0     0     0     0     0     0     0     2     0     0
 0     0     0     0     0     0     0     0     0     0
 0     0     0     6     0     0     0     0     0     0
 0     0     0     0     0     0     0     0     0     0

então uma resposta válida poderia ser o quadrado latino dado acima, já que ele respeita os valores 2 e 6 das posições não nulas. Qualquer outro quadrado latino com esses valores nessas posições também é permitido como saída.