Aula Prática Algoritmos e Estrutura de Dados Avançado

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.

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

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.

https://colab.google/

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

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.

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.

https://colab.google/

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