Repositório de dados

Prévia do material em texto

<p>UNIVERSIDADE PITÁGORAS UNOPAR ANHANGUERA</p><p>CURSO</p><p>NOME</p><p>ATIVIDADE PRÁTICA</p><p>REPOSITÓRIO DE DADOS</p><p>CIDADE</p><p>ANO</p><p>NOME</p><p>ATIVIDADE PRÁTICA</p><p>REPOSITÓRIO DE DADOS</p><p>Trabalho apresentado à Universidade, como requisito parcial para a obtenção de média semestral nas disciplinas norteadoras do semestre letivo.</p><p>Tutor (a): INSERIR NOME</p><p>CIDADE</p><p>ANO</p><p>SUMÁRIO</p><p>INTRODUÇÃO	3</p><p>MÉTODOS E RESULTADOS	4</p><p>CONCLUSÃO	19</p><p>REFERÊNCIAS BIBLIOGRÁFICAS	20</p><p>INTRODUÇÃO</p><p>Neste portfólio de aula prática, exploram-se conceitos fundamentais de estruturas de dados e algoritmos aplicados a diferentes cenários de armazenamento e recuperação de informações. O foco principal é aprimorar a eficiência de sistemas que envolvem grandes volumes de dados, melhorando a experiência do usuário e a performance computacional.</p><p>A primeira atividade concentra-se em um cenário de e-commerce, no qual é necessário ordenar uma lista de produtos com base em critérios como preço, avaliação dos usuários, data de adição ao catálogo e categoria. A implementação de algoritmos de ordenação, como Bubble Sort, Quick Sort, Merge Sort e Heap Sort, tem o objetivo de comparar a eficiência dessas técnicas em um contexto realista, proporcionando uma análise prática sobre sua aplicabilidade em sistemas de recomendação.</p><p>Na segunda atividade, o desafio está relacionado ao desenvolvimento de um sistema de gerenciamento de dados utilizando a Árvore AVL, uma estrutura balanceada que otimiza operações de busca, inserção e remoção de dados. A implementação da árvore visa garantir que, mesmo com modificações frequentes, o tempo de acesso aos dados seja minimizado, o que é crucial para a eficiência em sistemas que lidam com grandes volumes de informações.</p><p>Por fim, a terceira atividade envolve a aplicação do algoritmo de Dijkstra em um sistema de navegação, que tem como objetivo encontrar a rota mais curta entre dois pontos. Nesta atividade, conceitos de grafos, algoritmos de caminho mínimo e estruturas como listas de adjacência e filas de prioridade são aplicados para garantir que o sistema calcule rotas de maneira eficiente.</p><p>O Google Colab, uma plataforma colaborativa baseada na nuvem, foi utilizado para a implementação e teste das soluções, proporcionando um ambiente de fácil acesso e execução de código sem a necessidade de configurações complexas. Este portfólio oferece uma visão abrangente das técnicas algorítmicas e de balanceamento de dados aplicadas a problemas práticos de repositórios de dados.</p><p>MÉTODOS E RESULTADOS</p><p>Atividade 1 – Noções de Ordenação</p><p>Esta atividade prática teve como objetivo desenvolver e implementar uma solução para a criação, manipulação e ordenação de uma lista de produtos utilizando algoritmos de ordenação clássicos. Para isso, utilizamos o ambiente de desenvolvimento do Google Colab, que oferece recursos computacionais e uma interface colaborativa diretamente acessível via navegador. A atividade envolveu a criação de uma classe Produto, geração de dados aleatórios para 1000 produtos e a comparação de diferentes algoritmos de ordenação. Além disso, foi realizado um estudo sobre o desempenho desses algoritmos com base em critérios específicos de ordenação, utilizando a biblioteca time para a medição de tempos de execução.</p><p>1. Desenvolvimento</p><p>1.1. Preparação dos dados</p><p>Inicialmente, foi desenvolvida a classe Produto, com os seguintes atributos: nome (string), preco (float), avaliacao (float, com valores entre 0 e 5), data_adicao (datetime) e categoria (string). A classe foi criada de forma a permitir uma fácil manipulação dos objetos Produto, facilitando a posterior ordenação e análise.</p><p>class Produto:</p><p>def __init__(self, nome, preco, avaliacao, data_adicao, categoria):</p><p>self.nome = nome</p><p>self.preco = preco</p><p>self.avaliacao = avaliacao</p><p>self.data_adicao = data_adicao</p><p>self.categoria = categoria</p><p>def __repr__(self):</p><p>return f"{self.nome}: {self.preco}, {self.avaliacao}, {self.data_adicao}, {self.categoria}"</p><p>1.2. Geração de dados</p><p>Foi escrito um script para gerar uma lista de 1000 produtos com valores aleatórios utilizando as bibliotecas random e datetime. Os atributos de cada produto foram preenchidos com valores gerados dinamicamente:</p><p>· Nome: Um nome gerado concatenando "Produto" com um número único.</p><p>· Preço: Um valor decimal aleatório entre 10 e 1000.</p><p>· Avaliação: Um valor decimal aleatório entre 0 e 5.</p><p>· Data_Adição: Uma data aleatória dentro do último ano.</p><p>· Categoria: Uma string representando uma categoria de 1 a 5.</p><p>Abaixo está o código que gera os produtos:</p><p>import random</p><p>import datetime</p><p>def gerar_produtos(n):</p><p>nomes = ["Produto" + str(i) for i in range(n)]</p><p>precos = [round(random.uniform(10, 1000), 2) for _ in range(n)]</p><p>avaliacoes = [round(random.uniform(0, 5), 2) for _ in range(n)]</p><p>datas = [datetime.datetime.now() - datetime.timedelta(days=random.randint(0, 365)) for _ in range(n)]</p><p>categorias = ["Categoria" + str(random.randint(1, 5)) for _ in range(n)]</p><p>produtos = [Produto(nomes[i], precos[i], avaliacoes[i], datas[i], categorias[i]) for i in range(n)]</p><p>return produtos</p><p>produtos = gerar_produtos(1000)</p><p>1.3. Implementação de algoritmos de ordenação</p><p>Foram implementados quatro algoritmos de ordenação: Bubble Sort, Quick Sort, Merge Sort e Heap Sort. Cada um desses algoritmos foi adaptado para ordenar a lista de produtos com base nos critérios solicitados.</p><p>Exemplo da implementação do Bubble Sort:</p><p>def bubble_sort(lista, key):</p><p>n = len(lista)</p><p>for i in range(n):</p><p>for j in range(0, n-i-1):</p><p>if key(lista[j]) > key(lista[j+1]):</p><p>lista[j], lista[j+1] = lista[j+1], lista[j]</p><p>return lista</p><p>1.4. Critérios de ordenação</p><p>Os produtos foram ordenados segundo os seguintes critérios:</p><p>· Preço: de forma ascendente e descendente.</p><p>· Avaliação: de forma ascendente e descendente.</p><p>· Data de Adição: mais recente primeiro e mais antigo primeiro.</p><p>· Categoria: ordem alfabética.</p><p>A implementação das funções de ordenação para cada critério utilizou funções chave (key) apropriadas para acessar os atributos específicos dos objetos Produto.</p><p>Exemplo de ordenação por preço utilizando Quick Sort:</p><p>def quick_sort(lista, key):</p><p>if len(lista) key(pivot)]</p><p>return quick_sort(menores, key) + [pivot] + quick_sort(maiores, key)</p><p>produtos_ordenados_preco = quick_sort(produtos, key=lambda x: x.preco)</p><p>1.5. Comparação de desempenho</p><p>Para medir o desempenho dos algoritmos, utilizou-se a biblioteca time para cronometrar o tempo de execução de cada algoritmo sob diferentes critérios de ordenação. Os tempos foram registrados e posteriormente comparados.</p><p>import time</p><p>inicio = time.time()</p><p>bubble_sort(produtos, key=lambda x: x.preco)</p><p>fim = time.time()</p><p>print(f"Tempo de execução do Bubble Sort: {fim - inicio:.5f} segundos")</p><p>1.6. Análise de resultados</p><p>A análise dos resultados revelou variações significativas no desempenho dos algoritmos, de acordo com a complexidade temporal de cada um:</p><p>· Bubble Sort: Como esperado, foi o algoritmo mais lento, com tempo de execução proporcional ao número de comparações (O(n²)).</p><p>· Quick Sort: Apresentou excelente desempenho na maioria dos casos, com complexidade média de (O(n log n).</p><p>· Merge Sort: Foi consistente, com tempo de execução constante para todos os critérios, sendo eficiente em listas grandes (O(n log n)).</p><p>· Heap Sort: Também demonstrou eficiência semelhante ao Merge Sort, embora ligeiramente mais lento em alguns cenários específicos.</p><p>A atividade prática permitiu aplicar os conceitos de geração de dados, ordenação e análise de desempenho em um cenário realista de manipulação de objetos complexos. A comparação dos algoritmos de ordenação revelou que, enquanto algoritmos como o Bubble Sort são inadequados para grandes volumes de dados, algoritmos como o Quick Sort e o Merge Sort se mostraram</p><p>eficientes e adequados para diferentes critérios de ordenação. A utilização do Google Colab facilitou o desenvolvimento e execução do código, fornecendo um ambiente colaborativo e de fácil acesso.</p><p>Atividade 2 – Árvores AVL</p><p>Esta atividade prática teve como objetivo a implementação de uma árvore AVL, um tipo de árvore binária de busca que mantém seu balanceamento através de rotações, garantindo uma estrutura eficiente para inserção, remoção e busca de dados. A árvore AVL foi escolhida por sua capacidade de manter o tempo de busca em O(log n), mesmo após múltiplas inserções e remoções. Utilizando o Google Colab como ambiente de desenvolvimento, foi possível escrever, testar e visualizar o comportamento da árvore AVL.</p><p>1. Desenvolvimento</p><p>1.1. Definição da estrutura da árvore AVL</p><p>A implementação inicial da estrutura da árvore AVL envolveu a criação de duas classes: Node e AVLTree. A classe Node foi utilizada para representar cada nó da árvore, armazenando as informações do nó e seus ponteiros para os filhos esquerdo e direito. Além disso, a classe armazenou a altura do nó, fundamental para o processo de balanceamento.</p><p>A classe AVLTree foi responsável pela gestão da árvore, contendo métodos para inserção, remoção e busca de nós, além de garantir o balanceamento da estrutura através de rotações.</p><p>Implementação da classe Node:</p><p>class Node:</p><p>def __init__(self, key):</p><p>self.key = key</p><p>self.left = None</p><p>self.right = None</p><p>self.height = 1</p><p>Implementação da classe AVLTree:</p><p>class AVLTree:</p><p>def get_height(self, node):</p><p>if not node:</p><p>return 0</p><p>return node.height</p><p>def update_height(self, node):</p><p>node.height = 1 + max(self.get_height(node.left), self.get_height(node.right))</p><p>1.2. Implementação de operações básicas</p><p>A segunda parte da atividade envolveu a implementação das operações básicas da árvore AVL: inserção, remoção e busca. A inserção e a remoção foram particularmente desafiadoras, pois, após cada operação, a árvore precisou ser reequilibrada para manter as propriedades de uma árvore AVL.</p><p>· Inserção:</p><p>A inserção em uma árvore AVL segue a mesma lógica de uma árvore binária de busca, mas com a adição do balanceamento após cada inserção. O código abaixo demonstra a inserção de um nó, seguida do cálculo do fator de balanceamento e, se necessário, a realização de rotações.</p><p>def insert(self, root, key):</p><p>if not root:</p><p>return Node(key)</p><p>elif key 1 and key root.right.key:</p><p>return self.left_rotate(root)</p><p># Rotação dupla direita-esquerda</p><p>if balance > 1 and key > root.left.key:</p><p>root.left = self.left_rotate(root.left)</p><p>return self.right_rotate(root)</p><p># Rotação dupla esquerda-direita</p><p>if balance root.key:</p><p>root.right = self.delete(root.right, key)</p><p>else:</p><p>if not root.left:</p><p>return root.right</p><p>elif not root.right:</p><p>return root.left</p><p>temp = self.get_min_value_node(root.right)</p><p>root.key = temp.key</p><p>root.right = self.delete(root.right, temp.key)</p><p>self.update_height(root)</p><p>balance = self.get_balance(root)</p><p># Aplicar rotações conforme o balanceamento</p><p>if balance > 1 and self.get_balance(root.left) >= 0:</p><p>return self.right_rotate(root)</p><p>if balance > 1 and self.get_balance(root.left) 0:</p><p>root.right = self.right_rotate(root.right)</p><p>return self.left_rotate(root)</p><p>return root</p><p>1.3. Balanceamento da árvore</p><p>O balanceamento da árvore AVL foi garantido através da implementação das rotações simples e duplas. Foram implementadas as seguintes rotações:</p><p>· Rotação simples à direita.</p><p>· Rotação simples à esquerda.</p><p>· Rotação dupla esquerda-direita.</p><p>· Rotação dupla direita-esquerda.</p><p>As rotações são necessárias quando o fator de balanceamento de um nó fica fora da faixa permitida. Abaixo está a implementação da rotação simples à esquerda:</p><p>def left_rotate(self, z):</p><p>y = z.right</p><p>T2 = y.left</p><p>y.left = z</p><p>z.right = T2</p><p>self.update_height(z)</p><p>self.update_height(y)</p><p>return y</p><p>1.4. Testes de validação</p><p>Foram implementados testes para verificar a corretude das operações de inserção, remoção e busca em diferentes cenários. Testes específicos para inserção de nós em ordem ascendente e descendente foram realizados para garantir o balanceamento correto da árvore.</p><p>Exemplo de teste para inserção em ordem ascendente:</p><p>avl = AVLTree()</p><p>root = None</p><p>for i in range(1, 6):</p><p>root = avl.insert(root, i)</p><p>A árvore permaneceu balanceada após cada inserção, conforme esperado, com rotações sendo aplicadas automaticamente para corrigir qualquer desbalanceamento.</p><p>1.5. Visualização da árvore</p><p>Uma função foi implementada para imprimir a estrutura da árvore AVL, permitindo a visualização do balanceamento e das relações entre os nós.</p><p>def pre_order(self, root):</p><p>if not root:</p><p>return</p><p>print(f"{root.key} (H={root.height})", end=" ")</p><p>self.pre_order(root.left)</p><p>self.pre_order(root.right)</p><p>Essa função foi útil para validar visualmente a correção das rotações e o balanceamento da árvore.</p><p>A implementação da árvore AVL mostrou-se desafiadora, especialmente no que diz respeito ao balanceamento após inserções e remoções. No entanto, o uso das rotações garantiu que a árvore se mantivesse balanceada e eficiente, com tempo de busca, inserção e remoção em O(log n). O Google Colab se mostrou uma plataforma eficiente para o desenvolvimento, testes e visualização da árvore AVL, permitindo o acompanhamento contínuo do comportamento da estrutura conforme as operações foram realizadas. A árvore AVL é uma solução valiosa para cenários que exigem alta eficiência na manipulação de grandes conjuntos de dados.</p><p>Atividade 3 – Caminhos Mínimos</p><p>1. Definição da estrutura do Grafo</p><p>O primeiro passo da atividade foi a criação da estrutura do grafo. Utilizando uma lista de adjacência, a classe Graph foi definida para representar o grafo, onde cada nó é uma chave de um dicionário, e o valor associado é uma lista de tuplas que indicam os vizinhos e o peso das arestas. Essa estrutura foi escolhida por sua eficiência tanto em termos de armazenamento quanto de operações de consulta de vizinhos.</p><p>Exemplo de estrutura da classe Graph:</p><p>class Graph:</p><p>def __init__(self):</p><p>self.vertices = {}</p><p>def add_edge(self, u, v, weight):</p><p>if u not in self.vertices:</p><p>self.vertices[u] = []</p><p>if v not in self.vertices:</p><p>self.vertices[v] = []</p><p>self.vertices[u].append((v, weight))</p><p>self.vertices[v].append((u, weight)) # Caso seja um grafo não-direcionado</p><p>2. Implementação do algoritimo de Dijkstra</p><p>O algoritmo de Dijkstra foi implementado utilizando uma fila de prioridade (min-heap) para garantir que, a cada iteração, o próximo nó processado seja o que possui a menor distância acumulada desde o nó de origem. Para a fila de prioridade, utilizou-se o módulo heapq do Python, que permite a manipulação</p><p>eficiente da estrutura de heap.</p><p>Exemplo de implementação do algoritmo de Dijkstra:</p><p>import heapq</p><p>def dijkstra(graph, start):</p><p>distances = {vertex: float('infinity') for vertex in graph.vertices}</p><p>distances[start] = 0</p><p>priority_queue = [(0, start)]</p><p>while priority_queue:</p><p>current_distance, current_vertex = heapq.heappop(priority_queue)</p><p>if current_distance > distances[current_vertex]:</p><p>continue</p><p>for neighbor, weight in graph.vertices[current_vertex]:</p><p>distance = current_distance + weight</p><p>if distance .</p><p>Arano, Silvia et. al. “La comunidad Recursos y datos primarios de la Universitat Pompeu Fabra: los repositorios institucionales como infraestructuras científicas: estudio de caso”. Revista Española de Documentación Científica, v. 34, n. 3, 2011, pp. 385-407, doi: .</p><p>Budapest Open Access Initiative. Budapest Open Access Initiative. 2002, doi: .</p><p>Costa, Michelli Pereira da e Lima, Fernando César Lima. “Repositórios institucionais da América Latina e o acesso aberto à informação científica”. IBICT, 2017, .</p><p>Lynch, C.; Lippincott, J. “Institutional repository deployment in the United States as of early 2005”. D-lib Magazine, v. 11, n. 9, 2005, .</p><p>19</p>