Resumao AP3

Prévia do material em texto

(1,0) Algoritmo Ótimo. (2007-1) 
Um algoritmo é ótimo quando sua complexidade de pior caso é igual ao limite inferior para o problema. 
 
(1,0) Complexidade de PIOR caso de um Algoritmo (2008-1) 
Sejam A um algoritmo, E = {E1, · · · , En} o conjunto de todas as entradas possíveis de A e Ti o número de passos 
efetuados por A, quando a entrada for Ei. A complexidade de pior caso de A é definida por max Ei ∈ E {Ti| Ei ∈ E}. 
 
(1,0) Complexidade de MELHOR caso de um algoritmo. (2008-2) 
Sejam A um algoritmo, E = {E1, · · · , En} o conjunto de todas as entradas possíveis de A e Ti o número de passos 
efetuados por A, quando a entrada for Ei. A complexidade de melhor caso de A é definida por min Ei ∈ E {ti | Ei ∈ E}. 
 
A complexidade de melhor caso se dá quando o elemento buscado está na posição 
Por exemplo na busca pelo elemento 3 na lista L = 1; 2; 3; 4; 5. A complexidade de pior caso ocorre quando 
reduzimos a lista a apenas um elemento a medida que descartamos sucessivas metades das listas nas buscas 
intermediárias. Por exemplo quando buscamos o elemento 6 na lista L anterior. 
 
(1,0) Limite Inferior de um Problema (2008-1) 
O limite inferior de um problema P é uma função l tal que a complexidade de pior caso de qualquer algoritmo que 
resolva P é Ω(l). 
 
(1,0) Algoritmo recursivo. ----- (AP1 / 2017-2) 
É um algoritmo que contém ao mínimo uma chamada a si mesmo. Todo algoritmo recursivo possui um 
procedimento não-recursivo em sua composição. 
 
(1,5) Defina árvore Binária de Busca ----- (2015-1) 
 cada nó possui 0, 1 ou 2 filhos 
 todos os elementos da subárvore esquerda são menores que o elemento pertencente à raiz 
 todos os elementos da subárvore direita são maiores que o elemento pertencente à raiz 
 
(1,0) Explique o conceito de ALTURA de uma árvore binária. (AP1 / 2012-1) 
A altura de uma árvore binária é o número de nós do maior caminho da raiz até uma folha. 
 
(1,0) Explique o conceito de árvore ESTRITAMENTE binária. (AP1 / 2012-1) 
Uma árvore é estritamente binária se cada nó possui 0 ou 2 filhos. 
 
(1,0) Explique o conceito de árvore binária CHEIA. (AP1 / 2012-2) 
É aquela em que todas as subárvores vazias se localizam no último nível. 
 
(1,0) Explique o conceito de árvore binária completa. (2011-2) 
É uma árvore binária (cada nó possui no máximo 2 filhos) e é cheia até o penúltimo nível. 
 
(1,5) Conceitue árvore zigue-zague. (2007-2) 
Árvore zigue-zague é uma árvore binária cujos nós interiores possuem exatamente 
uma subárvore vazia. 
 Desenhe uma árvore binária de busca zigue-zague de altura 4, colocando os valores 
das chaves dentro dos nós. 
 
 
PERCURSOS DA ÁRVORE BINÁRIA 
Pré-ordem Pós-ordem Ordem Simétrica 
RED 
Raiz 
Esquerda 
Direita 
EDR 
Esquerda 
Direita 
Raiz 
ERD 
Esquerda 
Raiz 
Direita 
 
(1,0) Árvores balanceadas - AVL. (2008-1) 
Uma árvore binária T é uma árvore AVL quando todos os seus nós estão regulados (as alturas das suas subárvores 
esquerda e direita diferem em módulo de até uma unidade). 
 
Uma árvore é balanceada quando o custo das operações de busca, inserção, remoção e arrumação da estrutura 
mantem-se em O(log n). 
 
(2,5) Explique como efetuar a inclusão de um nó numa árvore AVL. (2006-1) 
Após efetuar a inclusão de um nó, percorre-se o caminho ascendente que vai deste nó até a raiz, e verifica-se se 
existe algum nó que se tornou desregulado (isto é, tal que a diferença de altura entre as duas subárvores da árvore 
tornou-se maior que um). Em caso afirmativo, podemos aplicar uma transformação apropriada para regulá-lo. 
 
Rotações nas árvores AVL 
RDD 
Rotação Dupla Direita 
RDE 
Rotação Dupla Esquerda 
RD 
Rotação Direita 
RE 
Rotação Esquerda 
 
 
(2,0) Arvore B de ordem d (2012-1) 
Seja d um número natural. 
Uma árvore B de ordem d é uma árvore ordenada que satisfaz as seguintes propriedades: 
 se a raiz não é uma folha, possui no mínimo 2 filhos; 
 cada nó interno diferente da raiz possui no mínimo d+1 filhos; 
 cada nó possui no máximo 2d + 1 filhos; 
 todas as folhas estão no mesmo nível. 
 
(1,5) Conceitue HEAP. --- HEAP - lista de prioridades 
 Desenhe um heap de altura 4, colocando as prioridades dentro dos nós. (2007-2) 
Um heap é uma lista linear composta de elementos com 
chaves S1, ... , Sn satisfazendo Si ≤ S L i/2 ˩ ..... 1 ≤ i ≤ n. 
 
 
 
(1,0) Função de dispersão (2008-2) 
É uma função que transforma uma chave x em um endereço-base h(x) da tabela de dispersão. 
 
 (2,5) Explique como funciona uma tabela de dispersão em que as colisões são tratadas por encadeamento 
exterior. (2006-1) 
O tratamento de colisões por encadeamento exterior consistem em manter M listas encadeadas, uma para cada 
possível endereço-base. Um campo para o encadeamento deve ser acrescentado a cada nó. Os nós correspondentes 
aos endereços-base são apenas nós-cabeça para essas listas. 
Para buscar uma chave x na tabela T, calcula-se h(x) = x mod m e procura-se x na lista encadeada correspondente ao 
endereço-base h(x). A inclusão de uma nova chave X é feita no final da lista encadeada correspondente ao endereço-
base h(x). 
desregulado * 
 
* desregulado 
 
* desregulado 
 
* desregulado 
 
 (1,0) Colisão (2012-1) 
Fenômeno que ocorre quando o compartimento h(x) (determinado para armazenar a chave x) já está ocupado por 
uma chave y. 
 
(1,0) Arvore de Huffman (2011-1) 
Uma árvore de Huffman é uma árvore estritamente binária (0 ou 2 filhos) de prefixo que possui custo mínimo para 
um conjunto de símbolos (texto) e suas respectivas frequências. 
 
 
*** EXERCÍCIOS DE VERDADEIRO OU FALSO *** 
 
(2010-2) (Valor 4,0): Responder se cada afirmativa abaixo é falsa ou verdadeira, justificando a resposta, em cada 
caso: 
(1,0) Uma árvore binária com N nós, que possua o número máximo de folhas é necessariamente cheia. 
FALSO. Para n = 5, por exemplo, a árvore binária possui no máximo 3 folhas, mas não é possível obtermos uma 
árvore cheia com este número de nós. 
 
(1,0) A complexidade de pior caso do algoritmo Heapsort (que utiliza um heap para efetuar a ordenação de uma lista 
de elementos) é expressa por uma função F que satisfaz F = Ω(n 2). 
FALSO. A complexidade de pior caso do algoritmo Heap-sort é Θ(n log n). 
A função F = n log n não é Ω(n2) (mas sim Ω(n log n)). 
 
(1,0) Seja um algoritmo cuja entrada consiste de um número inteiro n. Se o número de passos deste algoritmo for 
igual a N, e cada passo for executado em tempo constante, pode-se afirmar que o algoritmo possui complexidade 
linear no tamanho da entrada. 
VERDADEIRO. Neste caso, a complexidade do algoritmo é O(n), sendo portanto linear no tamanho da entrada. 
 
(1,0) Sejam dois algoritmos distintos que resolvem um mesmo problema. Se ambos forem ótimos, pode-se concluir 
que ambos possuem complexidades idênticas de pior caso, e complexidades idênticas de melhor caso. 
FALSO. Sendo ambos os algoritmos ótimos, podemos apenas concluir que suas complexidades de pior caso são da 
mesma de grandeza. Nada podemos afirmar a respeito da complexidade de melhor caso destes algoritmos. 
 
 
Falso ou verdadeiro? (Justifique.) ----- (2013-1) 
(1,0) Seja h(n) a altura mínima de uma árvore binária com N nós. Então h(n) = Ω(log n). 
VERDADEIRO. A altura mínima de uma árvore binária com N nós é h(n) = 1 + ⌈log n⌉. 
Como a notação Ω limita inferiormente uma função, temos h(n) = Ω(log n). 
 
(1,0) Seja h(n) a altura máxima de uma árvore binária com N nós. Então h(n) = O(log n). ----- (2013-1) 
FALSO. A altura máxima de uma árvore binária com n nós é h(n) = n ( árvore zigue-zague). Como a notação O limita 
superiormente uma função, temos h(n) = O(n). 
 
Considere a seguinte estrutura de dados: Lista Encadeada Ordenada. Para cada item abaixo, forneça a 
complexidade do algoritmo que realiza a tarefa indicada, utilizando a notação O: ----- (2013-1) 
 
(a) (1,0) Busca de um elemento qualquer. 
Resposta: O(n). 
(b) (1,0) Inserção de um elemento com valor menor do que todos os que estão na lista. 
Resposta: O(1).