QUESTIONÁRIO 8 - Método Quicksort

1 - Por que o método quicksort tem esse nome ? Existe outra versao do método ? Ele é conhecido pro qual outro nome ?

R: O método quicksort tem esse nome por ser o método mais rápido e ordenado dois vetores com n/2 elementos cada um , do que um com n de elementos . Além de versões recursiva , existe também a versão interativa do quicksort.

2- A ordenação pelo método quicksort é um dos mais simples . Qual a principal caracteristica do método ou como ele funciona ?

R: Adotando a estratégia dividir para conquistar o funcionamento resume-se a dividir o problema de ordenar um vetor de n posições em dois outros menores recursivamente ate atingir o objetivo de rearranjar todo vetor .

3 - Qual é a classificação do método quicksort ? Qual o seu grau de complexidade ?

R: Método recursivo e sua ordem de complexidade do algoritmo recursivo deste método é 0)n log n).

4- Dê um exemplo de aplicação do método quicksort , com as comparações , trocas e interações .

Usando o 5 como pivô:



5 - Demostre o codígo-fonte do método quicksort e coemente 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 . O vetor é percorrido a partir da direita até encontrar um V[i] < V[i] . Os valores V[i] e V[i] são trocados , i é incrementado de 1 e j é decrementado de 1 , o processo é repetido até que i e j se cruzem em um ponto do vetor . Quando são obitidos os dois segmentos do vetor por meio do processo de participação , realiza-se a ordenação de cada um deles de forma recursiva.

QUESTIONÁRIO 7 - Ordenação Método Mergersort

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

R: Merge sort , ou ordenação por mistura (fusão) e um exemplo algoritmo de ordenação do tipo dividir-para-conquistar.

2 - A ordenação pelo método mergesort é um dos mais simples . Qual principal caracteristica do metodo ou como ele funciona ?

R: Sua principal caracteristica e ordenação do tipo dividir para conquistar . Sua ideia básica é criar uma seguência ordenada a partir de duas outras também ordenadas . Para isso,ele divide a sequência original em pares de dados , ordena-das ; depois as agrupa em sequências de quatro elementos , e assim por diante , ate ter toda a sequência dividida em apenas duas partes .

3- Qual e a classificação do método mergersort ? Qual o seu grau de complexidade ?

R: Método recursivo e sua ordem de complexidade do algoritmo recursivo desde método é 0 (n log n).

4- Dê exemplo de aplicação do método mergersort , com as comparações trocas e interações.




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




Na quinta e sexta linha do código definimos os ponteiros para o vetor 1 e 2 . A função de copia do vetor temporário para o que retornara atualizado se encontra no segundo for . Na parte final do código é definida a função principal do mergesort que determina a metade do vetor depois a primeira metade e a segunda metade a ultima linha combina as metades já ordenadas.

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?

R: O método de comparações e movimentações do ShellSort 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?

R: Sua principal característica é utilizar a quebra sucessiva de seqüência a ser ordenada e implementa a ordenação na seqüência obtida

3- Qual é a classificação do método shell? Qual o seu grau de complexidade?

R: É classificado dentre os de complexidade quadrática, seu grau de complexidade é O(n^2 )

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

R: - Temos o seguinte vetor de números inteiros :

V = (36 , 24 , 17 , 14 , 39 , 27)

- A cada passagem do método de inserção ShellSort , o Vetor vai sendo alterado da seguinte forma :

- Inicial: V=(36,24,17,14,39,47)

-Apos i=2 V=(24,36,17,14,39,27)

-Apos i=3 V=(17,24,36,14,39,27)

-Apos i=4 V=(14,17,24,36,39,27)

-Apos i=5 V=(14,17,24,36.39,27)

-Apos i=6 V=(14,17,24,27,36,39)

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

void shell (int *v,int i) {

int x , j , valor;

int h = 1;

do{

h=3*h+1

}while(h< i);

do{

h/=3;

for(x = h; x < i; x++) {

valor = v [x]

j = x - h;

while (j>=0 && valor < v[j]) {

v [j + h] = v [j]

j = h

}

v [j + h] = valor

}

}while (h >1)

}

O algoritmo usa variável auxiliar denominada a distancia de comparação (h) , o valor de h e inicializado com um valor próximo de n/2.

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.

O objetivo principal da ordenação é facilitar a organização e a localização posterior de dados do conjunto ordenado. Pode-se citar uma lista telefônica. Imagine como seria consultar o telefone de uma pessoa se os nomes não estivessem classificados em ordem alfabética. Para algoritmos de ordenação interna, as medidas de complexidade relevantes contam o número de comparações entre chaves e o número de movimentações de itens do arquivo, os métodos de ordenação são classificados em dois grandes grupos: ordenação interna e externa.

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?

1-ordenação interna: São os métodos que não necessitam de uma memória

2-Ordenação externa : Quando o arquivo a ser ordenado não cabe na memória principal e , por isso , tem de ser armazenado em fita ou disco .

ShellSort , QuickSort , HeapSort e MergeSort são considerados mais eficientes .

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

O algortimo de “ordenação bolha”, ou “bubble sort”, recebeu este nome pela imagem pitoresca usada para descrevê-lo: os elementos maiores são mais leves, e sobem como bolhas até suas posições corretas.

A idéia fundamental é fazer uma série de comparações entre os elementos do vetor.

Quando dois elementos estão fora de ordem, há uma inversão e esses dois elementos são trocados de posição.

Assim, o primeiro elemento é comparado com o segundo. Se uma inversão for 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?

O BubbleSort é um método de simples implementação e de ordem de complexidade quadrática.

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

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

/* Ordenação bolha */

void bolha (int n, int* v)

{

int i,j,temp;

for (i=n-1; i>=1; i--)

for (j=0; j

if (v[j]>v[j+1]) { /* troca */

temp = v[j];

v[j] = v[j+1];

v[j+1] = temp;

}

}

Na quinta linha do código verifica-se os dois elementos se estão desordenados. Se os elementos não estiverem ordenados a troca exige uma variável de armazenamento temporário (temp = v[j+1];) do mesmo tipo que a dos elementos do array que está sendo ordenado.

QUESTIONÁRIO 4 - ÁRVORES AVL

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?

R: Uma arvore AVL é uma arvore binária de busca , (ABB) , auto balanceada , construída de tal modo que a altura de sua subarvore direita difere da altura de sua subarvore esquerda de no máximo 1.

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.

R: Seja c uma nova chave a inserir numa árvore AVL A. Primeiro, c é inserido como folha de A, seguindo o algoritmo 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.

R:A rotação simples segue apenas uma sub-árvore ou seja pela sub-árvore esquerda ou pela sub-árvore direita. Já a rotação dupla segue para ambos os lados da sub-árvore.

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.

R: O passo inicial da remoção consiste em seguir o procedimento aplicado no caso geral de uma ABB. é sempre uma folha que é eliminada da árvore (mesmo quando o valor removido está num nó interior, neste caso o conteúdo de uma folha é transferida nesse nó e a folha é removida). Portanto, a altura das sub arvores que contém esta folha pode ser alterada, e pode ser necessário reequilibrar a árvore, com operações de rotação.

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

R:

Questionário 03 - Árvores Binária de Busca

1- Uma Árvore binária e uma arvore onde cada nó tem no máximo 2 filhos . Uma árvore binária de busca é uma árvore e binária de 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 raiz . Portanto explique como serão inseridos os elementos 10,20,15,18,30,40 e 13 numa árvore binária de busca.

R:

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?

R: Busca : A operação para buscar um elemento na árvore explora a propriedade de ordenação da árvore, tendo um desempenho computacional proporcional a sua altura (0(logn) para o caso de árvore balanceada.

Inserção: A operação de inserção adiciona um elemento na árvore na posição correta para que a propriedade fundamental seja mantida.

Remoção : Essa operação é um pouco mais complexa que a de inserção. Existe três situações possíveis . A primeira , e mais simples, é quando se deseja retirar um elemento que é folha da árvore . Neste caso , basta retirar o elemento da árvore e atualizar o pai, pois seu filho não existe mais.

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<...

R: 8,4,12,2,14,10,6

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çacom relação às árvores binárias comuns?

R: Em pre ordem :

Visita a raiz;

Percorre sua subárvore esquerda, em pré-ordem;

Percorre sua subárvore direita, em pré-ordem;

Percurso em pré-ordem

In-ordem

• Percorrer sua subárvore esquerda, em in-ordem;

• Visitar a raiz;

• Percorrer sua subárvore direita, em in-ordem;

Pós-ordem

• Percorrer sua subárvore esquerda, em pós-ordem;

• Percorrer sua subárvore direita, em pós-ordem;

• Visitar a raiz;

QUESTIONÁRIO 2 - ÁRVORES BINÁRIAS + EXERCÍCIO DO SLIDE

1) Uma árvore é um conjunto de 1 ou mais nós, onde existe um nó especial chamado raíz e os demais nós formam conjuntos disjuntos onde cada conjunto é uma árvore (subárvore). O que caracterizaria então uma árvore Binária?

R : Árvore binária como o próprio nome sugere e um tipo especifico de estrutura na qual o numero máximo de filhos permitindo por nó e dois . Ou seja , um nó pode ter zero , um ou no máximo dois filhos .

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?

R:Sim. 2ⁿ -1.

3) Nas árvores binárias podemos percorrer os elementos através de alguns percursos, quais são eles?

R: EM-Ordem/IN-Ordem

PRÉ-Ordem/PRÉ-fixado

PÓS-Ordem/PÓS-Fixado

4)A definição do percurso EM-Ordem/IN-Ordem é:

R: 1- percorrer sua sub-árvore esquerda, em in-ordem

2- visitar a raiz

3- percorrer sua sub-árvore direita, em in-ordem

5)A definição do percurso PRÉ-Ordem/PRÉ-Fixado é:

R:1- visitar a raiz

2- percorrer sua sub-árvore, em pré-ordem

3- percorrer sua sub-árvore, em pré-ordem

6)A definição do percurso PÓS-Ordem/PÓS-Fixado é:

R: 1- percorrer sua sub-árvore esquerda em pós-ordem

2- percorrer sua sub-árvore direita em pós-ordem

3- visitar a raiz

7)Existe outra maneira de percorrer uma árvore (não obrigatoriamente binária), conhecida como percurso por extensão ou largura. Explique esse processo.

R: Sim . O percurso em largura é mais bem compreendido de forma não-recursiva. O percurso em largura de uma árvore visita os nós na ordem dos níveis da árvore. O percurso em largura primeiro visita todos os nós do nível 0, depois todos os nós do nível um, e daí por diante. Os nós são visitados da esquerda para a direita em cada um dos níveis.
------------------------------------------------------------------------------------------------------------------

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

R: Pré-ordem

ABDGCEHIF

In-ordem

OGBAHEICF

Pós-ordem

GBAHIEFCA