PDF - VERSÃO DE IMPRESSÃO

Lição 7 - Estruturas de Dados: fundamentos

objetivo

Olá, estudante! Na lição anterior, estudamos as ferramentas de monitoramento e análise de dados e conhecemos os conceitos fundamentais relacionados a elas. Nesta lição, você será introduzido aos fundamentos das estruturas de dados, como pilhas, filas e alocação dinâmica. O objetivo é lhe capacitar a compreender e aplicar conceitos essenciais para o desenvolvimento de sistemas computacionais eficientes, explorando características, aplicações e gestão flexível de memória. A recursividade será apresentada como uma técnica para resolver problemas divididos em subproblemas, sua aplicação em algoritmos e manipulação de árvores.

Ao final da lição, você, futuro técnico em desenvolvimento de sistemas, será capaz de escolher as estruturas de dados mais adequadas para diferentes problemas, compreendendo sua importância na eficiência dos sistemas e fortalecendo sua base para estudos avançados em programação e algoritmos.

Preparado para esta nova jornada?

problematização

No cotidiano do desenvolvimento de software, a necessidade de organizar e acessar grandes volumes de dados de forma eficiente é um desafio comum. Estruturas de dados, como árvores, surgem como uma solução poderosa para esse problema, especialmente, em cenários nos quais é necessário realizar buscas rápidas, ordenações dinâmicas ou hierarquias claras entre os dados.

Um exemplo prático é o funcionamento de sistemas de arquivos, em que as árvores permitem representar diretórios e subdiretórios de maneira que facilita a navegação e o acesso a arquivos específicos.

No dia a dia, as árvores também são empregadas na construção de compressores de dados, como o algoritmo de Huffman, e em mecanismos de busca, permitindo que os desenvolvedores construam soluções mais otimizadas e escaláveis. A capacidade das árvores de refletir relacionamentos hierárquicos e otimizar operações faz delas uma ferramenta indispensável para problemas complexos e recorrentes no desenvolvimento de software.

Após compreender a importância da estrutura de dados árvore, vamos entender como ela funciona na prática?

case

Para ilustrar como uma estrutura de dados árvore funciona na prática, utilizemos como exemplo a empresa fictícia DataPulse Analytics, especializada em soluções de ciência de dados para o setor de saúde. A companhia enfrentava um desafio significativo: otimizar o acesso e a análise de registros médicos de milhões de pacientes, os quais incluíam históricos médicos, resultados de exames e informações de prescrições, todos dados armazenados em uma database que precisava ser consultada por diferentes sistemas em tempo real, como plataformas de telemedicina, aplicativos de saúde e sistemas internos de pesquisa clínica.

Para resolver o problema, a equipe de engenharia optou por implementar árvores como estrutura de dados central no projeto. Eles utilizaram uma B-Tree para organizar os dados, permitindo uma indexação eficiente e consultas rápidas. Essa estrutura foi essencial para lidar com o volume massivo de informações, garantindo que buscas por palavras-chave, como condições médicas específicas ou medicamentos, fossem realizadas em frações de segundo.

A abordagem não apenas melhorou a experiência dos usuários, mas também contribuiu para percepções clínicas mais precisas, permitindo aos profissionais de saúde tomar decisões mais informadas. Com essa solução baseada em árvores, a DataPulse conseguiu transformar um desafio complexo em uma vantagem competitiva, destacando-se como uma referência em eficiência e inovação no setor de saúde digital.

Assim, o exemplo destaca como as estruturas de dados, como as árvores, são fundamentais para resolver problemas complexos de maneira eficiente. Elas oferecem organização, rapidez e escalabilidade, permitindo que grandes volumes de dados sejam gerenciados com precisão. Ao dominar os fundamentos das estruturas de dados, como árvores, pilhas, filas e listas, é possível criar soluções inovadoras, capazes de transformar desafios em oportunidades em diversas áreas da tecnologia.

Vamos nos aprofundar nesse assunto!

Conceitualização

Estruturas de dados são formas de organizar e armazenar informações para garantir eficiência no desenvolvimento de sistemas computacionais. Por isso, exploraremos os fundamentos dessas estruturas de dados. Você será apresentado a conceitos, como pilhas e filas, que permitem o gerenciamento estruturado de informações, além de técnicas de alocação dinâmica para otimizar o uso de memória em tempo de execução. Abordamos, também, a recursividade como uma poderosa estratégia para resolver problemas, dividindo-os em partes menores, observando sua aplicação em algoritmos e o papel central que desempenha na manipulação de árvores.

Pilhas

A estrutura baseada no princípio LIFO (Last In, First Out) e utilizada em problemas como gerenciamento de chamadas em recursão, desfazer ações (undo) e análise de expressões matemáticas. Menezes (2017) indica que uma pilha tem um política bem definida: novos elementos são adicionados ao topo. Da mesma forma, durante a retirada, esse princípio é mantido, sendo realizada a remoção a partir do topo. Isso é semelhante a uma pilha de pratos, em que você adiciona um prato ao topo e remove o último prato adicionado primeiro.

Embora a linguagem Python não tenha uma biblioteca específica dedicada exclusivamente a pilhas, a funcionalidade pode ser facilmente implementada usando estruturas já existentes na biblioteca-padrão, como listas e queue.LifoQueue. Nesse contexto, queue.LifoQueue implementa uma pilha com suporte para controle de concorrência e segurança em aplicações multithread, sendo um recurso mais robusto, ideal para casos em que há necessidade de gerenciar pilhas em contextos de threads. Confira uma implementação na Figura 1 a seguir.

Figura 1 - Pilha em Python
Fonte: o autor.

#PraCegoVer: temos, na Linha 1: # from queue import LifoQueue; na Linha 3: pilha = LifoQueue(); na Linha 4: pilha.put(1) # Adiciona 1 à pilha; na Linha 5: pilha.put(2) # Adiciona 2 à pilha; e na Linha 6: print(pilha.get()) # Remove e retorna 2. Na Linha 2, não há conteúdo escrito. Fim da descrição.

Filas

Essa estrutura segue o princípio FIFO (First In, First Out), sendo aplicada em sistemas de gerenciamento de processos, filas de impressão e sistemas de atendimento. Menezes (2017) nos dá o exemplo das filas de banco. Quando a agência abre pela manhã, a fila está vazia. Quando os clientes começam a chegar, eles vão diretamente para o fim da fila. Os caixas, então, começam a atendê-los por ordem de chegada, ou seja, o cliente que chegou primeiro será atendido primeiro. Em termos de programação, uma fila é usada para organizar itens de maneira que o primeiro item inserido seja o primeiro a ser removido.

Python oferece suporte à implementação de filas por meio de várias bibliotecas e estruturas. Embora a linguagem não tenha uma biblioteca exclusivamente para filas, ela fornece várias opções na biblioteca-padrão queue, que oferece a classe Queue, projetada para operações de fila com suporte à concorrência. Essa estrutura segue o modelo FIFO (First In, First Out). Observe um exemplo de implementação de fila em Python, usando a biblioteca queue, na Figura 2 a seguir.

Figura 2 - Fila em Python
Fonte: o autor.

#PraCegoVer: na Linha 1, temos: from queue import Queue; na Linha 3: fila = Queue(); na Linha 4: fila.put(1) # Adiciona 1 à fila; na Linha 5: fila.put(2) # Adiciona 2 à fila; na Linha 6: print(fila.get()) # Remove e retorna 1. Na Linha 2, não há conteúdo escrito. Fim da descrição.

Alocação dinâmica

A alocação dinâmica de memória é um processo utilizado em programação para gerenciar a memória de forma flexível, permitindo que estruturas de dados sejam criadas, redimensionadas ou liberadas durante o tempo de execução. Diferentemente da alocação estática, que reserva memória de forma fixa antes da execução do programa, a alocação dinâmica se adapta às necessidades do programa em tempo real. Isso é especialmente útil quando o tamanho exato dos dados não é conhecido de antemão ou pode variar significativamente durante a execução.

No contexto da linguagem Python, a gestão de memória é realizada automaticamente pelo interpretador, o que dispensa a necessidade de gerenciamento explícito como em linguagens como C ou C++. Entretanto, Python oferece mecanismos e bibliotecas, como ctypes ou array, para lidar com cenários que requerem controle mais detalhado sobre a memória.

Recursividade

É uma técnica de solução de problemas em que uma função se chama repetidamente, dividindo o problema em subproblemas menores até alcançar um caso-base. Segundo Groner (2018), a recursão é um método para resolução de problemas que consiste em solucionar partes menores do mesmo problema até resolvermos o problema original, mais amplo. Em geral, ela envolve chamar a própria função. A recursividade é fundamental para percorrer e manipular árvores, como na implementação de buscas, inserções ou remoções.

Árvores

Podemos dizer, de maneira geral, que se trata de uma representação hierárquica de dados em forma de nós e arestas, com aplicações que vão desde sistemas de arquivos até algoritmos de busca. Groner (2018) define a árvore como um modelo abstrato de uma estrutura hierárquica. O exemplo mais comum de uma árvore na realidade seria o de uma árvore genealógica ou o organograma de uma empresa. Incluem inserções, remoções e percursos (em ordem, pré-ordem e pós-ordem), além de variantes como árvores balanceadas (AVL, B-Trees). São aplicadas na organização de dados em bancos de dados, algoritmos de busca eficiente e modelagem de hierarquias complexas em sistemas.

Configura o exemplo de implementação de árvore binária com recursividade, usando Python, na Figura 3.

Figura 3 - Árvore binária com recursividade em Python
Fonte: o autor.

#PraCegoVer: na Linha 1, temos: class No:; na Linha 2: def __init__(self, valor):; na Linha 3: self.valor = valor; na Linha 4: self.esquerda = None; na Linha 5: self.direita = None; na Linha 7: class ArvoreBinaria:; na Linha 8: def __init__(self):; na Linha 9: self.raiz = None; na Linha 11: def inserir(self, valor):; na Linha 12: if self.raiz is None:; na Linha 13: self.raiz = No(valor); na Linha 14: else:; na Linha 15: self._inserir_recursivo(self.raiz, valor); na Linha 17: def _inserir_recursivo(self, atual, valor):; na Linha 18: if valor < atual.valor:; na Linha 19: if atual.esquerda is None:; na Linha 20: atual.esquerda = No(valor); na Linha 21: else:; na Linha 22: self._inserir_recursivo(atual.esquerda, valor); na Linha 23: elif valor > atual.valor:; na Linha 24: if atual.direita is None:; na Linha 25: atual.direita = No(valor); na Linha 26: else:; na Linha 27: self._inserir_recursivo(atual.direita, valor); na Linha 29: def percorrer_em_ordem(self):; na Linha 30: self._percorrer_em_ordem_recursivo(self.raiz); na Linha 32: def _percorrer_em_ordem_recursivo(self, no):; na Linha 33: if no is not None:; na Linha 34: self._percorrer_em_ordem_recursivo(no.esquerda); na Linha 35: print(no.valor, end=" "); e na Linha 36: self._percorrer_em_ordem_recursivo(no.direita). Nas Linhas 6, 10, 16, 28 e 31, não há conteúdo escrito. Fim da descrição.

Em resumo, as estruturas de dados são pilares fundamentais, fornecendo as bases para a organização e manipulação eficiente de informações em sistemas. Desde a simplicidade das pilhas e das filas até a complexidade de árvores e a flexibilidade da alocação dinâmica, cada estrutura desempenha um papel único e essencial. A compreensão e a aplicação desses conceitos otimizam a utilização de recursos e ampliam as possibilidades para enfrentar desafios de maneira criativa e eficiente.

saiba aplicar

Compreender os fundamentos das estruturas de dados, como pilhas, filas e alocação dinâmica, bem como a técnica de recursividade, é essencial para você, futuro técnico em desenvolvimento de sistemas, pois esses conceitos formam a base para a criação de soluções computacionais eficientes e flexíveis. A aplicação desses conhecimentos permite ao profissional lidar com desafios como a organização e manipulação de grandes volumes de dados, a otimização de algoritmos e a implementação de estruturas adaptáveis às necessidades específicas dos sistemas. Dessa forma, enquanto técnico, você estará preparado para desenvolver softwares robustos, garantindo desempenho e escalabilidade em projetos do mundo real.

Agora é a sua vez de aplicar os conceitos aprendidos nesta lição! Neste passo a passo, você aprenderá a implementar uma árvore binária para resolver um problema relacionado à organização de dados em ciência de dados. Vamos usar o site OnlineGDB para executar o código.

Passo a passo

Acesse o site OnlineGDB.
No menu suspenso de linguagem, selecione Python.
Implemente as classes de árvore binária que implementamos como exemplo na Figura 3.
Implemente o exemplo de uso a seguir, conforme a Figura 4.

Figura 4 - Exemplo de uso de árvore binária com recursividade em Python
Fonte: o autor.

#PraCegoVer: na Linha 1, temos: arvore = ArvoreBinaria(); na Linha 3: # Simulando valores médios de vendas mensais de uma empresa em milhares de reais; na Linha 4: valores_vendas = [25.4, 18.2, 33.5, 20.1, 27.6, 31.2, 40.8]; na Linha 5: for valor in valores_vendas:; na Linha 6: arvore.inserir(valor); na Linha 8: print(“Valores de vendas organizados em ordem crescente:”); e na Linha 9: arvore.percorrer_em_ordem(). Nas Linhas 2 e 7, não há conteúdo escrito. Fim da descrição.

5. Clique em Run no OnlineGDB.

6. Observe o console exibindo os valores médios de vendas organizados em ordem crescente.

Esse exemplo é útil em ciência de dados para organizar e categorizar informações rapidamente, facilitando a análise de tendências, comparações de desempenho e tomadas de decisão baseadas em dados ordenados. Além disso, também mostra como as árvores binárias podem ser usadas para organizar dados de forma eficiente – um conceito valioso, tendo em vista que, enquanto profissional, você poderá trabalhar com grandes volumes de dados em ciência de dados.

REFERÊNCIAS

GRONER, L. Estruturas de dados e algoritmos com JavaScript. 2. ed. São Paulo: Novatec, 2018.

MENEZES, N. N. C. Introdução à programação com Python: algoritmos e lógica de programação para iniciantes. 2. ed. São Paulo: Novatec, 2017.

Page updated

Google Sites

Report abuse