13 ideias e tópicos interessantes de projetos de estrutura de dados para iniciantes [2022]

No mundo da ciência da computação, estrutura de dados refere-se ao formato que contém uma coleção de valores de dados, seus relacionamentos e as funções que podem ser aplicadas aos dados. As estruturas de dados organizam os dados para que possam ser acessados ​​e trabalhados com algoritmos específicos de forma mais eficaz. Neste artigo, listaremos alguns projetos úteis de estrutura de dados para ajudá-lo a aprender, criar e inovar!

Noções básicas de estrutura de dados

As estruturas de dados podem ser classificadas nos seguintes tipos básicos:

• Matrizes
• Listas vinculadas
• Pilhas
• Filas
• Árvores
• Tabelas de hash
• Gráficos

A seleção da configuração apropriada para seus dados é parte integrante do processo de programação e solução de problemas. E você pode observar que as estruturas de dados organizam tipos de dados abstratos em implementações concretas. Para chegar a esse resultado, eles fazem uso de vários algoritmos, como ordenação, busca, etc. O aprendizado de estruturas de dados é uma das partes importantes nos cursos de ciência de dados.

Com a ascensão do big data e da análise, aprender sobre esses fundamentos tornou-se quase essencial para os cientistas de dados. O treinamento normalmente incorpora vários projetos de estrutura de dados para permitir a síntese de conhecimento de experiências da vida real. Aqui está uma lista de tópicos para você começar!

Ideias de Projeto de Estruturas de Dados

1. Árvores de busca binária obscuras

Itens, como nomes, números, etc. podem ser armazenados na memória em uma ordem de classificação chamada de árvores binárias de pesquisa ou BSTs. E algumas dessas estruturas de dados podem equilibrar automaticamente sua altura quando itens arbitrários são inseridos ou excluídos. Portanto, eles são conhecidos como BSTs de auto-equilíbrio. Além disso, pode haver diferentes implementações desse tipo, como BTrees, árvores AVL e árvores vermelho-preto. Mas existem muitas outras execuções menos conhecidas sobre as quais você pode aprender. Alguns exemplos incluem árvores AA, 2-3 árvores, árvores splay, árvores de bode expiatório e treaps.

Você pode basear seu projeto nessas alternativas e explorar como elas podem superar outros BSTs amplamente usados ​​em diferentes cenários. Por exemplo, as árvores esparsas podem ser mais rápidas do que as árvores rubro-negras sob condições de localidade temporal séria.

2. BSTs seguindo o algoritmo de memorização

Memorização relacionada à programação dinâmica. Em BSTs de memorização de redução, cada nó pode memorizar uma função de suas subárvores. Considere o exemplo de um BST de pessoas ordenadas por suas idades. Agora, deixe os nós filhos armazenarem a renda máxima de cada indivíduo. Com essa estrutura, você pode responder a perguntas como: “Qual é a renda máxima das pessoas com idade entre 18,3 e 25,3?” Ele também pode lidar com atualizações em tempo logarítmico.

Além disso, tais estruturas de dados são fáceis de realizar em linguagem C. Você também pode tentar vinculá-lo com Ruby e uma API conveniente. Escolha uma interface que permita especificar 'lambda' como sua função de ordenação e sua função de memorização de subárvores. Em suma, você pode esperar que os BSTs de memorização de redução sejam BSTs de autoequilíbrio com uma pitada de escrituração adicional.

Checkout: Tipos de Árvore Binária

3. Tempo de inserção de heap

Ao procurar projetos de estrutura de dados , você deseja encontrar problemas distintos sendo resolvidos com abordagens criativas. Uma dessas questões de pesquisa exclusivas diz respeito ao tempo médio de inserção de casos para estruturas de dados de heap binários. De acordo com algumas fontes online, é tempo constante, enquanto outros implicam que é tempo log(n).

Mas Bollobas e Simon dão uma resposta numérica em seu artigo intitulado “Inserção aleatória repetida em uma fila de prioridade”. Primeiro, eles assumem um cenário em que você deseja inserir n elementos em um heap vazio. Pode haver 'n!' possíveis encomendas para o mesmo. Em seguida, eles adotam a abordagem de custo médio para provar que o tempo de inserção é limitado por uma constante de 1,7645.

4. Treaps ideais com parâmetros de mudança de prioridade

Treaps são uma combinação de BSTs e heaps. Essas estruturas de dados aleatórias envolvem a atribuição de prioridades específicas aos nós. Você pode optar por um projeto que otimize um conjunto de parâmetros em diferentes configurações. Por exemplo, você pode definir preferências mais altas para nós que são acessados ​​com mais frequência do que outros. Aqui, cada acesso desencadeará um processo duplo:

• Escolhendo um número aleatório
• Substituindo a prioridade do nó por esse número se for maior que a prioridade anterior

Como resultado dessa modificação, a árvore perderá sua forma aleatória. É provável que os nós acessados ​​com frequência estejam agora próximos à raiz da árvore, proporcionando buscas mais rápidas. Então, experimente essa estrutura de dados e tente basear seu argumento em evidências.

No final do projeto, você pode fazer uma descoberta original ou até mesmo concluir que alterar a prioridade do nó não oferece muita velocidade. No entanto, será um exercício relevante e útil.

5. Projeto de pesquisa em árvores kd

Árvores K-dimensionais ou árvores kd organizam e representam dados espaciais. Essas estruturas de dados têm várias aplicações, particularmente em pesquisas de chave multidimensionais, como o vizinho mais próximo e pesquisas de intervalo. Aqui está como as árvores kd operam:

• Cada nó folha da árvore binária é um ponto k-dimensional
• Cada nó não folha divide o hiperplano (que é perpendicular a essa dimensão) em dois meios-espaços
• A subárvore esquerda de um determinado nó representa os pontos à esquerda do hiperplano. Da mesma forma, a subárvore direita desse nó denota os pontos na metade direita.

Você pode sondar um passo adiante e construir uma árvore kd auto-balanceada onde cada nó folha teria a mesma distância da raiz. Além disso, você pode testá-lo para descobrir se essas árvores balanceadas seriam ideais para um tipo específico de aplicação.

Com isso, cobrimos cinco ideias interessantes que você pode estudar, investigar e experimentar. Agora, vamos ver mais alguns projetos sobre estruturas de dados e algoritmos.

Leia: Salário de Cientista de Dados na Índia

6. As dores do cavaleiro

Neste projeto, vamos entender dois algoritmos em ação – BFS e DFS. BFS significa Breadth-First Search e utiliza a estrutura de dados Queue para encontrar o caminho mais curto. Considerando que, DFS refere-se à pesquisa em profundidade e atravessa as estruturas de dados da pilha.

Para começar, você precisará de uma estrutura de dados semelhante às árvores binárias. Agora, suponha que você tenha um tabuleiro de xadrez padrão 8 x 8 e queira mostrar os movimentos do cavalo em um jogo. Como você deve saber, o movimento básico de um cavalo no xadrez é de dois passos para frente e um para o lado. Virado em qualquer direção e com voltas suficientes, ele pode se mover de qualquer quadrado do tabuleiro para qualquer outro quadrado.

Se você quiser saber a maneira mais simples de seu cavalo se mover de um quadrado (ou nó) para outro em uma configuração bidimensional, primeiro você terá que construir uma função como a abaixo.

• knight_plays([0,0], [1,2]) == [[0,0], [1,2]]
• knight_plays([0,0], [3,3]) == [[0,0], [1,2], [3,3]]
• knight_plays([3,3], [0,0]) == [[3,3], [1,2], [0,0]]

Além disso, este projeto exigiria as seguintes tarefas:

• Criando um roteiro para um jogo de tabuleiro e uma noite
• Tratando todos os movimentos possíveis do cavalo como filhos na estrutura da árvore
• Garantir que qualquer movimento não saia do tabuleiro
• Escolhendo um algoritmo de busca para encontrar o caminho mais curto neste caso
• Aplicando o algoritmo de busca apropriado para encontrar o melhor movimento possível do quadrado inicial para o quadrado final.

7. Estruturas de dados rápidas em linguagens de sistemas não-C

Os programadores geralmente criam programas rapidamente usando linguagens de alto nível como Ruby ou Python, mas implementam estruturas de dados em C/C++. E eles criam um código de ligação para conectar os elementos. No entanto, acredita-se que a linguagem C seja propensa a erros, o que também pode causar problemas de segurança. Aqui está uma ideia de projeto empolgante.

Você pode implementar uma estrutura de dados em uma linguagem moderna de baixo nível, como Rust ou Go, e depois vincular seu código à linguagem de alto nível. Com este projeto, você pode tentar algo novo e também descobrir como as ligações funcionam. Se seu esforço for bem-sucedido, você pode até inspirar outras pessoas a fazer um exercício semelhante no futuro e orientar melhor o desempenho das estruturas de dados.

Leia também: Ideias de projetos de ciência de dados para iniciantes

8. Motor de busca para estruturas de dados

O software visa automatizar e agilizar a escolha de estruturas de dados para uma determinada API. Este projeto não apenas demonstra novas formas de representar diferentes estruturas de dados, mas também otimiza um conjunto de funções para equipar a inferência sobre elas. Compilamos seu resumo abaixo.

• O projeto de mecanismo de busca de estrutura de dados requer conhecimento sobre estruturas de dados e os relacionamentos entre diferentes métodos.
• Ele calcula o tempo gasto por cada estrutura de dados composta possível para todos os métodos.
• Por fim, seleciona as melhores estruturas de dados para um caso particular.

Leia: Ideias de Projetos de Mineração de Dados

9. Aplicativo de lista telefônica usando listas duplamente vinculadas

Este projeto pode demonstrar o funcionamento de aplicativos de catálogo de contatos e também ensinar sobre estruturas de dados como matrizes, listas vinculadas, pilhas e filas. Normalmente, o gerenciamento de catálogo telefônico abrange operações de pesquisa, classificação e exclusão. Uma característica distintiva das consultas de pesquisa aqui é que o usuário vê sugestões da lista de contatos depois de inserir cada caractere. Você pode ler o código-fonte de projetos disponíveis gratuitamente e replicar o mesmo para desenvolver suas habilidades.

10. Indexação espacial com quadtrees

A estrutura de dados quadtree é um tipo especial de estrutura de árvore, que pode dividir recursivamente um espaço 2-D plano em quatro quadrantes. Cada nó hierárquico nesta estrutura de árvore tem zero ou quatro filhos. Ele pode ser usado para vários propósitos, como armazenamento de dados esparsos, processamento de imagens e indexação espacial.

A indexação espacial tem tudo a ver com a execução eficiente de consultas geométricas selecionadas, formando uma parte essencial do design de aplicativos geoespaciais. Por exemplo, aplicativos de compartilhamento de caronas como Ola e Uber processam geo-consultas para rastrear a localização de táxis e fornecer atualizações aos usuários. O recurso Amigos Próximos do Facebook também tem funcionalidade semelhante. Aqui, os metadados associados são armazenados na forma de tabelas e um índice espacial é criado separadamente com as coordenadas do objeto. O objetivo do problema é encontrar o ponto mais próximo de um dado ponto.

Você pode buscar projetos de estrutura de dados quadtree em uma ampla variedade de campos, desde mapeamento, planejamento urbano e planejamento de transporte até gerenciamento e mitigação de desastres. Fornecemos um breve esboço para alimentar suas habilidades analíticas e de resolução de problemas.

Objetivo: Criar uma estrutura de dados que permita as seguintes operações

• Inserir um local ou espaço geométrico
• Procure as coordenadas de um local específico
• Contar o número de locais na estrutura de dados em uma determinada área contígua

11. Projetos baseados em gráficos em estruturas de dados

Você pode assumir um projeto de classificação topológica de um gráfico. Para isso, você precisará de conhecimento prévio do algoritmo DFS. Aqui está a principal diferença entre as duas abordagens:

• Imprimimos um vértice e então chamamos recursivamente o algoritmo para vértices adjacentes em DFS.
• Na ordenação topológica, primeiro chamamos recursivamente o algoritmo para vértices adjacentes. E então, colocamos o conteúdo em uma pilha para impressão.

Portanto, o algoritmo de classificação topológica usa um gráfico acíclico direcionado ou DAG para retornar uma matriz de nós.

Vamos considerar o exemplo simples de pedir uma receita de panqueca. Para fazer panquecas, você precisa de um conjunto específico de ingredientes, como ovos, leite, farinha ou mistura para panquecas, óleo, calda, etc. Essas informações, juntamente com a quantidade e porções, podem ser facilmente representadas em um gráfico.

Mas é igualmente importante saber a ordem exata de uso desses ingredientes. É aqui que você pode implementar a ordenação topológica. Outros exemplos incluem fazer gráficos de precedência para otimizar consultas de banco de dados e cronogramas para projetos de software. Aqui está uma visão geral do processo para sua referência:

• Chame o algoritmo DFS para a estrutura de dados do gráfico para calcular os tempos de término dos vértices
• Armazenar os vértices em uma lista com uma ordem de tempo de término decrescente
• Execute a classificação topológica para retornar a lista ordenada

12. Representações numéricas com listas de acesso aleatório

Nas representações que vimos no passado, os elementos numéricos são geralmente mantidos em Heaps Binomiais. Mas esses padrões também podem ser implementados em outras estruturas de dados. Okasaki desenvolveu uma técnica de representação numérica usando listas binárias de acesso aleatório. Essas listas têm muitas vantagens:

• Eles permitem a inserção e remoção desde o início
• Eles permitem acesso e atualização em um índice específico

Saiba mais: As seis estruturas de dados mais usadas em R

13. Editor de texto baseado em pilha

Seu editor de texto regular tem a funcionalidade de editar e armazenar texto enquanto está sendo escrito ou editado. Portanto, há várias alterações na posição do cursor. Para alcançar alta eficiência, exigimos uma estrutura de dados rápida para inserção e modificação. E os arrays de caracteres comuns levam tempo para armazenar strings.

Você pode experimentar outras estruturas de dados, como buffers de lacunas e cordas, para resolver esses problemas. Seu objetivo final será obter uma concatenação mais rápida do que as strings usuais, ocupando um espaço de memória contíguo menor.

Conclusão

As habilidades de estrutura de dados formam a base do desenvolvimento de software, principalmente quando se trata de gerenciar grandes conjuntos de dados no ecossistema digital atual. Empresas líderes como Adobe, Amazon e Google contratam para vários cargos lucrativos no domínio da estrutura de dados e algoritmo. E nas entrevistas, os recrutadores testam não apenas seu conhecimento teórico, mas também suas habilidades práticas. Então, pratique os projetos de estrutura de dados acima para colocar o pé na porta!

Se você está curioso para aprender sobre ciência de dados, confira o Programa PG Executivo em Ciência de Dados do IIIT-B & upGrad, que é criado para profissionais que trabalham e oferece mais de 10 estudos de caso e projetos, workshops práticos práticos, orientação com especialistas do setor, 1 -on-1 com mentores do setor, mais de 400 horas de aprendizado e assistência de trabalho com as principais empresas.