QUESTIONÁRIO 08 - QUICKSORT

1)      Por que o método quicksort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?
Resposta: O método Quicksort tem esse nome por ser um método que é mais rápido ordenar dois vetores com n/2 elementos cada um,  do que um com n elementos (conceito dividir para conquistar).  Além da versão recursiva, existe também a versão iterativa do Quicksort.
2)      A ordenação pelo método quicksort é um dos mais simples. Qual a principal característica do método ou como ele funciona?
Resposta: O primeiro passo é escolher o pivô. Uma vez escolhido o pivô, os elementos do vetor são movimentados de forma que o subvetor à esquerda do pivô contenha somente os elementos cujo valor é menor que o valor do pivô e o subvetor da direita contenha valores maiores que o valor do pivô. O procedimento é repetido até que o vetor esteja ordenado.

3)      Qual é a classificação do método quicksort? Qual o seu grau de complexidade?
Resposta: O método quicksort é um método recursivo. Existem dois tipos de complexidade: Complexidade de Tempo e Complexidade de Espaço.
Complexidade de Tempo θ(n lg₂ n) no melhor caso e θ(n) no caso médio e θ(n²) no pior caso;
Complexidade de espaço: θ(lg₂ n) no melhor caso e no caso médio e θ(lg₂ n) no pior caso. R. Sedgewick desenvolveu uma versão do Quicksort com partição recursão de cauda que tem complexidade θ(n²) no pior caso.

4)      Dê exemplo de aplicação do método quicksort, com as comparações, trocas e iterações.
a) Pivô é escolhido no meio do vetor. O elemento é colocado numa variável auxiliar trab;
b) São iniciados dois ponteiros i e j;
c) O vetor é percorrido a partir da esquerda até que se encontre um V[i] ≥ trab (i é incrementado no processo);
d) O vetor é percorrido a partir da direita até que se encontre um V[j] ≤ trab (j é decrementado no processo); 
e) Os valores V[i] e V[j] são trocados; i é incrementado de 1 e j é decrementado de 1;
f) O processo é repetido até que i e j se cruzem em algum ponto do vetor;
g) Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva.

5)      Demonstre o código-fonte do método quicksort e comente o mesmo.

  A parte muito importante do algoritmo é a escolha de um pivô, o vetor  estará particionado ao final em uma parte esquerda com chaves menores ou iguais ao pivô e outra parte direita maiores ou iguais. O vetor é percorrido a partir da direita até encontrar um V[j] ≤ V[i]. Os valores V[i] e V[j] são trocados, i é incrementado de 1 e j é decrementado de 1, o processo é repetido até que i e j se cruzem em algum ponto do vetor. Quando são obtidos os dois segmentos do vetor por meio do processo de partição, realiza-se a ordenação de cada um deles de forma recursiva.

QUESTIONÁRIO 07 - ORDENAÇÃO – MÉTODO MERGESORT

1) Por que o método mergesort têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?
 Resposta: O mergesort ou ordenação por mistura (fusão), é um exemplo de algoritmo de ordenação do tipo dividir-para-conquistar.

2) A ordenação pelo método mergesort é um dos mais simples. Qual a principal característica do método ou como ele funciona?

      Resposta: Complexidade de tempo. É (n log₂ n). É possível implementar o mergesort utilizando somente um vetor auxiliar ao longo de toda a execução.

      3) Qual é a classificação do método mergesort? Qual o seu grau de complexidade?
      Resposta: O   Mergesort é classificado como ordenação por partição, que parte do princípio de "dividir para conquistar". Este princípio é uma técnica que foi utilizada pela primeira vez por Anatolii Karatsuba em 1960 e consiste em dividir um problema maior em problemas pequenos, e sucessivamente até que o mesmo seja resolvido diretamente. 
      Esta técnica realiza-se em três fases:
      Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva. 
      Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
     Combinação: os resultados dos problemas menores são combinados até que seja obtida a solução do problema maior. Algoritmos que utilizam o método de partição são caracterizados por serem os mais rápidos dentre os outros algoritmos pelo fato de sua complexidade ser, na maioria das situações, O(nlogn). Os dois representantes mais ilustres desta classe são o quicksort e o mergesort.
     

      4) Dê exemplo de aplicação do método mergesort, com as comparações, trocas e iterações.

     

      5) Demonstre o código-fonte do método mergesort e comente o mesmo.

                              

Clique na figura para visualizar

QUESTIONÁRIO 06 - INSERÇÃO E MÉTODO SHELL

1)    Por que o método shell têm esse nome? Existe outra versão do método? Ele é conhecido por qual outro nome?

Resposta: O Método Shell leva o nome do seu inventor Donald L. Shell, formado em Ciência da Computação e teve seu PH.D. em matemática após a publicação  do algoritmo de ordenação shell. A versão que existe é a versão 1.2 e em relação ao nome, ela também pode ser conhecida como concha, pois lembra o formato de uma concha. 

2)    A ordenação pelo método shell é um dos mais simples. Qual a principal característica do método ou como ele funciona?
Resposta: A principal característica do método shell é que ele trabalha com 2 vetores: Vetor Ordenado e Vetor Desordenado. Com o funcionamento e evolução do método shell, o vetor desordenado vai diminuindo seus elementos, enquanto o vetor ordenado vai aumentando seus elementos, ou seja, os elementos que estavam desordenados vai se ordenando até que o vetor ordenado fique com todos os elementos completo e o vetor desordenado não haja mais nenhum elemento, ou seja, se torna um vetor vazio (null).

3)    Qual é a classificação do método shell? Qual o seu grau de complexidade?
Resposta: O método shell é classificado como método de simples implementação e o seu grau de complexidade é quadrática.

4)    Dê exemplo de aplicação do método shell, com as comparações, trocas e iterações.

Resposta: O primeiro elemento está no vetor ordenado e os demais no vetor desordenado;

Retira-se o primeiro elemento do vetor desordenado, colocando-o no vetor ordenado. Nesse processo, são realizadas as comparações necessárias para inserí-lo na sua posição correta;

Repete-se o processo até que todos os elementos do vetor desordenado tenham passado para o vetor ordenado.

5)    Demonstre o código-fonte do método shell e comente o mesmo.

QUESTIONÁRIO 05 - ORDENAÇÃO E MÉTODO BOLHA

1)      Ordenar é um processo de rearranjar um conjunto de objetos em uma ordem ascendente/crescente ou descendente/decrescente. Qual a importância da ordenação para qualquer processo e para informática? Dê exemplos práticos de utilização. Defina a complexidade dos métodos de ordenação e a sua classificação.

2)      Qual é a classificação dos métodos de ordenação? Qual a diferença entre eles? Quais são os métodos de ordenação mais utilizados ou principais?

3)      A ordenação pelo método bolha é um dos mais simples. Qual a principal característica do método ou como ele funciona?

Resposta: O primeiro elemento é comparado com o segundo, se uma inversão for encontrada, a troca é feita. Em seguida, independente se houve ou não troca após a primeira comparação, o segundo elemento é comparado com o terceiro, e, caso uma inversão seja encontrada, a troca é feita. O processo continua até que o penúltimo elemento seja comparado com o último.

4)      Qual é a classificação do método bolha? Qual o seu grau de complexidade?

Reposta:   N  > N  >  log(N)
E o seu grau de complexidade é pequeno , necessita de muita memória para opera-lo

5)      Dê exemplo de aplicação do método bolha, com as comparações, trocas e iterações.

Resposta: Bom um exemplo que pode ser dado é classificação  numerica  de forma  cresente  de uma derterminadaposta
1         40 30 20 10 50
2         30 20 10 40 50
3         20 10 30 40 50
4         10 20 30 40 50
5         10 20 30 40 50 --> Todos os numeros Ordenados.

6)      Demonstre o código-fonte do método bolha e comente o mesmo.

Resposta: #include <stdio.h>  
#include <stdlib.h>
 
  void bubble(int a[],int n)  
  {  
 
  int i,j,t;  
  for(i=n-2;i>=0;i--) {  
  for(j=0;j<=i;j++) {  
 
  if(a[j]>a[j+1]) {  
                  t=a[j];  
                  a[j]=a[j+1];  
                  a[j+1]=t;  
                  }  
                  }  

  } //Final do 1º FOR  
 
  } //Final da Função
 
  int main() {  
 
      int a[100],n,i;  
 
      system("pause");  
 
      printf("\n\n Entre com o total de numeros a serem sorteados:\n\n ");  
      scanf("%d",&n);  
 
      for( i=0;i<=n-1;i++) {
     
      printf("\n\n Entre com o valor inteiro %d:    ",i+1);  
      scanf("%d",&a[i]);  
      }  

QUESTIONÁRIO 04 - ÁRVORES AVL (BALANCEADAS)

1)         Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Para construirmos uma árvore balanceada ou AVL primeiramente precisamos utilizar o conceito de ABB. Portanto explique o conceito de árvore balanceada ou AVL?

Resposta: Uma árvore AVL é dita balanceada quando, para cada nó da árvore, a diferença entre as alturas das suas sub-árvores (direita e esquerda) não é maior do que um. Caso a árvore não esteja balanceada é necessário seu balanceamento através da rotação simples ou rotação dupla. O balanceamento é requerido para as operações de inserção e remoção de elementos. Para definir o balanceamento é utilizado um fator específico para nós. O Fator de Balanceamento (FB) é utilizado pela seguinte fórmula:

FB(nó) = altura(dir)  - altura(esq)

O fator de balanceamento de um nó é dado pelo seu peso em relação a sua sub-árvore. Um nó com fator balanceado pode conter 1, 0, ou -1 em seu fator. Um nó com fator de balanceamento diferente dos citados é considerado uma árvore não-AVL e requer um balanceamento por rotação ou dupla-rotação.

2)         Sabendo que podemos inserir elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de inserção na árvore AVL e do seu algoritmo.

Resposta: Primeiro, c é inserido como folha A, seguindo o algoritimo do caso geral das ABBs. Se depois da inserção a árvore permanece AVL, então nada mais temos a fazer. Caso contrário, é necessário remanejar a árvore.

3)         Sabendo-se que os conceitos de rotação simples a direita/esquerda e de rotação dupla a direita/esquerda são essenciais na inserção de elementos na árvore avl. Explique os conceitos de rotação simples e rotação dupla.
Resposta: Uma rotação simples ocorre quando um nó está desbalanceado e seu filho estiver no mesmo sentido da inclinação, formando uma linha reta. Uma rotação-dupla ocorre quando um nó estiver desbalanceado e seu filho estiver inclinado no sentido inverso ao pai, formando um "joelho".

4)         Sabendo que podemos retirar elementos numa árvore AVL e que isso é uma operação básica das árvores, explique o conceito de remoção na árvore AVL e do seu algoritmo.
Resposta: A remoção deve ser dada por uma rotação em torno do nó a ser removido, a fim de torná-lo folha para que então possa ser removido. Em alguns casos, após a remoção são necessárias rotações para ajustar o fator de balanceamento.

1. Remover X da árvore AVL usando o mesmo algoritmo de remoção de um nó em uma árvore de busca binária. Recursivamente, empilhar cada nó que é visitado a partir do nó raiz até o nó X, incluindo-o;
2. Verificar se a pilha está vazia
• Se sim, o algoritmo termina.
• Senão, vá para o passo (3).
3. Desempilhar um nó e verificar se a diferença de altura entre a sub-árvore da esquerda e da direita desse nó é maior que 1.
• Se sim, você precisará rotacionar os nós. Dependendo do tipo de rotação realizada, o algoritmo pode não terminar aqui. Se ele não terminar, vá para o passo (2).
• Senão, vá para o passo (2). 

Note que a operação de remoção pode ser realizada em tempo O(lg(n)). Na remoção de um elemento em uma árvore AVL, pode haver a necessidade de realizar mais de duas rotações (o que não acontece na inserção), podendo se estender para uma rotação em cada nível (O(log(n))) no pior caso. A figura a seguir mostra um exemplo deste caso:

5)         Através dos conceitos discutidos, dê dois exemplos de inserção em árvores AVL e dois exemplos de remoção em árvores AVL.

Resposta: Exemplo de remoção:                                                                                                            Exemplo 1 : Dada a árvore abaixo, retirando o 5 resulta uma arvore desbalanceada no nó 10(b). A partir daí, raciona-se como se estivéssemos inserindo: que nó inserido teria causado esse desequilíbrio? O 30. Aplicando os conhecimentos de inserção em arvore AVL, constata-se que uma rotação simples a esquerda resolve o problema. O resultado esta na AVL(C).

 

Exemplo 2: Retirando a folha 12 de (a), na figura abaixo, desbalanceia a raiz (b); supondo-se a inserção recente de 8, corrige-se o desequilíbrio mediante uma rotação dupla a esquerda (c).

Exemplo de inserção:

Exemplo 1: Inserção seqüencial ( Chaves de 1 a 7) em arvore AVL em destaque nós P e U dos exemplos que precisam de rotação ( e Y, filho que precisa “Trocar de Pai) em vermelho), nos retângulos arvore antes e após a rotação:

 

Exemplo 2:

Inserção das Chaves 80,40,60,50 e 45 (nessa seqüência ):

QUESTIONÁRIO 03 - ÁRVORE BINÁRIA DE BUSCA

1)   Uma árvore binária é uma árvore onde cada nó tem no máximo 2 filhos.  Uma árvore binária de busca é uma árvore binária onde os elementos da subárvore esquerda são menores que a raiz e os elementos da subárvore direita são maiores que a raíz. Portanto explique como serão inseridos os elementos 10, 20, 15, 18,  30, 40 e 13 numa árvore binária de busca.
Resposta: Primeiramente, ordenar os números em ordem crescente:

10, 13, 15, 18, 20, 30, 40.

      Após a ordenação dos números, identifica-se que a raiz será o número 18, pois se encontra no meio do intervalo de números acima;

      Em seguida, colocar todos os números menores que 18 na subárvores da esquerda e maiores que 18 na subárvores da direita.

      Veja como ficou inseridos os elementos na figura da árvore abaixo.

2)   Sabendo que podemos inserir elementos numa árvore binária e que isso é uma operação básica das árvores, indique e explique quais são as operações básicas de uma árvore binária?
Resposta: Inserção quando adciona-se um elemento na árvore na posição correta para que a propriedade fundamental seja mantida. Para inserirmos um valor x em uma árvore usamos sua estrutura recursiva, e a ordenação especifica na propriedade fundamental.
Remoçao quando se permite retirar um determinado elemento da árvore. Primeiro quando se deseja retirar um elemento da folha de árvore, basta retirar o elemento da árvore e atualizar o pai, pois seu filho não existe mais. Segundo passo quando o nó a ser retirado possui um único filho, para retirar esse elemento é necessário antes acertar o ponteiro do pai, pulando o nó, o único neto passa a ser o filho direto.
Construção as operações de inserção devem ser efetuadas conforme a ordem das chaves o 1º passo é inserir as chaves que ficaram mais proximas da raiz, se caso tivermos um conjunto de chaves deve se inserir o valor médio das chaves, inserindo as chaves inferior e as superiores a esse valor.

3)   Sabendo que as árvores binárias podem ser cheias e completas e que uma árvore otimal é uma árvore completa que a operação de inserção segue a regra de inserção por ordem das chaves. Como as inserções sempre ocorrem à nível de folha,  deve-se primeiro inserir as chaves que ficarão mais perto da raíz. Se temos um conjunto de chaves {c1,..,ci} tal que c1<...<ci, deve se inserir o valor médio das chaves, inserir o conjunto das chaves inferior a esse valor, e inserir o conjunto das chaves superior a esse valor.  Portanto no conjunto de chaves K={1,2,3,4,5,6,7}.  Uma ordem de inserção otimal seria o 4, 2, 6, 1, 7, 5 e 3. Explique como ficaria uma inserção otimal do conjunto K={2,4,6,8,10,12,14}.
Resposta:  Se temos um conjunto de chaves {c1,. . . c} tal que c1 < ... < c, deve se inserir o valor médio das chaves, inserir o conjunto das chaves inferior a esse valor, e inserir o conjunto das chaves superior a esse valor.
Então, pela inserção K={2,4,6,8,10,12,14}, o número 8 é a raiz pois se encontra no meio desse intervalo de números. Veja na figura abaixo a inserção otimal do intervalo de números acima:

4)   Uma das operações mais úteis das ABB é a localização, outra característica desse tipo de árvore são os chamados percursos que mostram os elementos que a árvore contém e que são classificados em pré-fixado/pré-ordem, pós-fixado/pós-ordem e in-ordem/em ordem. Explique como funciona o procedimento para realizar cada percurso considerando as subárvores. Existe alguma diferença com relação às árvores binárias comuns?

Percurso de uma árvore binária em pré-fixado / pré-ordem 

Percorrer uma árvore binária em pré-ordem:

    1.Visitar a raiz.

    2. Percorrer a sua subárvore esquerda em pré-ordem.

    3. Percorrer a sua subárvore direita em pré-ordem.



O percurso em pré-ordem segue os nós até chegar os mais “profundos”, em “ramos” de subárvores da esquerda para a direita. É conhecida usualmente pelo nome de percurso em profundidade (depth-first).

Percurso de uma árvore binária em pós-fixado / pós-ordem

Percorrer uma árvore binária em pós-ordem:

1. Percorrer a sua subárvore esquerda em pós-ordem.

2. Percorrer a sua subárvore direita em pós-ordem.

3. Visitar a raiz.

Outro Exemplo:

A representação de uma expressão aritmética com o operador no final dos operando é conhecida pelo nome de notação reversa ou polonesa.

Percurso de uma árvore binária em in-ordem / em ordem

Percorrer uma árvore binária em in-ordem:

1. Percorrer a sua subárvore esquerda em in-ordem.

2. Visitar a raiz.

3. Percorrer a sua subárvore direita em in-ordem.

A in-ordem visita a raiz entre as ações de percorrer as duas subárvores. É conhecida também pelo nome de ordem simétrica.



QUESTIONÁRIO 02 – ÁRVORES BINÁRIAS

1) Uma árvore é um conjunto de 1 ou mais nós, onde existe um nó especial chamado raiz e os demais nós formam conjuntos disjuntos onde cada conjunto é uma árvore (subárvore). O que caracterizaria então uma árvore Binária?
Resposta: Uma árvore binaria deve conter no máximo 2 filhos(nós), e nela possuem grau zero ou um.

2) Uma árvore binária tem por tanto uma subárvore da esquerda e outra subárvore da direita (mesmo que exista uma só ou nenhuma), existe alguma maneira de calcular o número máximo de elementos de uma árvore conhecendo sua altura?
Resposta: Sim, isso acontece através da Formula: 2n – 1 = Numero máximo de elementos de uma árvore binária.

3) Nas árvores binárias podemos percorrer os elementos através de alguns percursos, quais são eles?
Resposta: IN-Ordem, PRÉ-Ordem, PÓS-Ordem.

4) A definição do percurso EM-Ordem/IN-Ordem é:
Resposta: A raiz fica no meio das sub-arvores esquerda e direita.

5) A definição do percurso PRÉ-Ordem/PRÉ-Fixado é:
Resposta: A raiz vem antes das sub-arvores esquerda e direita.

6) A definição do percurso PÓS-Ordem/PÓS-Fixado é:
Resposta: A raiz vem depois das sub-arvores esquerda e direita.

7) Existe outra maneira de percorrer uma árvore (não obrigatoriamente binária), conhecida como percurso por extensão ou largura. Explique esse processo.
Resposta: Percurso por Extensão ou Largura: Os nós são visitados na ordem dos níveis da árvore, isto é: primeiramente são visitados os nós do nível 0, depois do nível 1, depois do nível 2 eassim por diante; os nós são visitados da esquerda para a direita em cada um dos níveis.



Ordem de Processamento: A B E C F G D H

Exercício do Slide

Faça o percurso em pré-ordem, in-ordem e pós-ordem da seguinte árvore.

PRÉ-ORDEM (RED) – A B D G C E H I F 

IN/EM-ORDEM (ERD) – D G B A H E I C F

PÓS-ORDEM (EDR) – G D B H I E F C A



QUESTIONÁRIO 01 – ÁRVORES, CONCEITOS GERAIS

1)   A estrutura de uma árvore é especializada em representar hierarquia. Defina e caracterize de forma completa o conceito da Estrutura Árvore.

Uma árvore é uma estrutura de dados em que cada elemento tem um ou mais elementos associados, podendo definir-se uma árvore recursivamente como:

1. uma estrutura (uma árvore);
2. um nó (designado por raiz), que contém a informação a armazenar e um conjunto finito de árvores (as sub-árvores).
3. Não Existe árvores vazias, no minímo haverá um nó raiz(que não possui pai)

Cada árvore tem apenas uma raiz. Além disso, os elementos associados a cada nó são habitualmente chamados de filhos desses nós. Os nós sem filhos de uma árvore são chamados de folhas.

2)         O conceito da estrutura árvore é muito importante para as disciplinas de Sistema Operacional e Banco de Dados. Dê exemplos da aplicação prática da estrutura de dados árvore, explicando cada exemplo (pelo menos 3).
Hierarquia de classes: São as classes e subclasses, ou seja, uma classe subordinando a outra;
Ordenação de Valores: São as  Árvore ordenada na esquerda, na  raiz, e na direita;
Organogramas de empresas: É a  hierarquia entre os empregados de uma empresa.

3)         Para compreender o conceito de árvore é necessário entender alguns conceitos básicos. Explique o conceito de raíz, nó filho, nó pai, nó terminal, nó ascendente, nó descendente, grau, altura, nível, profundidade, caminho e floresta.
Os conceitos básicos da estrutura árvore são:

• Raiz – é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);
• Nós – são todos os itens guardados na árvore;
• Nós Filhos – são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);
• Nós Pais – são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);
• Folhas ou nó terminal – são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13);
• Nó Ascendente- Nó acima de um dado nó, em direção a raiz (No caso da figura acima, o nó 8 é ancestral do nó 3, 10 ,1, 6 …, 13);
• Nó Descendente- Nó abaixo de um dado nó (No caso da figura acima, o nó 3 e 10 é ascendente de 8);
• Grau de um nó é o número de nós  filhos do mesmo. Obviamente um nó folha tem grau zero;
• Nível de um nó é o número de nós existentes no caminho entre a raiz e o próprio nó;
• Altura de uma árvore  (também denominada profundidade) é a distância entre x e o seu descendente mais afastado. Mais precisamente, a altura de x é o número de passos do mais longo caminho que leva de x até uma folha somando um;
• caminho da árvore é composto por uma seqüência de nós consecutivos (n₁, n₂, …, n_k-1, n_k) tal que existe sempre a relação n_i é pai de n_i+1;
• Floresta: é um conjunto de zero ou mais árvores disjuntas, ou seja, se for eliminado o nó raiz da árvore, as sub-árvores que restarem chama-se de florestas.

4)         Existem diversas maneiras de representar a estrutura de uma árvore. Demonstre e conceitue a representação Hierárquica, Diagrama de Inclusão, Expressão parametrizada e Expressão não parametrizada.


Representação hierárquica





Representação por conjuntos (diagrama de inclusão)

      Representação por expressão parentetizada (parênteses aninhados)
      Cada conjunto de parênteses correspondentes contém um nodo e seus  filhos.
      Se um nodo não tem filhos, ele é seguido por um par de parênteses sem conteúdo.

      Representação por expressão não parentetizada
      Cada nó é seguido por um número que indica a quantidade de filhos desse nodo, e em seguida por esses filhos, representados do mesmo modo.