informática para engenharia aula 9 e 10

Prévia do material em texto

INFORMÁTICA Aula 9: Estruturas e Tipos Abstratos de Dados
# OBJETIVO:Analisar as diferentes formas de representar os dados a partir do
comportamento esperado pelo usuário;
Avaliar o uso de técnicas para criação e manipulação de estruturas de dados abstratas.
#Estrutura de dados e algoritmos
Sabemos que os algoritmos manipulam uma grande variedade de informações a partir de
um conjunto sistemático de regras. Tais regras manipulam dados que representam algum
fenômeno do mundo real, como os números inteiros.
#No entanto, em algumas situações, esse é um fator limitante para a modelagem e
implementação de diversos problemas de várias áreas do conhecimento. Operações com
estruturas complexas, como vetores e matrizes, são recorrentes nas áreas de exatas, como
a Engenharia.
#O Python fornece uma variedade de estruturas de dados internas úteis, como listas (lists),
conjuntos (sets) e dicionários (dictionaries). Na maior parte, o uso dessas estruturas é
simples.
#Por meio da biblioteca NumPy, é possível utilizar estruturas do tipo vetor (array) e matriz
NumPy
#discutir estruturas de dados comuns e algoritmos envolvendo dados, o tratamento é dado
às várias estruturas de dados contidas no módulo.
Estruturas de dados heterogêneas
Lists
#Lista é uma sequência ordenada (indexada) de itens. Trata-se de um dos tipos de dados
mais usados no Python e é muito flexível. Nenhum item em uma lista precisa ser do mesmo
tipo.
→ Lista tem tamanhos variados, internamente se tem lista cadeado (ponderada), é uma
coleção de dados, uso de colchete, apnd e inserto.O índice inicia a partir do 0 em Python.
#Declarar uma lista é bastante simples. Itens separados por vírgulas são colocados entre
colchetes [ ].
>>> lst = [5, 7.2, ‘python’]
#Uma vez que as listas são mutáveis, você pode atualizar elementos de listas, informando a
posição (índice) nos colchetes.
#del para remover um conteúdo da lista se souber o que remover, ou o método remove ( )
se você não souber.
#A inserção de itens na lista pode ser realizada de duas maneiras: no final da lista ou
informando a posição. O comando para inserir um elemento no fim da lista é o append( ).
#Para inserir um valor em determinada posição (índice), a função é inserir (índice, valor).
>>> depois10h=tmp[3:]
>>> print(depois10h)
[22.4, 21.8, 19.1]
Tuplas
#As tuplas são objetos imutáveis, ou seja, uma vez criadas, não podemos
modificá-las,implica a impossibilidade de fazer atribuições a um objeto imutável. Para alterar
o valor de um objeto imutável, deve criar outro objeto para armazenar esse novo valor.
#Definição:As tuplas são usadas para proteger os dados e – geralmente mais rápidas que a
lista – não podem ser alteradas dinamicamente, São definidas entre parênteses (), em que
os itens são separados por vírgulas.
#Podemos usar o operador colchetes [ ] para extrair itens, mas não podemos alterar seu
valor.
>>> 2 in t1 #verifica se o valor 2 está na tupla True
>>> t1[2] #exibe o conteúdo da posição 2 da tupla 3
>>> t1[0:4] #exibe os 4 primeiros elementos da tupla (1, 2, 3, 4)
>>> len(t1) #exibe o tamanho da tupla 9
>>> min(t1) #exibe o menor valor da tupla 1
>>> max(t1) #exibe o maior valor da tupla 10
>>> t1.count(5) #exibe a quantidade de vezes que o valor 5 aparece na tupla 1
Sets | Conjuntos
#Os sets (ou conjuntos) são estruturas para construir e manipular coleções não ordenadas de
elementos únicos. Usos comuns incluem testes de associação, remoção de duplicatas de uma
sequência e computação de operações matemáticas padrão em conjuntos como interseção, união,
diferença e diferença simétrica.
#Muito utilizada numa série de constantes;
#principais características dos conjuntos: Os elementos não são armazenados em uma ordem
específica + Não contêm elementos repetidos.
#não é imutáveis mas os elementos deles sim, elementos são indexados (grupo),
diferentemente das listas, os sets não suportam indexação nem fatiamento (slicing). Apesar de
serem mutáveis, os sets não podem possuir itens mutáveis.
MÉTODO INTERNO (BUILT-IN)
>>> A = {1, 2, 3, 4}
>>> print(A)
{1, 2, 3, 4}
>>> A = {} #set vazio
FUNÇÃO SET( )
>>> A = set([1, 2, 3, 4])
>>> print(A)
{1, 2, 3, 4}
>>> A = set() #set vazio
#Uma vez que não suportam índices, os parâmetros passados nas funções add( ), update( ) e discard( )
são os próprios valores. Para verificarmos se determinado elemento pertence ao grupo, podemos utilizar o
operador in.
#A verificação se determinado conjunto é um subconjunto de outros sets é realizada por meio do
comando issubset(): , De maneira similar, podemos checar se um conjunto é superconjunto do outro por
meio do método issuperset().A disjunção entre dois conjuntos pode ser verificada pelo comando
isdisjoint(). Considera-se que dois conjuntos são disjuntos se eles tiverem interseção nula.
#Várias são as operações possíveis com sets, como as da Teoria Clássica dos Conjuntos (união,
interseção e diferença)
União
>>> print(A.union(B))
{1, 2, 3, 4, 5, 6}
Interseção
>>>
print(A.intersection(B)
{3, 4}
Diferença
>>>
print(A.difference(B))
{1, 2}
>>> print(B.difference(A)
#O uso dos sets pode ser muito útil quando quisermos identificar valores repetidos em listas!
Estruturas de dados homogêneas
Arrays
#Em problemas de computação aplicados à Engenharia, é muito comum o uso de vetores ou arrays.
Semelhantes às listas do Python, arrays são estruturas de dados semelhantes às listas do Python, no
entanto não tão flexíveis.
#Os arrays são estruturas unidimensionais, em que todos os elementos devem ser de um mesmo tipo,
tipicamente numérico, como int ou float. Em contrapartida, o uso de arrays é muito mais eficiente e facilita
a computação de grandes volumes de dados numéricos. Isso faz com que arrays sejam particularmente
úteis em computação científica.
#Apesar de a biblioteca NumPy possibilitar a criação de estruturas multidimensionais, trataremos os
arrays como uma estrutura de uma dimensão (rank 1).
Criando Arrays
#Manipulação de arrays, importar a biblioteca NumPy.
>>> import numpy as np
>>> a = np.array([1,2,3]) #cria um array de rank 1
>>> print(a)
[1 2 3]
Fatiamento de arrays
#Assim como as listas, podemos realizar o fatiamento (slicing) de arrays da mesma maneira.
>>> arr = np.arange(10)
>>> arr[:5] #primeiros cinco elementos
>>> arr[4:7] #meio do array
>>> arr[::2] #dois em dois elementos a partir do início
>>> arr[a::2] #dois em dois elementos a partir do índice 1
>>> arr[::-1] #ordem inversa
Iterando arrays
#A maneira mais fácil de percorrer os elementos do array é pelo comando for, o pacote NumPy contém um
iterador chamado nditer, que percorre de forma eficiente os elementos de um array. Podemos converter
sequência em Python em um array, pode ser convertida em um array pelo comando asarray() TUPLAS TBM
>>> arr = np.arange(0,20,3)
>>> for elemento in arr: #Para cada elemento no arr
... print(elemento)
...
Matrizes
Considerando a construção unidimensional (os arrays), o modo de construção de matrizes é o mesmo dos
arrays, tendo como única diferença a inclusão de mais dimensões, chamada de matriz estruturas com
duas ou mais dimensões.
Criando uma matriz
>>> m = np.array([[1, 2, 3], [4, 5, 6]]) #criando uma matriz de dimensão 2 x 3
>>> print(m.ndim) #exibindo o número de dimensões da matriz 2
>>> print(m.shape) #exibindo a dimensão da matriz (linha,coluna) (2,3)
>>> m1 = np.arange(6).reshape(2,3) #criando um array de tamanho e depois
reajustando # para uma matriz 2x3
>>> print(m1)
>>> m2 = np.ones([2,2]) #criando matriz 2x2 de 1’s
>>> print(m2)
>>> m3 = np.random.random((2,2)) #criando uma matriz com valores aleatórios
>>> print(m3)
Iterando matrizes
Assim como os arrays, podemos utilizar a função nditer(), que exibirá os números da matriz seguindo uma
ordem (da esquerda para a direita, de cima para baixo), podemos controlar sua ordem para percorrer os
elementos por coluna, ou F-order.
>>> m = np.arange(6).reshape(2,3)
>>> print(m) #exibindo a matriz original
[[0 1 2]
[3 4 5]]
>>> for i in np.nditer(m): #exibindo os elementos por linha da esquerdapara a
# direita
... print(i)
0
1,2,3,4,5.
>>> for i in np.nditer(m, order=’F’):
#matriz-identidade e matriz transposta, até operações aritméticas de matrizes são largamente utilizadas
em computação matemática.
#Obter uma matriz transposta (aT) no Python é muito simples. Basta inserir o .T (de transposta) logo após
o nome da matriz, conforme código a seguir:
>>> a = np.arange(6).reshape(2,3) #cria uma matriz 2x3
>>> print(a)
[[0 1 2]
[3 4 5]]
>>> print(a.T) #exibe a transporta da matriz a
[[0 3]
[1 4]
[2 5]]
#De maneira simples, uma matriz-identidade pode ser definida simplesmente pela função eye(ordem)
OBS.:As lists e tuplas possuem uma ordem associada, ou seja, os elementos possuem uma posição (logo,
são indexadas). Também podem misturar, em sua estrutura, números, letras e demais tipos,
caracterizando-os como estruturas de dados heterogêneas.
*Por qual motivo a saída do código não é igual à estrutura de dados dataScientist?
Uma vez que a estrutura de dados utilizada foi o set (conjunto), isso implica que os valores não sejam
armazenados exatamente na ordem em que foram estipulados.
INFORMÁTICA 10 (Estrutura de dados avançadas)
#Objetivos
•Analisar a aplicabilidade das estruturas de dados, tópicos avançados de Lists em Python;
•Avaliar o uso de técnicas para criação e manipulação de estruturas de dados abstratas, contendo tipos
primitivos e abstratos de dados, por estruturas lineares, como filas e listas encadeadas.
Lists avançadas em Python
# ilustra os vários métodos de lista Python.
Filas
Nesta seção, ajudaremos você a entender a estrutura de dados de uma fila e como implementá-la.
Esses conceitos são frequentemente testados em entrevistas e possuem uma ampla variedade de
aplicativos. A implementação em Python de um Fila (Queue) é relativamente simples quando
comparada com outras linguagens.
#As filas estão abertas em ambas as extremidades, elementos de significado são adicionados por trás
e removidos da frente.
#O elemento a ser adicionado primeiro é removido primeiro (First In First Out - FIFO).
#Se todos os elementos forem removidos, a fila estará vazia e, se você tentar remover elementos de
uma fila vazia, um aviso ou uma mensagem de erro será emitida.
#Se a fila estiver cheia e você adicionar mais elementos à fila, uma mensagem de aviso ou de erro
deverá ser lançada.
#O ponto de entrada e o de saída são diferentes em uma Fila;
#Enfileirar significa adicionar um elemento a uma fila;
#Desenfileirar significa remover um elemento de uma fila;
#Acesso aleatório não é permitido – você não pode adicionar nem remover um elemento do meio.
Implementação usando List
→Definir uma classe Queue e adicionar métodos para executar:
1-Enfileirar elementos para o início da Fila e emitir um aviso se estiver cheio;
2-Desenfileirar elementos do final da Fila e emitir um aviso se estiver vazio;
3-Avaliar o tamanho da fila;
4-Imprimir todos os elementos da fila.
#Resumidamente, podemos conceituar uma classe como um módulo composto por uma série de
funções (métodos).
Como fazer uma lista:
>>> class Fila:
... def
__init__(self):
#Construtor cria uma lista
…
self.fila = list()
…
Listas encadeadas
Uma lista encadeada é frequentemente comparada a arrays (vetores). Enquanto um array possui um
tamanho fixo, uma lista encadeada pode ter seus elementos alocados.
Quais são as vantagens e desvantagens dessas características?
Vantagens : Uma lista vinculada economiza memória, pois aloca somente o espaço necessário para os valores
serem armazenados;
Em arrays, você precisa definir um tamanho de array antes de preenchê-lo com valores, o que pode potencialmente
desperdiçar memória;
Os nós da lista vinculada podem residir em qualquer parte da memória. Enquanto um array exige que uma
sequência de memória seja iniciada, desde que as referências sejam atualizadas, cada nó da lista vinculada pode
ser movido com flexibilidade para um endereço diferente.
Desvantagens
A principal desvantagem é o tempo de pesquisa linear. Ao procurar um valor em uma lista vinculada, você precisa
começar do início da cadeia e verificar um elemento de cada vez para um valor que esteja procurando. Se a lista
vinculada tiver n elementos, isso pode levar até n hora. Pelo contrário, muitas linguagens permitem pesquisas
constantes em arrays.
#destacar dois pontos estruturais fundamentais:
1- Uma lista encadeada consiste de nós (ou nodos).
2- Cada nó consiste em um valor e um ponteiro para outro nó.
As operações básicas em uma lista encadeada são: inserir um nó na lista, excluir um nó da lista, pesquisa um valor na
lista e retornar o tamanho da lista.
O nó inicial de uma lista encadeada é o cabeçalho, é uma cadeia de valores conectada com endereços que
apontam para outros nodos (daí o motivo para o nome de ‘ponteiros’).
#Definimos a lista encadeada (linked list) com seu construtor padrão e o cabeçalho (head).
#Uma vez criado, ele aponta para o nó que referenciado por head, e, por fim, o head passa a apontar para o nó
recém-criado.
#Já o método size é mais simples. A partir do início da lista, aqui pela variável current, cada nó da lista é percorrido
até que se chegue ao fim.
#A implementação do método delete busca pelo valor informado para chegar ao fim. Vamos dividir em dois blocos:
1- O valor não foi encontrado na lista (current.data==data seja False).
2- O valor foi encontrado na lista (current.data==data seja True).
#utilizamos uma variável auxiliar chamada previous (anterior), q guarda a posição corrente. Assim, a variável
current passa a apontar para o próximo nó, temos armazenadas as referências para dois nós contíguos.
Continuando.