Aula Prática Algoritmos e estrutura de dados avançado
ROTEIRO DE AULA PRÁTICA
NOME DA DISCIPLINA: ALGORITMOS E ESTRUTURA DE DADOS AVANÇADO
Unidade: U1_ FUNDAMENTOS DE ALGORITMOS
Aula: A4_ NOÇÕES DE ORDENAÇÃO
OBJETIVOS
Definição dos objetivos da aula prática:
Implementar e comparar diferentes algoritmos de ordenação em um cenário de aplicação realista.
O objetivo é entender a eficiência e a aplicabilidade de cada algoritmo em diferentes situações.
SOLUÇÃO DIGITAL
Computador com acesso à Internet para uso do Google Colab
O Google Colab, ou Colaboratory, é uma plataforma gratuita baseada na nuvem oferecida pelo
Google. Ela fornece um ambiente de notebook interativo e colaborativo que permite a criação e
execução de código diretamente no navegador, sem a necessidade de configurar ou instalar
qualquer software no seu computador.
PROCEDIMENTOS PRÁTICOS
Procedimento/Atividade nº 1
Atividade proposta:
Você trabalha em uma empresa de e-commerce e precisa ordenar uma lista de produtos com
base em diferentes critérios para melhorar a experiência do usuário e a eficiência do sistema de
recomendação. A lista de produtos inclui informações como preço, avaliação dos usuários, data
de adição ao catálogo e categoria.
Procedimentos para a realização da atividade:
1. Preparação dos Dados:
– Crie uma classe `Produto` com os seguintes atributos:
– `nome`: string
– `preco`: float
Público3
– `avaliacao`: float (0 a 5)
– `data_adicao`: datetime
– `categoria`: string
2. Geração de Dados:
– Escreva um script para gerar uma lista de 1000 produtos aleatórios. Utilize bibliotecas como
`random` e `datetime` para preencher os atributos de cada produto.
3. Implementação de Algoritmos de Ordenação:
– Implemente os seguintes algoritmos de ordenação:
– Bubble Sort
– Quick Sort
– Merge Sort
– Heap Sort
4. Critérios de Ordenação:
– Implemente funções de ordenação para os seguintes critérios:
– Por preço (ascendente e descendente)
– Por avaliação (ascendente e descendente)
– Por data de adição (mais recente primeiro e mais antigo primeiro)
– Por categoria (ordem alfabética)
5. Comparação de Desempenho:
– Meça e compare o tempo de execução de cada algoritmo para cada critério de ordenação
utilizando a biblioteca `time`.
6. Análise de Resultados:
– Escreva um relatório discutindo a eficiência de cada algoritmo de ordenação nos diferentes
critérios. Considere a complexidade temporal de cada algoritmo e como eles se comportam com
os dados gerados.
Dicas
– Utilize a função `sorted()` do Python para verificar a corretude das suas implementações.
– A biblioteca `time` pode ser utilizada para medir o tempo de execução de um bloco de código.
– A biblioteca `datetime` pode ajudar na manipulação de datas.
– Para visualização, você pode utilizar gráficos de barras para mostrar o tempo de execução de
cada algoritmo em diferentes cenários. A biblioteca `matplotlib` pode ser útil aqui.
Público4
Código Inicial:
import random
import datetime
import time
class Produto:
def __init__(self, nome, preco, avaliacao, data_adicao, categoria):
self.nome = nome
self.preco = preco
self.avaliacao = avaliacao
self.data_adicao = data_adicao
self.categoria = categoria
def __repr__(self):
return f”{self.nome}: {self.preco}, {self.avaliacao}, {self.data_adicao}, {self.categoria}”
def gerar_produtos(n):
nomes = [“Produto” + str(i) for i in range(n)]
precos = [round(random.uniform(10, 1000), 2) for _ in range(n)]
avaliacoes = [round(random.uniform(0, 5), 2) for _ in range(n)]
datas = [datetime.datetime.now() – datetime.timedelta(days=random.randint(0, 365)) for _ in
range(n)]
categorias = [“Categoria” + str(random.randint(1, 5)) for _ in range(n)]
produtos = [Produto(nomes[i], precos[i], avaliacoes[i], datas[i], categorias[i]) for i in range(n)]
return produtos
# Exemplo de geração de produtos
produtos = gerar_produtos(1000)
for produto in produtos[:10]: # Mostrar os 10 primeiros produtos
print(produto)
Checklist:
• Preparação dos Dados
• Geração de Dados
• Implementação de Algoritmos de Ordenação
Público5
• Critérios de Ordenação
• Comparação de Desempenho
• Análise de Resultados
RESULTADOS
Resultados de Aprendizagem:
Espera-se que o aluno seja capaz de entender a implementação e a análise dos principais
algoritmos de ordenação aplicados a um cenário realista, proporcionando uma compreensão
prática e teórica sólida sobre a eficiência dos diferentes métodos de ordenação.
ESTUDANTE, VOCÊ DEVERÁ ENTREGAR
Descrição orientativa sobre a entregada da comprovação da aula prática:
• Para comprovar a realização da atividade, é necessario entregar um arquivo com os
códigos criados e um PDF com o relatório de análise.
Unidade: U2_ ÁRVORES
Aula: A1_ ÁRVORES AVL
OBJETIVOS
Definição dos objetivos da aula prática:
Entender os conceitos de balanceamento e rotação em árvores binárias de busca implementando
uma Árvore AVL em Python, incluindo inserção, remoção e busca de nós, além de garantir que a
árvore permaneça balanceada após cada operação.
SOLUÇÃO DIGITAL
Computador com acesso à Internet para uso do Google Colab
O Google Colab, ou Colaboratory, é uma plataforma gratuita baseada na nuvem oferecida pelo
Google. Ela fornece um ambiente de notebook interativo e colaborativo que permite a criação e
execução de código diretamente no navegador, sem a necessidade de configurar ou instalar
qualquer software no seu computador.
Público6
PROCEDIMENTOS PRÁTICOS
Procedimento/Atividade nº 1
Atividade proposta:
Você trabalha em uma empresa de tecnologia que está desenvolvendo um sistema de
gerenciamento de dados. Para otimizar as operações de busca, inserção e remoção, você foi
designado para implementar uma Árvore AVL que manterá os dados balanceados.
Procedimentos para a realização da atividade:
1. Definição da Estrutura da Árvore AVL:
– Crie uma classe `Node` para representar cada nó da árvore.
– Crie uma classe `AVLTree` para gerenciar as operações na árvore.
2. Implementação de Operações Básicas:
– Implementar a inserção de nós na árvore AVL.
– Implementar a remoção de nós da árvore AVL.
– Implementar a busca de nós na árvore AVL.
3. Balanceamento da Árvore:
– Implementar as rotações à esquerda e à direita para manter a árvore balanceada.
– Garantir que, após cada inserção e remoção, a árvore permanece uma AVL válida.
4. Testes de Validação:
– Escreva testes para validar a inserção, remoção e busca em diferentes cenários.
– Testar casos de borda como inserção de nós em ordem ascendente ou descendente para
verificar o balanceamento.
5. Visualização da Árvore:
– Implementar uma função para imprimir a árvore de forma que seja fácil visualizar sua estrutura
e balanceamento.
Dicas
– Utilize a propriedade de altura dos nós para ajudar no balanceamento.
– Uma árvore AVL é uma árvore binária de busca onde a diferença de altura entre as subárvores
esquerda e direita de qualquer nó é no máximo 1.
– As rotações (simples e duplas) são cruciais para manter a árvore balanceada.
Público7
Checklist:
• Definição da Estrutura da Árvore AVL:
• Implementação de Operações Básicas:
• Balanceamento da Árvore:
• Testes de Validação:
• Visualização da Árvore:
RESULTADOS
Resultados de Aprendizagem:
Espera-se que o aluno seja capaz de entender a implementação de uma Árvore AVL em Python
com operações de inserção, remoção e busca, além do balanceamento automático,
demonstrando habilidade prática.
ESTUDANTE, VOCÊ DEVERÁ ENTREGAR
Descrição orientativa sobre a entregada da comprovação da aula prática:
Para comprovar a realização da atividade, é necessario entregar um relatório em PDF com:
• Códigos criados
• Prints de tela com os resultados da execução
• Um breve relatório de análise.
Unidade: U3_ GRAFOS
Aula: A3_ CAMINHOS MÍNIMOS
OBJETIVOS
Definição dos objetivos da aula prática:
Compreender os conceitos de grafos, algoritmos de busca de caminhos mínimos e estruturas de
dados como listas de adjacência e filas de prioridade.
SOLUÇÃO DIGITAL
Computador com acesso à Internet para uso do Google Colab
O Google Colab, ou Colaboratory, é uma plataforma gratuita baseada na nuvem oferecida pelo
Google. Ela fornece um ambiente de notebook interativo e colaborativo que permite a criação e
execução de código diretamente no navegador, sem a necessidade de configurar ou instalar
qualquer software no seu computador.
Público8
PROCEDIMENTOS PRÁTICOS
Procedimento/Atividade nº 1
Atividade proposta:
Você está desenvolvendo um sistema de navegação para uma aplicação de mapas. Para
encontrar a rota mais curta entre dois pontos, você precisa implementar o algoritmo de Dijkstra.
Procedimentos para a realização da atividade:
1. Definição da Estrutura do Grafo:
• Crie uma classe Graph para representar o grafo usando uma lista de adjacência.
• Cada aresta do grafo deve ter um peso associado.
2. Implementação do Algoritmo de Dijkstra:
• Implemente o algoritmo de Dijkstra para encontrar o caminho mais curto a partir de
um nó de origem para todos os outros nós do grafo.
• Utilize uma fila de prioridade (min-heap) para otimizar a escolha do próximo nó com
a menor distância.
3. Função para Encontrar o Caminho Mínimo:
• Implemente uma função que, dado um nó de origem e um nó de destino, retorne o
caminho mínimo e a distância mínima entre esses nós.
4. Testes de Validação:
• Escreva testes para validar o algoritmo com diferentes grafos e nós de origem e
destino.
• Teste casos de borda, como grafos desconectados ou nós sem arestas.
5. Visualização do Caminho:
• Implemente uma função para imprimir o caminho mínimo de forma legível.
Dicas
• Utilize um dicionário para representar o grafo onde as chaves são os nós e os valores são
listas de tuplas (vizinho, peso).
• A fila de prioridade pode ser implementada usando o módulo heapq do Python.
Público9
• Mantenha um dicionário de distâncias mínimas e um dicionário de predecessores para
reconstruir o caminho
RESULTADOS
Resultados de Aprendizagem:
Espera-se que o aluno seja capaz de entender a implementação de um algoritmo que encontra
caminhos mínimos em grafos.
ESTUDANTE, VOCÊ DEVERÁ ENTREGAR
Descrição orientativa sobre a entregada da comprovação da aula prática:
Para comprovar a realização da atividade, é necessario entregar um relatório em PDF com:
• Códigos criados
• Prints de tela com os resultados da execução
• Um breve relatório explicando todo o procedimento realizado.
Unidade: U4_ COMPRESSÃO DE DADOS E OUTRAS ESTRUTURAS
Aula: A1_ HEAP
OBJETIVOS
Definição dos objetivos da aula prática:
Aprender a construir uma lista de prioridade, inserir e remover elementos no heap, e alterar a
prioridade de elementos existentes.
SOLUÇÃO DIGITAL
Infraestrutura mínima necessária para execução.
Computador com acesso à Internet para uso do Google Colab
O Google Colab, ou Colaboratory, é uma plataforma gratuita baseada na nuvem oferecida pelo
Google. Ela fornece um ambiente de notebook interativo e colaborativo que permite a criação e
execução de código diretamente no navegador, sem a necessidade de configurar ou instalar
qualquer software no seu computador.
Público10
PROCEDIMENTOS PRÁTICOS
Procedimento/Atividade nº 1
Atividade proposta:
Você deverá implementar uma lista de prioridade usando um heap (min-heap) em Python.
Procedimentos para a realização da atividade:
1. Construção da Lista de Prioridade: Construa a classe `PriorityQueue`
– Implemente uma lista de prioridade usando um min-heap.
– crie uma função para inicializar a lista de prioridade.
– Implemente funções para inserir elementos na lista de prioridade.
– Implemente funções para remover o elemento com a menor prioridade.
– Implemente uma função para alterar a prioridade de um elemento existente.
2. Teste da Lista de Prioridade: Implemente a função `test_priority_queue` para testar a lista de
prioridade
– Inicialize uma lista de prioridade.
– Adicione tarefas com diferentes prioridades e exiba a lista.
– Insira novas tarefas na lista de prioridade.
– Remova a tarefa com a menor prioridade e exiba a lista após cada remoção.
– Altere a prioridade de uma tarefa existente e exiba a lista.
– Verifique os resultados e assegure-se de que as operações de inserção, remoção e alteração
de prioridade funcionam conforme esperado.
Dicas
– Use a estrutura de min-heap do módulo `heapq` para gerenciar a lista de prioridade.
– Mantenha um dicionário (`entry_finder`) para rastrear os itens na lista e facilitar a alteração de
prioridade.
– Use um contador (`counter`) para diferenciar entre tarefas com a mesma prioridade.
RESULTADOS
Resultados de Aprendizagem:
Espera-se que o aluno seja capaz de entender a implementação de um algoritmo de lista de
prioridades com heap.
Público11
ESTUDANTE, VOCÊ DEVERÁ ENTREGAR
Descrição orientativa sobre a entregada da comprovação da aula prática:
Para comprovar a realização da atividade, é necessario entregar um relatório em PDF com:
• Códigos criados
• Prints de tela com os resultados da execução
• Um breve relatório explicando todo o procedimento realizado
Aula Prática Algoritmos e estrutura de dados avançado
