Archive for 2014

Codificando Matrizes

§ 0

Origem:
Os antigos chineses apreciavam as vantagens da manipulação de matrizes ao lidar com equações lineares. Dentro da história da matemática chinesa, a obra "Nove capítulos" é de maior destaque. Sua influência estendeu-se ao Japão, onde Seki Kowa (1642-1708) formulou o conceito que hoje nós chamamos de determinante, através de sua compreensão das operações elementares utilizadas na eliminação chinesa. Posteriormente, Arthur Cayley (1821-1895) fez a distinção entre a noção de determinantes e as operações algébricas de matrizes.

Operações básicas:
- Adição de matrizes: [A+B]ij=[A]ij+[B]ij para cada i e j.
- Transposição: A=[aij], então [AT]ij = aji.
- Multiplicação de escalares: [αA] ij = α[A]ij para cada i e j. 
- Multiplicação de matrizes: Ai₁B₁j+Ai₂B₂j+···+AirBrj.
- Matriz inversa: AB=In e BA=In.

Para fazer as operações básicas entre as matrizes, temos a biblioteca numpy:

Irá retornar:
[8 9 3] [ 7 20  2]
[[1 4 7]
 [2 5 8]
 [3 6 9]] 

Criptografiando mensagens com a matriz inversa:
Podemos criptografar mensagens utilizando a propriedade da matriz inversa. Por exemplo, Alice deseja enviar uma mensagem secreta para Bob. Para isso, ela atribui um número a cada letra do alfabeto. Depois ela crifra a mensagem em uma matriz multiplicando pela sua chave (T=MC). Bob decodifica a mensagem, multiplicando a mensagem pela inversa da chave, (T=MC⁻¹).

O código abaixo demonstra o processo:
Retornado a mensagem: 'greatwork'. ;)


 * Fontes:
Aspectos da Matemática Chinesa: O "Nove Capítulos" - Marcel Vinhas Bertolini.
Matrix Analysis and Applied Algebra - C. Meyer.
http://www.programiz.com/python-programming/examples/multiply-matrix 
http://www.python-course.eu/matrix_arithmetic.php

Plotando gráficos para o Scidavis

§ 0

O Scidavis é uma aplicação gratuita para análise de dados científicos e visualização.

 Instalação no Linux:
Download: http://pt.sourceforge.jp/projects/sfnet_scidavis/downloads/SciDAVis/0.2.4/scidavis-0.2.4-linux-x86-qt4.4-py2.5.tar.bz2/
Depois é só descompactar e compilar:
$ tar -jxvf scidavis-0.2.4-linux-x86-qt4.4-py2.5.tar.bz2
$ cd scidavis-0.2.4-linux-x86-qt4.4-py2.5
$ ./scidavis

Ajustando o gráfico linear:

Para avaliar a relação linear temos o coeficiente de Pearson, que pode ser calculado usando a biblioteca numpy:  
pr = numpy.corrcoef(lista1,lista2)[0, 1]
O Scidavis faz automaticamente o ajuste da reta utilizando o método os mínimos quadrados, que consiste em calcular a linha do melhor ajuste. Podemos criar um script python fazendo o ajuste manualmente para determinar os valores de a (coeficiente angular) e b (coeficiente linear):






 
Plotando um Histograma:
O Scidavis é bastante utilizado para a construção de histogramas (distribuição de frequências), que pode ser criado através de um script python:









 A biblioteca numpy utiliza a função random e o método normal com os parâmetros (centro da distribuição, desvio padrão, tamanho) para fazer a distribuição gaussiana e a biblioteca pylab irá construir e gerar o histograma.


* Fontes:
http://pessoal.sercomtel.com.br/matematica/superior/algebra/mmq/mmq.htm
http://academic.sun.ac.za/mathed/174WG/LeastSquares.pdf
http://daemoniolabs.wordpress.com/2013/03/16/instalando-o-scidavis-no-fedora/
Basic Beginners' Introduction to plotting in Python - Sarah Blyt

Algoritmo Estendido de Euclides

§ 0

Algoritmo de Euclides:  
É um dos algoritmos mais antigos do mundo, escrito há cerca de 300 AC. Ele nada mais é do que repetidas divisões com resto que encontram o mdc.

 Exemplo do algoritmo na linguagem python:
Algoritmo Estendido de Euclides: 
Pode ser usado para expressar o mdc(a,b) como uma combinação linear de inteiros a e b: ax+by=mdc(a,b). Ex: 

 2024=748(2)+528
748=528(1)+220
528=220(2)+88
220=88(2)+44 * o último resto diferente de zero é a resposta.
88=44(2)+0

 Concluímos que o mdc(2024,748)=44.

 Agora usamos a substituição para expressar que 44 é a combinação linear de a=2024 e b=748, calculado o resto com:  r=a-b*q.

528=2024-748(2)
528=a-2b
Sub. na 2 linha:
b=(a-2b)*1+220 , então, 220=-a+3b
Sub. na 3 linha:
a-2b=(-a+3b)*2+88, então, 88=3a-8b
Sub. na penúltima linha:
-a+3b=(3a-8b)*2+44 , então, 44=-7a+19b
Ficando:
44=-7*2024+19*748=44=mdc(2024,748)

 Concluímos que a solução inteira de 2024x+748y=mdc(2024,748) é: x=-7, y=19. 

Algoritmo estendido de Euclides em python:

Se x0, y0 são a solução inteira de ax+by=mdc(a,b), então para cada inteiro k:
x=x0+    bk       e  y=y0+    ak    
          mdc(a,b)               mdc(a,b)
também é uma solução.
No exemplo acima, concluímos que x=-7+17k e y=19+46k são soluções para cada inteiro k.

Números Relativamente Primos:
Se o mdc(a,b)=1, dizemos que a e b são relativamente primos. Por exemplo, 2091 e 2143 são relativamente primos:
2143=2091+52
2091=40(52)+11
52=4(11)+8
11=8+3
8=2(3)+2
3=2+1
Então, o mdc(2091,2143)=1.
 
Podemos usar a função de Euler para encontrar os números relativamente primos. Ex: 
φ(420): Fatorando os primos 420 = 2²*3*5*7, então os divisores primos de 420 são 2, 3, 5, 7. Aplicando a função phi de Euler: n*(p-1/p1)*(p-1/p2)*...*(p-1/pk):
φ(420): 420*1/2*2/3*4/5*6/7=96, encontramos φ(420)=96.

Exemplo da função phi de Euler em python:
 


* Referências:
http://www.shsu.edu/kws006/Professional/Concepts_files/EuclideanAlgorithm.pdf
http://www3.nd.edu/~sevens/13150unit10.pdf
http://pages.pacificcoast.net/~cazelais/222/xeuclid.pdf 
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers  

Newer Entries »