Modulo 15 - Vetores e Matrizes

Prévia do material em texto

© E.L.Favero Algoritmos em Python 105 
 
 
 
Capítulo 
 
 
15 VETORES E MATRIZES 
Neste capítulo apresentamos duas estruturas de dados: vetores e matrizes. Estas 
estruturas são generalizações da lista e da tupla. Aqui uma lista de vetores é uma 
matriz. Falamos sobre dados e informação. Com vetores, apresentamos distância 
Euclidiana, distância de Manhattan, norma de um vetor, coseno de dois vetores. 
Apresentamos os comandos zip(), zip(*) para trabalhar com matrizes. Mostramos 
como trabalhar com a geração de valores aleatórios. 
 
 
Aqui introduzimos o conceito de estrutura de dados, como um tipo de dados contruído a 
partir de uma lista de tipos de dados mais simples. Dizemos que os tipos de dados int, float, 
char, string são tipos simples. Um vetor é uma lista homogênea, com todos elementos do 
mesmo tipo. Uma lista de vetores é uma matriz (listas de listas). Vetores e matrizes são 
objetos da matemática muito utilizados na computação. 
 
BOX: Bit e Byte x Dado x Informação. Aqui vamos conceituar a palavra 
dado. Bit é uma unidade mínima de informação. O bit pode ser 0 ou 1. Oito 
bits são um byte. Num byte pode-se representar um caracter. Composições 
de bytes formam os tipos de dados simples: int, bool, float, char e string. Tudo 
o que representamos nas variáveis dos algoritmos são os dados. 
 Os dados num contexto de interesse são interpretados como 
informações úteis. Por exemplo, num algoritmo de dar aumento de salário, os 
valores salário atual, percentual de aumento e novo salário são três variáveis 
para o programador. São três dados para o programador. Mas, são três 
informações importantes para a pessoa que paga o salário e para a pessoa 
que recebe o salário. 
 
 
15.1 Medidas de distância 
 
A distância Euclidiana é uma medida de uma reta entre dois pontos no espaço. Outra 
medida é a distância de Manhattan que consiste em seguir os contornos dos quadrados, 
unidades de medida, como fazemos para andar nas ruas de uma cidade. Assim de (0,0) até 
(6,6) via distância Eucliadiana temos sqrt( (6-0)**2+ (6-0)**2)= sqrt(72)= 8.48 unidades; e via 
distância de Manhattan teremos (6-0)+(6-0)=12 unidades (6 na vertical + 6 na horizontal). 
 
 © E.L.Favero Algoritmos em Python 106 
 
 
 
Diagrama das ruas de uma cidade: a distancia euclidiana é a reta entre os dois pontos; a 
distância de Manhattan segue o contorno dos quadrados 
 
O tabuleiro acima é um espaço plano, de duas dimensões, 2D. Podemos trabalhar em 
espaços 3D, ou até multidimensionais. Para trabalhar num espaço multidimensional, com 
distâncias e com o coseno do ângulo entre dois vetores, precisamos de uma estrutura de 
dados chamada de vetor. Um vetor é uma lista de valores. Um vetor também é chamado de 
uma estrutura de dados homogênea, pois seus elementos são todos do mesmo tipo de 
dados. 
 A figura abaixo mostra a equação da distância Euclidiana, do Coseno e da Norma. 
O coseno mede o ângulo entre dois vetores, que também pode ser considerada uma 
medidade de similaridade entre vetores. Quanto menor for o ângulo mais similares são os 
vetores. Na equação do Coseno, X dot Y significa o somatório de x(i)*y(i) para todos os x in 
X e y in Y. 
 
Distância Euclidiana: Coseno: Norma: 
 
 
Coseno versus distância euclidiana Norma do vetor 
 
 
 © E.L.Favero Algoritmos em Python 107 
 
 
15.2 Distância euclidiana, conseno e norma 
# definições estilo functional 
def euclD(x,y):return sum((a-b)**2) for a,b in zip(x, y))**0.5 
def manhD(x,y):return sum(abs(a-b) for a,b in zip(x,y)) 
def rootX2( x ):return sum([a*a for a in x])**0.5 
def cosiV(x,y):return sum(a*b for a,b in zip(x,y))/(inf+rootX2(x)*rootX2(y)) 
 
As equações podem ser facilmente codificadas em Python numa programação bem abstrata 
como consta no quadro acima, num estilo funcional de programação. Para facilitar o 
entendimento vamos codificá-las da maneira convencional, de maneira procedural, com 
comandos “for” percorrendo os vetores. 
 Se temos dois vetores X e Y e se seus elementos são x(i) e y(i), então euclD(X,Y) 
é a raiz quadrada do somatório dos valores (x(i)-y(i))**2. O sqrt(), raiz quadrada, está na 
biblioteca math, mas também pode ser escrita como x**0.5. 
 Uma biblioteca de funções é similar a uma coleção de livros, mas neste caso os 
objetos armazenados são de programação, são funções e classes. O comando from math 
import *, importa tudo da biblioteca math. Importar tudo não é uma das melhores práticas. O 
ideal é importar só o que é necessário, como veremos mais adiante. 
 
from math import * 
def euclD(x,y): 
 aux=0; 
 for i in range(len(x)): 
 aux += (x[i]-y[i])**2 
 return sqrt(aux) 
def manhD(x,y): 
 aux=0; 
 for i in range(len(x)): 
 aux += abs(x[i]-y[i]) 
 return aux 
 
A função rootX2() representa a norma de um vetor, que também é o seu comprimento. A 
norma é usada no denominador do coseno. Se u=(a,b,c,d), a rootX2(u) = 
sqrt(a*a+b*b+c*c+d*d). 
 
inf=float(1E-20) 
def rootX2(x): 
 aux=0; 
 for i in range(len(x)): 
 aux += (x[i])**2 
 return sqrt(aux) 
def cosV(x,y): 
 aux=0; 
 for i in range(len(x)): 
 aux += (x[i]*y[i]) 
 return aux/(inf+float(rootX2(x)*rootX2(y))) 
 
O coseno possui um denominador que eventualmente pode ser zero. Porém, na 
computação devemos evitar divisões por zero porque geram erros de execução. Para 
contornar este problema definimos uma constante infinitezimal (inf) com valor 1E-20= 
0.00000000000000000001, são 20 casas depois do ponto, 19 zeros antes do um. Esta 
constante é somada com o denominador e assim não dá erro de divisão. 
 
 
 © E.L.Favero Algoritmos em Python 108 
 
 
 
x=[6,1,3,2] 
y=[3,1,1,4] # z=2y 
z=[6,2,2,8] 
a=[1,2,1] 
b=[3,1,2] 
print('coseno a,b:', round(cosV(a,b),2) ) 
print('coseno x,x:', round(cosV(x,x),2)) 
print('coseno x,y:', round(cosV(x,y),2)) 
print('coseno y,z:', round(cosV(y,z),2)) 
print('euclidiana x,x:', round(euclD(x,x),2)) 
print('euclidiana y,z:', round(euclD(y,z),2)) 
>>> 
coseno a,b: 0.76 
coseno x,x: 1.0 
coseno x,y: 0.82 
coseno y,z: 1.0 
euclidiana x,x: 0.0 
euclidiana y,z: 5.2 
 
Pelos resultados podemos ver que coseno(x,x) é sempre 1, não importa quem é o vetor x. 
Agora se criamos um vetor z=2*y, coseno(y,z) continua sendo 1. Pois o vetor 2*y tem a 
mesma direção de y. Por outro lado, a distância Euclidiana entre x e x é sempre zero, 
euclD(x,x) = 0. 
 
 
15.3 Matriz como Listas 
Transpor uma matriz é transformar suas colunas em linhas e vice versa. Por exemplo, 
abaixo temos uma matriz B de 3x2, 3 linhas por duas colunas, que transposta fica de 2x3. 
 
Transposta de uma matriz 
 
 
Em Python um vetor é uma lista. O que são vetores ou matrizes multidimensionais? São 
vetores de listas ou listas de listas. 
Abaixo vamos apresentar vários recursos que são necessário para se trabalhar com 
matrizes até se chegar na transposição de matrizes. 
 
15.4 Trabalhar com números aleatórios: random 
Antes de criar a matriz vamos apresentar uma biblioteca de números aletórios, random. 
Import random as rand, significa que todos os objetos da biblioteca podem ser utilizados, 
mas com o prefixo rand, as=alias, “nick name”, nas chamadas dos métodos. 
 © E.L.Favero Algoritmos em Python 109 
 
 
Inicialmente vamos utilizar seed() e randint(). Seed cria uma semente para o 
gerador de número aletórios. Assim, debaixo de uma mesma semente ele gerará sempre a 
mesma sequência de números, mas quando mudamos a semente muda a sequência. 
Randint(2,900) gerará um numero aletório entre o valor 2 e o valor 900. Seguem alguns 
exemplos, gerando 10 valores. No for _ in, o _ indica que não importa o valor, pois neste 
caso queremos que ele apenas conte até 10, a cada conta geramos um valor randômico. 
 
import random as rand 
rand.seed(1234) 
L=[rand.randint(2,900) for _ in range(10)] 
print(L) 
rand.seed(1234)# mesma semente 
L=[rand.randint(2,900) for _ in range(10)] 
print(L) 
rand.seed(13) # muda a semente 
L=[rand.randint(2,900) for _ in range(10)] 
print(L) 
>>> 
[798, 453, 121, 9, 94, 828, 598, 37, 689, 711] 
[798, 453, 121, 9, 94, 828, 598, 37, 689, 711] 
[267, 299, 703, 702, 823, 871, 192, 669, 238, 684] 
 
Agora que sabemos como gerar uma lista de valores aletórios vamos preencher uma matriz 
com valores aletórios. Abaixo criamos uma matriz de 3 linhas por 4 colunas. 
Aqui utilizamos outra forma de importação pois vamos utilizar apenas a função 
randint e seed; esta forma de importação é uma das melhores práticas. Só importa o 
necessário. Nesta forma de importação não é usado o prefixo. 
 
from random import randint, seed 
lin=3; col=4 
matriz=[] 
seed(123321) 
for i in range(lin): 
 linha=[ (i,j,randint(1,100) ) for j in range(col)] 
 matriz.append(linha) 
# escreve todas as linhas 
for i in range(lin):print(matriz[i]) 
# escreve a diagonal 
for i in range(lin):print(matriz[i][i]) 
>>> 
[(0, 0, 18), (0, 1, 23), (0, 2, 89), (0, 3, 32)] 
[(1, 0, 48), (1, 1, 34), (1, 2, 5), (1, 3, 9)] 
[(2, 0, 63), (2, 1, 95), (2, 2, 68), (2, 3, 11)] 
(0, 0, 18) 
(1, 1, 34) 
(2, 2, 68) 
 
Para efeito didático, cada célula da matriz armazena uma tripla (linha, coluna, valor 
aleatório). O valor aleatório é gerado com randint(1,100). Cada linha compreende 4 valores 
aleatórios. Mostra-se toda a matriz com um comando for; com outro comando for, mostra-se 
como acessar só a diagonal. 
 
 
 
 
 © E.L.Favero Algoritmos em Python 110 
 
 
 
 
 
15.5 Zip e unzip zip(* ) 
Vamos ilustrar o funcionamento do zip(), fecha o zíper. Suponha a e b duas listas. zip 
emparelha as duas em duplas, fecha o zíper. O unzip, zip(* ) faz o efeito ao contrário, abre o 
zíper. O * transforma uma lista ou tupla em elementos como argumentos de uma função. 
 
>>> a=[1,2,3,4] 
>>> b=[7,8,9,10] 
>>> list(zip(a,b)) 
[(1, 7), (2, 8), (3, 9), (4, 10)] 
 
>>> cd=list(zip(a,b)) 
>>> cd 
[(1, 7), (2, 8), (3, 9), (4, 10)] 
>>> list(zip(* cd)) 
[(1, 2, 3, 4), (7, 8, 9, 10)] 
 
 
 
Zipper de listas 
 
Python tem algumas funções poderosas, por exemplo, com zip(*) podemos transpor a 
matriz: as linhas viram colunas e vice versa. O resultado do zip(*) são tuplas, cada linha é 
uma tupla; com list(zip(* matriz)) as tuplas das linhas são convertidas em listas. Com o 
comando for, a forma de manipular listas e tuplas é a mesma. 
 
from random import randint, seed 
lin=3; col=4; matriz=[] 
seed(123321) 
for i in range(lin): 
 linha=[ randint(1,100) for j in range(col)] 
 matriz.append(linha) 
print('matriz:') 
for i in range(lin):print(matriz[i]) 
print('\nmatriz transposta:') 
inv=list(zip(* matriz)) 
for i in range(col):print(list(inv[i])) # linha: tupla->lista 
>>> 
matriz: 
[18, 23, 89, 32] 
 © E.L.Favero Algoritmos em Python 111 
 
 
[48, 34, 5, 9] 
[63, 95, 68, 11] 
 
matriz transposta: 
[18, 48, 63] 
[23, 34, 95] 
[89, 5, 68] 
[32, 9, 11] 
 
15.6 Mais sobre valores aleatórios random 
Da biblioteca random temos mais algumas preciosidades. A primeira é escolher uma 
amostra aleatória dos elementos de uma lista (sample), e a segunda é embaralhar os 
elementos de uma lista (shuffle). Vamos exemplificar estes dois métodos. 
 
import random as rd 
rd.seed(15) 
L=[x for x in range(12)] 
print(L) 
>>> 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 
 
Primeiro geramos uma lista L com 12 valores. Agora vamos pegar duas amostra aleatórias 
de 3 elementos desta lista L. O zero aleatoriamente foi selecionado nas duas amostras. 
 
>>> rd.sample(L,3) 
[3, 0, 8] 
>>> rd.sample(L,3) 
[11, 0, 2] 
 
Agora vamos embaralhar a lista toda. O suffle() destrói a lista original L enquanto que o 
sample() não afeta ela. Para mostrar o resultado do shuffle() é necessário mostrar o 
conteúdo da lista L. Note que as duas embaralhadas são bem diferentes. 
 
>>> rd.shuffle(L) 
>>> L 
[7, 6, 4, 11, 8, 9, 1, 5, 2, 10, 0, 3] 
>>> rd.shuffle(L) 
>>> L 
[5, 2, 7, 10, 4, 6, 0, 11, 9, 3, 1, 8] 
 
 
15.7 Exercícios (12) 
 
E15.1 Programe as funções abaixo, num estilo procedural, utizando o comando for ou o 
commando while para percorrer os vetores. 
 
# definições estilo functional 
def euclD(x,y):return sum((a-b)**2) for a,b in zip(x, y))**0.5 
def manhD(x,y):return sum(abs(a-b) for a,b in zip(x,y)) 
def rootX2( x ):return sum([a*a for a in x])**0.5 
def cosiV(x,y):return sum(a*b for a,b in zip(x,y))/(inf+rootX2(x)*rootX2(y)) 
 
a)teste as funções com pequenos vetores garantindo que euclD(V,V) e 
 © E.L.Favero Algoritmos em Python 112 
 
 
manhD(V,V) deve ser zero e cosiV(V,V) deve ser 1.0. 
b)gere vetores aleatórios de tamanho 100 com valores entre 10 e 99 e teste 
novamente as funções 
c)será que euclD() roda em dois vetores de 100.000 elementos? 
 
E15.2 Parte I: Crie uma matriz de 10 x 9, com valores aleatórios entre 10 e 99. Use a 
biblioteca: from random import randint, seed; use uma semente para que nos testes 
seja sempre a mesma matriz. 
a)imprima a matriz em dez linhas 
b)imprima a diagonal principal 
c)imprima a diagonal secundária 
d)imprima a soma da diagonal principal, se quiser pode usar sum() 
e)imprima a média da diagonal secundária, se quiser pode usar sum() 
f)imprima o valor do mínimo elemento da matriz, se quiser pode usar min() 
g)imprima a posição do primeiro mínimo elemento da matriz, se quiser pode usar 
min() 
 
Parte II: faça a transposta da matriz gerada 
a)imprima a matriz em nove linhas 
b)imprima a diagonal principal 
c)imprima a diagonal secundária 
d)imprima a soma da diagonal principal, se quiser pode usar sum() 
e)imprima a média da diagonal secundária, se quiser pode usar sum() 
f)imprima o valor do mínimo elemento da matriz, se quiser pode usar min() 
g)imprima a posição do primeiro mínimo elemento da matriz, se quiser pode usar 
min() 
 
E15.3 Será que euclD() roda em dois vetores de 100.000 elementos? Usando vetores 
aleatórios, verifique se roda 
 
 
 
 
15.8 Perguntas conceituais (12) 
 
 Responda com no mínimo 10 palavras e no máximo 20 palavras: 
C15.1 Qual a diferença entra a distância Euclidiana e distância de Manhattan? 
C15.2 O que é a norma de um vetor? 
C15.3 O que mede o coseno de dois vetores? 
C15.4 O que faz o comando import? 
C15.5 O que faz o zip()? 
C15.6 O que faz o zip(* ) ? 
C15.7 Porque utilizar random.seed() ? 
C15.8 O que faz o shuflle()? 
C15.9 O que faz o sample() ? 
C15.10 O que é uma estrutura de dados? 
C15.11 O que é um dado? 
C15.12 Qual a diferença entre dado e informação?