ALGORITMOS E ESTRUTURA DE DADOS AVANÇADO

ROTEIRO DE AULA PRÁTICA

CLIQUE AQUI! PARA VISUALIZAR O MANUAL!

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.

https://colab.google/

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

3

Público

– `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.

4

Público

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

5

Público

•

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.

https://colab.google/

6

Público

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.

7

Público

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.

8

Público

https://colab.google/

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.

9

Público

•

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.

https://colab.google/

10

Público

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.

11

Público

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.