Algoritimos e Estruras de Dados

Público Roteiro Aula Prática 2 Público 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 httpscolabgoogle PROCEDIMENTOS PRÁTICOS ProcedimentoAtividade nº 1 Atividade proposta Você trabalha em uma empresa de ecommerce 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 dataadicao 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 initself nome preco avaliacao dataadicao categoria selfnome nome selfpreco preco selfavaliacao avaliacao selfdataadicao dataadicao selfcategoria categoria def reprself return fselfnome selfpreco selfavaliacao selfdataadicao selfcategoria def gerarprodutosn nomes Produto stri for i in rangen precos roundrandomuniform10 1000 2 for in rangen avaliacoes roundrandomuniform0 5 2 for in rangen datas datetimedatetimenow datetimetimedeltadaysrandomrandint0 365 for in rangen categorias Categoria strrandomrandint1 5 for in rangen produtos Produtonomesi precosi avaliacoesi datasi categoriasi for i in rangen return produtos Exemplo de geração de produtos produtos gerarprodutos1000 for produto in produtos10 Mostrar os 10 primeiros produtos printproduto 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 Esperase 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 httpscolabgoogle 6 Público PROCEDIMENTOS PRÁTICOS ProcedimentoAtividade 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 Esperase 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 httpscolabgoogle PROCEDIMENTOS PRÁTICOS ProcedimentoAtividade 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 minheap 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 Esperase 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 httpscolabgoogle 10 Público PROCEDIMENTOS PRÁTICOS ProcedimentoAtividade nº 1 Atividade proposta Você deverá implementar uma lista de prioridade usando um heap minheap 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 minheap 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 testpriorityqueue 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 assegurese de que as operações de inserção remoção e alteração de prioridade funcionam conforme esperado Dicas Use a estrutura de minheap do módulo heapq para gerenciar a lista de prioridade Mantenha um dicionário entryfinder 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 Esperase 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 CIDADE 2025 NOME DO ALUNO RA ALGORITMOS E ESTRUTURA DE DADOS AVANÇADO UNIVERSIDADE ANHANGUERA CENTRO DE EDUCAÇÃO À DISTÂNCIA CIÊNCIA DA COMPUTAÇÃO BACHARELADO CIDADE 2025 ALGORITMOS E ESTRUTURA DE DADOS AVANÇADO Roteiro Aula Prática apresentado a Universidade Anhanguera como requisito para obtenção de média para a disciplina de Algoritmos E Estrutura De Dados Avançado Tutora à Distância NOME DO ALUNO Explainability in AI How can you tell if an AI model is making decisions for the right reasons Developing explainability tools helps stakeholders trust and understand AI decisions Why It Matters Ensures transparency and accountability Helps diagnose and correct errors Builds user trust Supports regulatory compliance Types of Explainability Global Overall model behavior Local Specific decision explanations Techniques Feature importance Saliency maps Counterfactual explanations Example Applications Healthcare diagnostics Fraud detection Autonomous driving Credit scoring Challenges Complexity of models Tradeoff with accuracy Diverse stakeholder needs Future Directions Interactive explanations Multimodal explanations Personalized explainability Summary Explainability is key to responsible AI enabling better decisionmaking and fostering trust between humans and AI systems SUMÁRIO 1 INTRODUÇÃO3 2 DESENVOLVIMENTO4 3 CONCLUSÃO24 1 INTRODUÇÃO Ao longo deste trabalho tive a oportunidade de explorar e implementar conceitos fundamentais de algoritmos e estruturas de dados avançados dividindo a experiência em quatro atividades principais Na primeira parte foquei na comparação de diferentes algoritmos de ordenação como Bubble Sort Quick Sort Merge Sort e Heap Sort utilizando critérios específicos como preço avaliação data de adição e categoria para ordenar uma lista de produtos Essa etapa foi essencial para entender na prática a eficiência e as limitações de cada algoritmo em cenários variados Na segunda atividade mergulhei no mundo das árvores AVL uma estrutura que combina busca eficiente com balanceamento automático Desenvolvi as operações de inserção remoção e busca garantindo que a propriedade AVL fosse mantida Além disso implementei rotações simples e duplas para corrigir desbalanceamentos validando a estrutura com testes como inserções em ordens ascendente descendente e aleatória bem como remoções de nós específicos incluindo a raiz A terceira parte do trabalho foi dedicada aos grafos onde implementei o algoritmo de Dijkstra para calcular os caminhos mínimos em grafos ponderados Estruturei o grafo com listas de adjacência e desenvolvi funcionalidades para exibir tanto as distâncias mínimas quanto o caminho mais curto entre dois nós Essa etapa me proporcionou uma visão clara de como algoritmos de grafos são aplicados em problemas reais como sistemas de navegação e redes Por fim na quarta atividade trabalhei com a implementação de uma lista de prioridade utilizando heap binário Desenvolvi uma classe que permite inserir elementos alterar prioridades e remover o elemento de maior prioridade de forma eficiente Realizei testes com diferentes cenários como atualização de prioridade e manipulação de listas vazias garantindo o funcionamento robusto da estrutura Essas atividades interligadas pelo objetivo de aplicar conceitos teóricos em soluções práticas não só consolidaram meus conhecimentos mas também reforçaram minha capacidade de lidar com problemas de maneira estruturada e eficiente Cada etapa representou um desafio único contribuindo para meu aprendizado e minha evolução como estudante na área de algoritmos e estruturas de dados avançados 3 2 DESENVOLVIMENTO 21 ATIVIDADE PROPOSTA 01 NOÇÕES DE ORDENAÇÃO Atividade Proposta Atuei como desenvolvedor em uma empresa de ecommerce onde fui responsável por implementar um sistema de ordenação para melhorar a experiência do usuário e a eficiência do sistema de recomendação O objetivo era ordenar uma lista de produtos com base em diferentes critérios como preço avaliação dos usuários data de adição ao catálogo e categoria Procedimentos Realizados 1 Preparação dos Dados Para iniciar o projeto criei uma classe chamada Produto com os seguintes atributos nome string preco float avaliacao float valores entre 0 e 5 dataadicao datetime categoria string Essa classe foi projetada para representar cada produto da lista de maneira estruturada 2 Geração de Dados Escrevi um script em Python para gerar uma lista de 1000 produtos com valores aleatórios Para isso utilizei as bibliotecas random e datetime Cada produto foi preenchido com valores variados Nomes foram gerados sequencialmente ex Produto1 Produto2 Preços e avaliações foram gerados aleatoriamente dentro de intervalos predefinidos Datas de adição foram calculadas com base em intervalos aleatórios de dias retroativos Categorias foram atribuídas de forma aleatória entre cinco opções disponíveis Código 4 import random import datetime class Produto def initself nome preco avaliacao dataadicao categoria selfnome nome selfpreco preco selfavaliacao avaliacao selfdataadicao dataadicao selfcategoria categoria def reprself return fNome selfnome Preço Rselfpreco2f fAvaliação selfavaliacao1f5 fData de Adição selfdataadicaostrftimedmY fCategoria selfcategoria def gerarprodutosn nomes fProduto i randomchoiceBásico Premium Luxo for i in rangen precos roundrandomuniform10 1000 2 for in rangen avaliacoes roundrandomuniform0 5 1 for in rangen datas datetimedatetimenow datetimetimedeltadaysrandomrandint0 365 for in rangen categorias randomchoices Eletrônicos Livros Vestuário Móveis Alimentos kn return Produtonomesi precosi avaliacoesi datasi categoriasi for i in rangen Gerar 10 produtos para exibição produtos gerarprodutos10 Exibir detalhes dos produtos for produto in produtos printproduto 5 Figura 1 Tela de Saídas Fonte Autoria Própria 3 Implementação de Algoritmos de Ordenação Implementei os seguintes algoritmos para ordenar a lista de produtos Bubble Sort Focado na simplicidade mas menos eficiente em grandes listas Quick Sort Utilizado por sua eficiência em muitos casos práticos Merge Sort Aplicado pela sua estabilidade e previsibilidade Heap Sort Escolhido por sua eficiência em memória constante 4 Critérios de Ordenação Implementei funções para ordenar os produtos com base nos seguintes critérios Preço Ascendente e descendente Avaliação Ascendente e descendente Data de adição Mais recente primeiro e mais antigo primeiro Categoria Ordem alfabética Essas funções tornaram possível organizar os produtos de acordo com as necessidades específicas do sistema 5 Comparação de Desempenho Utilizei a biblioteca time para medir o tempo de execução de cada algoritmo em cada critério de ordenação Com os dados coletados criei gráficos para comparar o desempenho import random import datetime import time from heapq import heappush heappop Classe Produto class Produto 6 def initself nome preco avaliacao dataadicao categoria selfnome nome selfpreco preco selfavaliacao avaliacao selfdataadicao dataadicao selfcategoria categoria def reprself return fselfnome Preço Rselfpreco2f fAvaliação selfavaliacao5 fData selfdataadicaostrftimedmY fCategoria selfcategoria Gerar produtos def gerarprodutosn nomes fProduto i for i in rangen precos roundrandomuniform10 1000 2 for in rangen avaliacoes roundrandomuniform0 5 1 for in rangen datas datetimedatetimenow datetimetimedeltadaysrandomrandint0 365 for in rangen categorias randomchoicesEletrônicos Livros Vestuário Móveis Alimentos kn return Produtonomesi precosi avaliacoesi datasi categoriasi for i in rangen Algoritmos de Ordenação def bubblesortarr key reverseFalse n lenarr for i in rangen for j in range0 ni1 if keyarrj keyarrj1 reverse arrj arrj1 arrj1 arrj def quicksortarr key reverseFalse if lenarr 1 return arr pivot keyarr0 left x for x in arr1 if keyx pivot reverse right x for x in arr1 if keyx pivot reverse return quicksortleft key reverse arr0 quicksortright key reverse def mergesortarr key reverseFalse if lenarr 1 mid lenarr 2 L mergesortarrmid key reverse R mergesortarrmid key reverse i j k 0 while i lenL and j lenR 7 if keyLi keyRj reverse arrk Li i 1 else arrk Rj j 1 k 1 while i lenL arrk Li i 1 k 1 while j lenR arrk Rj j 1 k 1 return arr def heapsortarr key reverseFalse Usar heapq com tuplas para evitar comparações diretas de objetos heap counter 0 Identificador único para evitar comparações diretas for item in arr heappushheap keyitem if not reverse else keyitem counter item counter 1 sortedarr heappopheap2 for in rangelenheap return sortedarr Critérios de Ordenação def criterioprecoproduto return produtopreco def criterioavaliacaoproduto return produtoavaliacao def criteriodataadicaoproduto return produtodataadicaotimestamp def criteriocategoriaproduto return produtocategoria Comparação de Desempenho def medirtempofunc arr key reverseFalse start timetime if func heapsort result funcarr key reverse heapsort retorna uma nova lista else 8 funcarr key reverse Os outros algoritmos alteram a lista original result arr end timetime return result end start Execução e Análise produtos gerarprodutos1000 algoritmos Bubble Sort bubblesort Quick Sort quicksort Merge Sort mergesort Heap Sort heapsort criterios Preço ascendente criteriopreco False Preço descendente criteriopreco True Avaliação ascendente criterioavaliacao False Avaliação descendente criterioavaliacao True Data mais recente primeiro criteriodataadicao True Data mais antigo primeiro criteriodataadicao False Categoria ordem alfabética criteriocategoria False printComparação de desempenho for nomealg algoritmo in algoritmositems for nomecrit criterio ordem in criteriositems produtoscopia produtos tempo medirtempoalgoritmo produtoscopia criterio ordem printfnomealg com nomecrit tempo4f segundos Saída de tela Comparação de desempenho Bubble Sort com Preço ascendente 03406 segundos Bubble Sort com Preço descendente 03311 segundos Bubble Sort com Avaliação ascendente 03028 segundos Bubble Sort com Avaliação descendente 02102 segundos Bubble Sort com Data mais recente primeiro 05970 segundos Bubble Sort com Data mais antigo primeiro 05898 segundos Bubble Sort com Categoria ordem alfabética 01762 segundos Quick Sort com Preço ascendente 00045 segundos Quick Sort com Preço descendente 00044 segundos Quick Sort com Avaliação ascendente 00075 segundos Quick Sort com Avaliação descendente 00082 segundos Quick Sort com Data mais recente primeiro 00165 segundos 9 Quick Sort com Data mais antigo primeiro 00129 segundos Quick Sort com Categoria ordem alfabética 00332 segundos Merge Sort com Preço ascendente 00051 segundos Merge Sort com Preço descendente 00048 segundos Merge Sort com Avaliação ascendente 00048 segundos Merge Sort com Avaliação descendente 00048 segundos Merge Sort com Data mais recente primeiro 00132 segundos Merge Sort com Data mais antigo primeiro 00120 segundos Merge Sort com Categoria ordem alfabética 00046 segundos Heap Sort com Preço ascendente 00010 segundos Heap Sort com Preço descendente 00009 segundos Heap Sort com Avaliação ascendente 00009 segundos Heap Sort com Avaliação descendente 00009 segundos Heap Sort com Data mais recente primeiro 00013 segundos Heap Sort com Data mais antigo primeiro 00012 segundos Heap Sort com Categoria ordem alfabética 00009 segundos Análise de Desempenho Bubble Sort Resumo O Bubble Sort apresentou os maiores tempos de execução em todas as categorias confirmando sua ineficiência para grandes conjuntos de dados Melhores Resultados Categoria ordem alfabética 01762 segundos Avaliação descendente 02102 segundos Piores Resultados Data mais recente primeiro 05970 segundos Data mais antigo primeiro 05898 segundos Observação A complexidade de tempo On2On2On2 é evidente tornandoo inadequado para listas extensas Quick Sort Resumo O Quick Sort foi muito eficiente com tempos de execução significativamente menores do que o Bubble Sort Melhores Resultados Preço descendente 00044 segundos Preço ascendente 00045 segundos Piores Resultados Categoria ordem alfabética 00332 segundos Data mais recente primeiro 00165 segundos Observação O Quick Sort é rápido devido à sua complexidade OnlognOn 10 log nOnlogn mas pode apresentar variações dependendo da escolha do pivô Merge Sort Resumo O Merge Sort apresentou tempos estáveis e rápidos em todas as categorias sendo comparável ao Quick Sort Melhores Resultados Categoria ordem alfabética 00046 segundos Avaliação ascendente 00048 segundos Piores Resultados Data mais recente primeiro 00132 segundos Data mais antigo primeiro 00120 segundos Observação A estabilidade e consistência do Merge Sort são evidentes com tempos uniformes adequados para cenários onde a estabilidade da ordenação é crítica Heap Sort Resumo O Heap Sort foi o mais rápido entre os algoritmos testados com tempos extremamente baixos em todas as categorias Melhores Resultados Categoria ordem alfabética 00009 segundos Avaliação ascendente e descendente 00009 segundos Piores Resultados Data mais recente primeiro 00013 segundos Data mais antigo primeiro 00012 segundos Observação A complexidade OnlognOn log nOnlogn e a eficiência em memória tornam o Heap Sort ideal para grandes conjuntos de dados Tabela 1 Comparação Geral Algoritmo Tempo Médio segundos Observações Bubble Sort 03854 Ineficiente inapropriado para grandes listas Quick Sort 00123 Rápido mas com variações em alguns critérios Merge Sort 00083 Consistente e estável com bom desempenho 11 Heap Sort 00010 Extremamente rápido e eficiente Recomendações Para grandes conjuntos de dados Utilize Heap Sort ou Merge Sort pela eficiência e consistência Evite Bubble Sort pois é inadequado para tamanhos maiores Quando a estabilidade é necessária Prefira Merge Sort já que mantém a ordem relativa de itens iguais Para conjuntos pequenos ou moderados Quick Sort é uma boa opção com tempos rápidos e simplicidade de implementação 22 ATIVIDADE PROPOSTA 02 IMPLEMENTAÇÃO DE ÁRVORES AVL Definição da Estrutura da Árvore AVL Para a implementação criei duas classes principais Node Representa cada nó da árvore AVL armazenando a chave os ponteiros para os nós filhos esquerdo e direito e a altura do nó AVLTree Gerencia as operações da árvore como inserção remoção busca e balanceamento Implementação de Operações Básicas Inserção Implementei o método insert que adiciona nós à árvore Após cada inserção o balanceamento é verificado e as rotações necessárias são aplicadas para garantir que a árvore permaneça equilibrada Remoção Implementei o método delete que remove nós da árvore Assim como na inserção o balanceamento é ajustado após cada remoção Busca Adicionei o método search que percorre a árvore para localizar um nó com a chave desejada Balanceamento da Árvore 12 Rotações Implementei as rotações simples e duplas Rotação à direita LL Corrige desbalanceamento à esquerda Rotação à esquerda RR Corrige desbalanceamento à direita Rotação dupla esquerdadireita LR Corrige desbalanceamento complexo à esquerda Rotação dupla direitaesquerda RL Corrige desbalanceamento complexo à direita Altura dos Nós A altura de cada nó foi atualizada após cada operação de inserção ou remoção garantindo que a diferença entre as subárvores esquerda e direita nunca excedesse 1 Testes de Validação Inserções em Ordem Ascendente Inserir valores em sequência crescente para verificar o balanceamento automático da árvore print Teste Inserção em ordem ascendente ascendente 1 2 3 4 5 6 7 root None for valor in ascendente root avlinsertroot valor printÁrvore AVL após inserções em ordem ascendente inordertraversalroot Saída Esperada A árvore deve se balancear automaticamente com rotações apropriadas mantendo a propriedade AVL Inserções em Ordem Descendente Inserir valores em sequência decrescente para verificar o comportamento da árvore ao balancear subárvores à esquerda print Teste Inserção em ordem descendente descendente 7 6 5 4 3 2 1 root None for valor in descendente 13 root avlinsertroot valor printÁrvore AVL após inserções em ordem descendente inordertraversalroot Saída Esperada A árvore deve realizar rotações à direita para manter o balanceamento Inserções em Ordem Aleatória Inserir valores em uma sequência aleatória para validar a capacidade da árvore de manterse balanceada independentemente da ordem de inserção print Teste Inserção em ordem aleatória aleatorio 10 5 20 15 25 30 1 root None for valor in aleatorio root avlinsertroot valor printÁrvore AVL após inserções em ordem aleatória inordertraversalroot Saída Esperada A árvore deve continuar balanceada com subárvores equilibradas Remoções de Folhas Remover um nó folha sem filhos e verificar se a árvore permanece balanceada print Teste Remoção de folha root avldeleteroot 1 Supondo que 1 seja uma folha printÁrvore AVL após a remoção de uma folha 1 inordertraversalroot Saída Esperada A remoção de um nó folha não deve afetar o balanceamento global da árvore Remoções de Nós Intermediários Remover um nó com um ou dois filhos e verificar o rebalanceamento print Teste Remoção de nó intermediário root avldeleteroot 20 Supondo que 20 seja um nó intermediário printÁrvore AVL após a remoção de um nó intermediário 20 14 inordertraversalroot Saída Esperada A árvore deve se ajustar com rotações se necessário para manter a propriedade AVL Remoção da Raiz Remover o nó raiz e verificar se a nova raiz é escolhida corretamente e se a árvore permanece balanceada print Teste Remoção da raiz root avldeleteroot 10 Supondo que 10 seja a raiz printÁrvore AVL após a remoção da raiz 10 inordertraversalroot Saída Esperada A árvore deve eleger uma nova raiz mantendo o balanceamento Verificação da Propriedade AVL Após cada operação verificar se a diferença de altura entre as subárvores de cada nó é no máximo 1 def verificaavlroot if not root return True balance avlgetbalanceroot if absbalance 1 return False return verificaavlrootleft and verificaavlrootright print Verificando a propriedade AVL após operações if verificaavlroot printA propriedade AVL está preservada else printErro A propriedade AVL foi violada Saída Esperada A propriedade AVL está preservada Conclusão dos Testes 15 Inserções A árvore AVL lidou adequadamente com diferentes ordens de inserção mantendo o balanceamento Remoções A remoção de folhas nós intermediários e da raiz foi bem sucedida com a árvore se rebalanceando automaticamente Propriedade AVL Em todos os testes a diferença de altura entre subárvores nunca excedeu 1 Visualização da Árvore Implementei um método para exibir a estrutura da árvore no console facilitando a verificação do balanceamento e da disposição dos nós Teste de funcionamento da árvore AVL if name main avl AVLTree root None Inserindo valores na árvore valores 10 20 30 40 50 25 printInserindo valores na árvore AVL for valor in valores printfInserindo valor root avlinsertroot valor Exibir a árvore em ordem def inordertraversalroot if root inordertraversalrootleft printfrootkey Altura rootheight end inordertraversalrootright print Árvore AVL após inserções em ordem inordertraversalroot print Removendo um valor printRemovendo o valor 20 root avldeleteroot 20 print Árvore AVL após a remoção de 20 em ordem inordertraversalroot print 16 Tela de Saída Inserindo valores na árvore AVL Inserindo 10 Inserindo 20 Inserindo 30 Inserindo 40 Inserindo 50 Inserindo 25 Árvore AVL após inserções em ordem 10 Altura 1 20 Altura 2 25 Altura 1 30 Altura 3 40 Altura 2 50 Altura 1 Removendo o valor 20 Árvore AVL após a remoção de 20 em ordem 10 Altura 1 25 Altura 2 30 Altura 3 40 Altura 2 50 Altura 1 Resultados A árvore AVL demonstrou eficiência em operações de busca inserção e remoção O balanceamento automático foi validado garantindo uma complexidade OlognOlog nOlogn para todas as operações 23 ATIVIDADE PROPOSTA 03 ALGORITMO DE CAMINHOS MÍNIMOS GRAFOS Definição da Estrutura do Grafo Implementei uma classe Graph para representar o grafo utilizando listas de adjacência Cada nó é armazenado como uma chave no dicionário As arestas são representadas como uma lista de tuplas vizinho peso class Graph def initself selfgraph def addedgeself u v weight if u not in selfgraph selfgraphu if v not in selfgraph selfgraphv 17 selfgraphuappendv weight selfgraphvappendu weight Para grafos não direcionados Implementação do Algoritmo de Dijkstra O algoritmo foi implementado para calcular as distâncias mínimas a partir de um nó de origem para todos os outros nós do grafo import heapq def dijkstragraph start distances node floatinf for node in graph distancesstart 0 priorityqueue 0 start while priorityqueue currentdistance currentnode heapqheappoppriorityqueue if currentdistance distancescurrentnode continue for neighbor weight in graphcurrentnode distance currentdistance weight if distance distancesneighbor distancesneighbor distance heapqheappushpriorityqueue distance neighbor return distances Função para Encontrar o Caminho Mínimo Para exibir o caminho mínimo entre dois nós implementei uma função que rastreia os predecessores dos nós def dijkstrawithpathgraph start end distances node floatinf for node in graph distancesstart 0 priorityqueue 0 start predecessors node None for node in graph while priorityqueue currentdistance currentnode heapqheappoppriorityqueue if currentnode end break 18 if currentdistance distancescurrentnode continue for neighbor weight in graphcurrentnode distance currentdistance weight if distance distancesneighbor distancesneighbor distance predecessorsneighbor currentnode heapqheappushpriorityqueue distance neighbor path current end while current is not None pathinsert0 current current predecessorscurrent return distancesend path Testes de Validação Criar o Grafo Criei um grafo de exemplo com nós e arestas para validar a funcionalidade Criando o grafo de exemplo graph Graph edges A B 4 A C 2 B C 5 B D 10 C D 3 C E 4 D E 1 D F 8 E F 6 for u v weight in edges graphaddedgeu v weight printGrafo criado printgraphgraph Tela de saída Grafo criado A B 4 C 2 B A 4 C 5 D 10 C A 2 B 5 D 3 E 4 D B 10 C 3 E 1 F 8 E C 4 D 1 F 6 F D 8 E 6 Executar o Algoritmo 19 Calculei os caminhos mínimos a partir do nó A para todos os outros nós print Caminhos mínimos a partir do nó A distances dijkstragraphgraph A for node distance in distancesitems printfDistância até node distance Tela de Saída Caminhos mínimos a partir do nó A Distância até A 0 Distância até B 4 Distância até C 2 Distância até D 5 Distância até E 6 Distância até F 12 Encontrar Caminho Mínimo Encontrei o caminho mínimo entre dois nós específicos como A e F print Caminho mínimo entre A e F distance path dijkstrawithpathgraphgraph A F printfDistância distance printfCaminho joinpath Tela de Saída Caminho mínimo entre A e F Distância 12 Caminho A C E F 24 ATIVIDADE PROPOSTA 04 LISTA DE PRIORIDADE COM HEAP Implementação da Lista de Prioridade A classe PriorityQueue foi implementada para gerenciar a lista de prioridade com suporte para inserção remoção do elemento com maior prioridade e alteração da prioridade de elementos import heapq class PriorityQueue def initself selfheap selfentryfinder 20 selfREMOVED removedtask selfcounter 0 def addtaskself task priority0 Adiciona uma nova tarefa ou atualiza a prioridade de uma existente if task in selfentryfinder selfremovetasktask count selfcounter entry priority count task selfentryfindertask entry heapqheappushselfheap entry selfcounter 1 def removetaskself task Marca uma tarefa como removida entry selfentryfinderpoptask entry1 selfREMOVED def poptaskself Remove e retorna a tarefa com a maior prioridade while selfheap priority count task heapqheappopselfheap if task is not selfREMOVED del selfentryfindertask return task raise KeyErrorpop from an empty priority queue def isemptyself Verifica se a lista de prioridade está vazia return not selfentryfinder Testes de Operações Inserção de Tarefas Adicionei tarefas à lista de prioridade com diferentes níveis de prioridade print Teste Inserção de tarefas pq PriorityQueue pqaddtaskTarefa 1 priority3 pqaddtaskTarefa 2 priority5 pqaddtaskTarefa 3 priority1 pqaddtaskTarefa 4 priority4 printTarefas adicionadas com sucesso Tela de Saída 21 Teste Inserção de tarefas Tarefas adicionadas com sucesso Alteração de Prioridade Atualizei a prioridade de uma tarefa existente print Teste Alteração de prioridade pqaddtaskTarefa 1 priority6 Atualiza a prioridade de Tarefa 1 printPrioridade de Tarefa 1 atualizada Tela de Saída Teste Alteração de prioridade Prioridade de Tarefa 1 atualizada Remoção do Elemento com Maior Prioridade Removi tarefas da lista sempre retornando a tarefa com maior prioridade print Teste Remoção de tarefas while not pqisempty task pqpoptask printfTarefa removida task Tela de Saída Teste Remoção de tarefas Tarefa removida Tarefa 3 Tarefa removida Tarefa 4 Tarefa removida Tarefa 2 Tarefa removida Tarefa 1 Tentativa de Remover de uma Lista Vazia Verifiquei o comportamento ao tentar remover de uma lista de prioridade vazia print Teste Remoção de uma lista vazia try pqpoptask except KeyError as e printErro capturado e 22 Tela de Saída print Teste Remoção de uma lista vazia try pqpoptask except KeyError as e printErro capturado e A lista de prioridade implementada com heap binário demonstrou funcionalidade completa para Inserção e atualização de elementos Remoção do elemento com maior prioridade Tratamento seguro para listas vazias Essa implementação é eficiente e pode ser aplicada em cenários que demandam gerenciamento dinâmico de prioridades 23 3 CONCLUSÃO A realização deste trabalho foi uma experiência enriquecedora que consolidou minha compreensão sobre algoritmos e estruturas de dados avançados Cada uma das atividades desenvolvidas trouxe desafios específicos e contribuiu para aprofundar meu entendimento teórico e prático Na primeira atividade a comparação entre os algoritmos de ordenação destacou a importância de escolher a técnica adequada para cada situação considerando fatores como a eficiência e a complexidade de implementação Foi possível perceber como estruturas aparentemente simples como listas de produtos podem ser otimizadas com o uso de algoritmos mais eficientes A implementação das árvores AVL na segunda atividade reforçou a relevância de estruturas que mantêm o balanceamento dinâmico As operações de inserção remoção e busca juntamente com as rotações para corrigir desbalanceamentos mostraram como é possível garantir eficiência em operações frequentes mesmo em conjuntos de dados maiores Na terceira parte o estudo dos grafos e a aplicação do algoritmo de Dijkstra ampliaram minha visão sobre problemas complexos de caminhos mínimos Além de compreender a lógica por trás do algoritmo a prática com grafos ponderados evidenciou a aplicabilidade dessa ferramenta em cenários do mundo real como logística e redes Finalmente na quarta atividade a criação de uma lista de prioridade utilizando heap binário destacou a importância de estruturas eficientes para gerenciamento dinâmico de tarefas A capacidade de manipular prioridades de forma ágil mostrouse essencial em diversas aplicações como sistemas de agendamento e algoritmos de otimização Este trabalho não apenas consolidou os conceitos aprendidos mas também desenvolveu minha habilidade de resolver problemas de forma analítica e estruturada A integração entre teoria e prática foi essencial para meu desenvolvimento preparandome para desafios mais complexos no futuro 24 REFERÊNCIAS httpscolabgoogle 25