av1 algoritmos avançados

Prévia do material em texto

Disciplina:​Algoritmos Avançados 
Professora: ​Larissa Luz Gomes 
Aluno:​Pablo Andel Silva Pereira 
Matrícula: ​201602836159 
 
 
 
 
 
1ª) ​Algoritmos Recursivos: 
 
Em programação, a recursividade é um mecanismo útil e poderoso que permite a uma 
função chamar a si mesma direta ou indiretamente, ou seja, uma função é dita 
recursiva se ela contém pelo menos uma chamada explícita ou implícita a si própria. 
Para todo algoritmo recursivo existe um outro correspondente iterativo (não 
recursivo), que executa a mesma tarefa. 
 
 
A) Com base nas aulas e exercícios que fizemos, explique o porquê de usar um 
algoritmos recursivo para solucionar um problema, ao invés do seu 
correspondente iterativo? 
A utilização de um algoritmo recursivo ao invés de seu correspondente iterativo se 
dá pelo motivo da fácil compreensão dos resultados e a fácil implementação em 
linguagens de programação de alto nível 
 
A) Explique quando NÃO se deve usar uma função recursiva e por que? 
A função recursiva não deve ser utilizada em casos que o algoritmo for de 
implementação simples e que não haverá utilização de pilhas. À função recursiva é 
um função que chama a si mesmo de forma direta ou indireta utilizando de forma 
intensa as pilhas alocando e desalocando memória tendendo à ter um desempenho 
menor que seu correspondente iterativo. 
 
2ª) Faça uma comparação, em relação a complexidade, dos algoritmos de ordenação 
de Quicksort e MergeSort. (0,5 pt) 
O MergeSort é mais complexo pois divide o problema ou vetor independente do seu 
caso em subproblemas com o intuito de resolvê-los combinando os resultados para a 
resolução do problema original. O QuickSort tem uma complexidade semelhante à do 
MergeSort, porém necessita apenas de uma pequena pilha como memória auxiliar e 
seu tempo de execução depende dos dados de entrada. 
 
 
 E quando usar o algoritmo de Quicksort e MergeSort? (0,5 pt) 
 
Os algoritmos Quicksort e MergeSort devem ser utilizados quando elementos de uma 
lista devem ser ordenados. À ordenação tem o objetivo de recuperar dados da lista de 
forma prática e eficiente. 
 
3ª) A árvore AVL é uma árvore binária de busca balanceada, ou seja, uma árvore 
balanceada (árvore completa) são as árvores que minimizam o número de 
comparações efetuadas no pior caso para uma busca com chaves de probabilidades 
de ocorrências idênticas. Contudo, para garantir essa propriedade em aplicações 
dinâmicas, é preciso reconstruir a árvore para seu estado ideal a cada operação 
sobre seus nós (inclusão ou exclusão), para ser alcançado um custo de algoritmo 
com o tempo de pesquisa tendendo a O (log n)} Então, quando deve ser usada uma 
Árvore AVL, visto que a cada operação de inclusão ou exclusão a árvore deve ser 
rotacionada caso a operação deixe a árvore desbalanceada? (1,0 pt) 
 
Está estrutura permite inclusão e exclusão em tempo logarítmico por isso é recomendada 
em casos que se quer balancear à árvore utilizando rotações. 
 
4ª) 
Como foi visto em nossas aulas, para todo algoritmo recursivo existe um outro 
correspondente iterativo (não recursivo), que executa a mesma tarefa. Escolha um 
problema que pode ser implementado por Recursividade (EX. Fatorial) e implemente o 
algoritmo de maneira RECURVISA e seu correspondente ITERATIVO. (1, 0 pt​) 
 
Algoritmo Fatorial Recursivo 
 
def fatorial (n) 
If n == 0 or n == 1 
return 1 
else: 
return n * fatorial(n - 1) 
 
Correspondente Iterativo 
 
def f(n) 
 if n == 0: 
 return 0 
 if n == 1 
 return 1 
 if n > 1: 
 return f( n - 1) * n 
 
 
 
 
 
Após implementar os algoritmos mostre por que o algoritmo Recursivo é mais 
indicado para 
implementar do que o Iterativo. (use a complexidade para justificar sua resposta) (1,0 
pt) 
 
À diferença de complexidade entre os dois algoritmos se da ao seu tempo de 
execução. O algoritmo iterativo repete à operação até ela estar completa tendo à 
complexidade de O(n). O algoritmo recursivo quebra o problema em subproblemas 
até resolvê-lo tendo uma complexidade de O(2^n). Sendo assim o algoritmo recursivo 
tem um complexidade exponencial e o iterativo uma complexidade linear o que pode 
impactar na hora da implementação. 
 
5) Com base na árvore abaixo, escreva como fica a sequência das letras para os 
percursos: pré-ordem, in-ordem e pós-ordem . (1,5 pt) 
 
Pré ordem: ​13-10-5-4-8-11-15-16 
Em ordem: ​4-5-8-10-11-13-16-15 
Pós Ordem: ​4-8-5-11-10-16-15-13 
 
 
Quando devem ser usados cada um dos 3 percursos da questão anterior? (1,0 pt) 
 
Pré Ordem: ​Este percurso é utilizado quando se quer começar no nó atual, seguindo os 
seguintes passos: se tiver filhos na esquerda executa à pré ordem; se tiver filhos na direita 
executa à pré ordem. 
 
Pós Ordem: ​Executado se tiver filho à esquerda; Executado se tiver filho à direita ou 
executa à operação no nó atual 
 
Em Ordem: ​Quando se quer executar a operação seguindo os seguintes passos: se houver 
filhos à esquerda executar a operação; executar à operação no nó atual; se houver filhos à 
direita executar a operação. 
 
 
 
 
 
6ª) Rotação em Árvore AVL: 
Construa um algoritmo(simples) que verifique se uma árvore AVL está balanceada ou 
não. (1,5 pt). 
 
def b_d (lado_direito, lado_esquerdo): 
 
fb = lado_direito - lado_esquerdo 
If (fb == 0): 
 
Print (“ lado direito e esquerdo com altura igual) 
 
elif (fb == -1): 
 
Print (“ lado esquerdo e maior que o direito com 1”) 
 
elif(fb == 1): 
 
print (“ lado direito e maior que o esquerdo com 1”) 
 
 
 
Se a árvore AVL ficar desbalanceada depois de uma operação de inserção ou 
remoção, construa um 
algoritmo para balancear esta árvore novamente. (1,0 pt). 
 
static Node rotacao(Node y) 
{ 
Node x = y.direita; y.direita = x.esquerda; x.esquerda = y; 
return x; 
}