Category: Algoritmos

Tree Data Structure

Usually when we start to study data structures, we study first trees and then graph. Can I give you two tips ? First read about graph theory. Try to answer for yourself the two following questions:

  • What are acyclic and cyclic graphs ?
  • What are directed, undirected and bidirectional graphs ?

Right. Are you a bit more confused now ? 🙂 Let’s blow the candles and see the knowledge emerging like magic. Let’s list some conditions to say: “Hey it is a tree !”

  • Just like in real life, there are many types of trees data structures that we can have.
  • In graph theory, a tree is a nonlinear data structure, compared to arrays, linked lists, stacks and queues which are linear data structures.
  • One of the disadvantages of using an array or linked list to store data is the time necessary to search for an item. Since both the arrays and Linked Lists are linear structures the time required to search a “linear” list is proportional to the size of the data set.
  • Every tree is a graph, but not every graph is a tree.
    • A is the root but it also a parent. In graph theory, a loop (also called a self-loop or a “bucle”) is an edge that connects a vertex to itself. A tree don’t have loop.
  • A child has just one parent.
  • A tree is acyclic(contains no cycles).

Desafio “Onde está o mármore ?” URI[1025]

Olá amigos! Na disciplina de PAA(Pesquisa e Análise de Algoritmos) do Mestrado,  a prof. dra. Roseane de Freitas nos passou alguns desafios do URI, e o primeiro deles que estou postando aqui é “Onde está o mármore”. O enunciado do desafio você pode estar conferindo clicando aqui.

Seguindo então o que nos é apresentado pelo desafio, precisamos receber N(número) e Q(Quantidade de Consultas) e após isso imprimir  algo como:

4 1
CASE# 1:
2
3
5
1
5
5 found at 4

Mas aí vem a dúvida, como que o resultado diz que o número 5 foi encontrado na posição 4 ? 🙂 E então ? Já sabe a charada ? Vamos reler o nome do desafio, “onde está o mármore ?”, a questão é que após os números serem inseridos para podemos trabalhar com eles, precisamos realizar a ordenação de modo que os números fiquem em ordem crescente, ou seja, a ordem no exemplo acima ficaria:

Números ordenados de forma crescente: 1 2 3 5, portando o 5 ele foi encontrado em nosso vetor ou conjunto e na posição 4. Então aqui foi a primeira dica. Para concluir, precisamos realizar uma busca pelo número informado e se tratando de busca iremos utilizar a “busca binária” pois conseguiremos uma melhor performance em relação a velocidade.

Marbles was hacked ! 🙂 O código fonte você pode conferir no meu github clinkando AQUI!

Até o próximo post!

Grafos

Pessoal este post será bem curto mas acredito que a informação é bem valiosa. Estou cursando a Disciplina de Inteligência Artificial e o trabalho que o nosso professor nós pediu é a implementação do algoritmo a*(a star). Primeiro que encontrei um livro excelente que se chama “Objetos, Abstração, Estruturas de Dados e Projetos Usando C++, Elliot B. Koffman e Paul A. T. Wolfgang”, e no capítulo 12 Grafos, “Uma das limitações das árvores é que elas não podem representar estruturas de informação em que um item de dados possui mais de um pai. Neste capítulo, apresentaremos uma estrutura de dados conhecida como um grafo, que nos permitirá superar essa limitação”.

Achei interessante em compartilhar esta interpretação.