Exercício 2 - Introdução aos conceitos e Ferramentas

Python

Python é uma linguagem de programação de propósito geral, de alto nível e com uma sintaxe bastante legível e intuitiva. Ela é orientada a objetos, majoritariamente imperativa e dinâmica, sendo geralmente codificada como uma linguagem de script e já vem com vários pacotes disponíveis, o que permite que o usuário crie algoritmos e protótipos rapidamente.

Tipos de alto nível

  • String
  • Lista e tupla
  • Dicionário
  • Classe

String representa uma cadeia de caracteres.

 1 # cria uma string
 2 s1 = str('a minha casa')
 3 print 's1: %s' %(s1)
 4 
 5 # adiciona uma string com outra
 6 s2 = str(' azul.')
 7 s3 = s1 + s2
 8 print 's3: %s' %(s3)
 9 
10 # enxuga string
11 s3 = s3.strip('.')
12 print 's3 exugada: %s' %(s3)
13 
14 # acha a posição da palavra azul
15 pos = s3.find('azul')
16 print 'posição da palavra azul na string s3: %d' %(pos)
17 
18 # substitui a palavra azul por amarela
19 s4 = s3.replace('azul', 'amarela')
20 print 's4: %s' %(s4)
21 
22 # separa a string segundo um delimitador, nesse caso, espaço
23 ls= s4.split(' ')
24 print 'lista de palavras em s4 separadas por espaço: '
25 print ls
s1: a minha casa
s3: a minha casa azul.
s3 exugada: a minha casa azul
posição da palavra azul na string s3: 13
s4: a minha casa amarela
lista de palavras em s4 separadas por espaço: 
['a', 'minha', 'casa', 'amarela']

Lista é semelhante a um vetor na linguagem de programação C. A lista pode conter qualquer tipo do python como elemento, até mesmo listas e pode conter diferentes elementos.

 1 # construção de uma lista
 2 l1 = [1, 'a', 2, 'b']
 3 print 'lista l1: %s' %(l1)
 4 
 5 # para acessar um elemento da lista, usa-se seu índice
 6 i  = l1[2]
 7 print 'elemento no índice 2: %d' %(i)
 8 
 9 # listas suportam operadores
10 l2 = [3, 'c']
11 l3 = l1+l2
12 print 'soma da lista l1 com l2: %s' %(l3)
13 
14 # uma outra opção de criação de lista
15 l4 = ['a']*5
16 print 'lista l4: %s' %(l4)
17 
18 # removendo um item da lista pelo valor
19 l3.remove(2)
20 print 'lista l3 após elemento "2" removido : %s' %(l3)
21 
22 # removendo um item da lista pelo índice
23 l3.pop(0)
24 print 'lista l3 após removido elemento no índice 0 : %s' %(l3)
lista l1: [1, 'a', 2, 'b']
elemento no índice 2: 2
soma da lista l1 com l2: [1, 'a', 2, 'b', 3, 'c']
lista l4: ['a', 'a', 'a', 'a', 'a']
lista l3 após elemento "2" removido : [1, 'a', 'b', 3, 'c']
lista l3 após removido elemento no índice 0 : ['a', 'b', 3, 'c']

Tupla é análoga a lista, porém ela é imútavel, ou seja, uma vez criada, ela não pode ser modificada.

1 # construção de uma tupla
2 t1 = (1, 'a', 2, 'b')
3 print 'tupla l1: %s' %(t1.__str__())
4 
5 # para acessar um elemento da tupla, usa-se seu índice
6 i  = t1[2]
7 print 'elemento no índice 2: %d' %(i)
tupla l1: (1, 'a', 2, 'b')
elemento no índice 2: 2

Dicionário é um container com chaves e valores, ou seja, cada elemento do dicionário tem uma espécie de label associado a ele. E pode conter elementos de diferentes tipos.

 1 # construção de um dicionário
 2 d1 = {'a': 1, 'b': 2, 'c': 3}
 3 print 'dicionário d1: %s' %(d1.__str__())
 4 
 5 # outra maneira de criar um dicionário
 6 d1 = dict(a=1, b=2, c=3)
 7 print 'dicionário d1: %s' %(d1.__str__())
 8 
 9 # acessando um elemento pela chave
10 i = d1['a']
11 print 'elemento associado a chave "a": %d' %(i)
12 
13 # verificando quais são as chaves do dicionário
14 keys = d1.keys()
15 print 'chaves de d1: %s' %(keys)
16 
17 # verificando quais são os valores do dicionário
18 vals = d1.values()
19 print 'valores de d1: %s' %(vals)
dicionário d1: {'a': 1, 'c': 3, 'b': 2}
dicionário d1: {'a': 1, 'c': 3, 'b': 2}
elemento associado a chave "a": 1
chaves de d1: ['a', 'c', 'b']
valores de d1: [1, 3, 2]

Classe é usada para representar qualquer objeto ou idea. Uma classe possui atributos e métodos e ela pode ser entendida como um molde, a qual pode ser instanciada, gerando um objeto. É recomendável que quando se defina uma classe, ela herde de uma classe base do Python chamada Object, a qual já possui diversos atributos e métodos já definidos.

 1 # criando uma classe
 2 class Bola(object):
 3 
 4     # construtor
 5     def __init__(self, cor = 'azul'):
 6         # cor é um atributo
 7         self.cor = cor
 8 
 9     # método para alterar o atributo cor
10     def setarCor(self, valor):
11         self.cor = valor
12 
13 # criando uma instância da classe A
14 a = Bola()
15 print 'valor do atributo cor em a: %s' %(a.cor)
16 
17 # criando outra instância da classe A
18 b = Bola()
19 print 'valor do atributo cor em b: %s' %(b.cor)
20 
21 # alterando o atributo cor do objeto a
22 a.setarCor('verde')
23 print 'valor do atributo cor em a: %s' %(a.cor)
24 print 'valor do atributo cor em b: %s' %(b.cor)
valor do atributo cor em a: azul
valor do atributo cor em b: azul
valor do atributo cor em a: verde
valor do atributo cor em b: azul

Diferença entre lista e tupla

A mais nítida diferença entre lista e tupla é a imutabilidade da segunda. Ou seja, uma vez que uma tupla seja criada, ela não pode ser alterada. Porém existe, uma outra diferença, muito mais sútil, porém não menos importante. As listas são simples containers, podendo ter sequências homogẽneas, enquanto as tuplas são estruturas de dados heterogêneas, ou seja, seus índices contem uma semântica implícita e cada um possui um significado diferente. Exemplificando, faz muito mais sentido usar tuplas do que listas para retornar as coordenadas cartesianas de um objeto. Enquanto faz mais sentido usar listas para retornar quantos objetos estão nesse plano cartesiano.

Importância da identação em Python

A identação em Python serve para distinguir trechos de código que ficam em uma certa estrutura de dados ou em um escopo, a identação é então, um delimitador de estruturas ou escopo. Na linguagem de programação C/C++, esse delimitador é o {. A indentação permite que os códigos sejam elegantes e fáceis de ler.

Numpy

Com o Numpy é possível criar vetores de n dimensões com diversas capacidades de algebra linear e manipulação de matrizes. Ele também possui strings, variáveis lógicas, inteiros, pontos flutuantes e complexos de diferentes precisões como mostra a tabela a seguir

Tipo Descrição
string_ string do Python
int_ int do Python
byte char da linguagem C
short short da linguagem C
intc int da linguagem C
longlong long long da linguagem C
intp inteira de ponto flutuante
int8 int de 8 bits
int16 int de 16 bits
int32 int de 32 bits
int64 int de 64 bits
ubyte unsigned char da linguagem C
ushort unsigned short da linguagem C
uintc unsigned int da linguagem C
ulonglong unsigned long long da linguagem C
uintp unsigned int de ponto flutuante
uint8 unsigned int de 8 bits
uint16 unsigned int de 16 bits
uint32 unsigned int de 32 bits
uint64 unsigned int de 64 bits
float_ float do Python
single float da linguagem C
double double da linguagem C
longfloat long float da linguagem C
float16 float de 16 bits
float32 float de 32 bits
float64 float de 64 bits
float96 float de 96 bits
bool_ booleana do Python
bool8 booleana de 8 bits
complex_ número complexo do Python
clongfloat número complexo long float
complex64 número complexo duplo float de 32 bits
complex128 número complexo duplo float de 64 bits
 1 import numpy as np
 2 
 3 # criando uma matriz (2x3)
 4 a = np.array([[2,4,6], [3,5,7]])
 5 print 'matrix a: %s' %(a.__str__())
 6 
 7 # obtendo o tamanho das dimensões da matriz
 8 print 'tamanho das dimensões de a: %s' %(a.shape.__str__())
 9 
10 # obtendo a transposta da matriz
11 print 'transposta de a: %s' %(a.transpose().__str__())
12 
13 # achando o valor mínimo
14 print 'mínimo de a: %d' %(a.min())
15 
16 # e o valor máximo
17 print 'máximo de a: %d' %(a.max())
18 
19 # somando uma matriz com outra
20 b = np.array([[4,5,6],[8,9,10]])
21 c = a + b
22 print 'soma de a com b: %s' %(c.__str__())
23 
24 # redimensionando a matrix a para ser (6x1)
25 d = a.reshape(6,1)
26 print 'matriz a em 6x1: %s' %(d.__str__())
27 
28 # copiando as duas primeiras colunas da matriz a (slice)
29 e = a[0:2,0:2]
30 print '2 primeiras colunas de a: %s' %(e.__str__())
31 
32 # multiplicando a primeira linha de a por um escalar
33 f = a[0]*4
34 print 'primeira linha de a multiplicada por 4: %s' %(f.__str__())
matrix a: [[2 4 6]
 [3 5 7]]
tamanho das dimensões de a: (2, 3)
transposta de a: [[2 3]
 [4 5]
 [6 7]]
mínimo de a: 2
máximo de a: 7
soma de a com b: [[ 6  9 12]
 [11 14 17]]
matriz a em 6x1: [[2]
 [4]
 [6]
 [3]
 [5]
 [7]]
2 primeiras colunas de a: [[2 4]
 [3 5]]
primeira linha de a multiplicada por 4: [ 8 16 24]

Criando grafos

Usando o Graphviz

  • Grafo sem orientação
1. graph grafo1 {
2.     a -- {x y z};
3. }
/media/_xsb/courseIA368Q1S2012/thi_ex2/GRVIZ74626_001.png

  • Grafo com orientação
1. digraph grafo2 {
2.     a -> {x y z};
3. }
/media/_xsb/courseIA368Q1S2012/thi_ex2/GRVIZ74626_002.png

  • Grafo com peso nas arestas
1. digraph grafo3 {
2.     a -> x [label="1", len=1.00];
3.     a -> y [label="1", len=1.00];
4.     a -> z [label="1", len=1.00];
5. }
/media/_xsb/courseIA368Q1S2012/thi_ex2/GRVIZ74626_003.png

  • Grafo com diferentes formas nos nós e diferente aresta só entre a e z
01. digraph grafo4 {
02.     a -> x [label="1", len=1.00];
03.     a -> y [label="2", len=2.00];
04.     edge [style=dashed,color=red];
05.     a -> z [label="3", len=3.00];
06.     x [shape="box"]
07.     y [shape="pentagon"]
08.     z [shape="hexagon"]
09. 
10. }
/media/_xsb/courseIA368Q1S2012/thi_ex2/GRVIZ74626_004.png

Usando o Python

  • A primeira forma é usando a função mmgraphviz. Nessa função, passamos o texto que usamos na linguagem Graphviz e uma imagem é gerada. Passando o texto do último grafo criado acima, temos:
 1 s = """
 2     digraph grafo4 {
 3          a -> x [label="1", len=1.00];
 4          a -> y [label="2", len=2.00];
 5          edge [style=dashed,color=red];
 6          a -> z [label="3", len=3.00];
 7          x [shape="box"]
 8          y [shape="pentagon"]
 9          z [shape="hexagon"]
10 
11      }
12      """
13 
14 mmgraphviz(s, title='Grafo 4')
/media/_xsb/courseIA368Q1S2012/thi_ex2/GRVIZ74626_005.png

Grafo 4

  • A segunda forma é programando em Python através da função gven
 1 graph = gvgen.GvGen()
 2 graph.smart_mode = 1
 3 
 4 a = graph.newItem("a")
 5 x = graph.newItem("x")
 6 y = graph.newItem("y")
 7 z = graph.newItem("z")
 8 linkaa = graph.newLink(a, a)
 9 linkax = graph.newLink(a, x)
10 linkay = graph.newLink(a, y)
11 linkaz = graph.newLink(a, z)
12 
13 graph.styleAppend("linkax", "label", "1")
14 graph.styleAppend("linkax", "len", 1.00)
15 graph.styleApply("linkax", linkax)
16 
17 graph.styleAppend("linkay", "label", "2")
18 graph.styleAppend("linkay", "len", 2.00)
19 graph.styleApply("linkay", linkay)
20 
21 graph.styleAppend("linkaz", "label", "3")
22 graph.styleAppend("linkaz", "len", 3.00)
23 graph.styleAppend("linkaz", "color", "red")
24 graph.styleAppend("linkaz", "style", "dashed")
25 graph.styleApply("linkaz", linkaz)
26 
27 graph.styleAppend("x", "shape", "box")
28 graph.styleAppend("x", "color", "red")
29 graph.styleApply("x", x)
30 
31 graph.styleAppend("y", "shape", "pentagon")
32 graph.styleAppend("y", "color", "blue")
33 graph.styleApply("y", y)
34 
35 graph.styleAppend("z", "shape", "hexagon")
36 graph.styleAppend("z", "color", "green")
37 graph.styleApply("z", z)
38 
39 import StringIO
40 fd = StringIO.StringIO()
41 graph.dot(fd)
42 dottext = fd.getvalue()
43 
44 mmgraphviz(dottext, title='Grafo 5')
/media/_xsb/courseIA368Q1S2012/thi_ex2/GRVIZ74626_006.png

Grafo 5

Melhorando a função Larcos2MA

  • Nova função sem o for
1 from numpy import ones
2 
3 def Larcos2MA(L):
4     # n é a quantidade total de nós
5     n = L.max()+1
6     A = ones((n,n)) * float('inf')
7     A[L[:,0],L[:,1]]=1
8     return A