Notas do 1º Exame

14 junho 2013, 22:45 • Carlos Filipe Gomes Bispo

Olá a todos,

Foram afixadas as notas do 1º Exame. Cumpre-me lamentar a fraca qualidade da preparação do alunos que compareceram a esta prova (49 alunos). A média foi de 7,85 Valores e a nota mais alta foram uns meros 12,59 Valores.

Apenas 9 alunos acertaram a questão 2, 12 alunos acertaram a questão 5, e 15 alunos acertaram a questão 7. A maior surpresa é a questão 7, dado tratar-se de um exercício absolutamente trivial de tabelas de dispersão.

Quanto às questões de desenvolvimento, quebro excepcionalmente a regra de não publicar soluções, apenas porque espero com o texto abaixo fazer com que os alunos percebam o que se entende por uma resposta com pés e cabeça. Considerem a Questão 11.

Pedia-se que os alunos discutissem a complexidade temporal da operação de procura numa tabela de dispersão com colisões resolvidas por inserção em árvore ordenada. Dizia-se que o número de dados a inserir na tabela de dispersão (N) era maior que a dimensão da tabela (M).

Dizia-se também para se assumir que a função de dispersão garantia uma dispersão uniforme pelos índices da tabela.

Então cá vai:

Questão 11 a)

"Dado que a função de dispersão assegura uma distribuição uniforme dos números a inserir na tabela, tal significa que, em média, cada posição da tabela de dispersão aponta para uma árvore ordenada de tamanho N/M. Isto é, N números uniformemente distribuídos em M endereços.

A altura de uma árvore binária (ordenada ou não) com N/M vértices varia entre log(N/M) e N/M (ver acetato 56 do ficheiro 07-Tree.pdf). Este último caso, o pior caso para a altura, acontece quando a árvore degenera numa lista. A altura média de uma árvore binária é log(N/M) (ver actetatos 121 e 122 do ficheiro 07-Tree.pdf).

Assim, relativamente à operação de procura, isto é, determinar se um dado número está presente na tabela de dispersão as operações a executar são: aplicar a função de dispersão a esse número para obter o índice da tabela onde o número terá de estar (operação O(1)); de seguida procurar na árvore ordenada se o número lá está (operação que depende da altura da árvore).

Como a árvore é ordenada, a procura com insucesso só percorre a árvore toda se esta for uma lista. Caso não seja uma lista, cada comparação com a raíz permite decidir se a procura pára, se continua à esquerda ou se continua à direita.

Em síntese, a procura por um número na tabela de dispersão varia entre O(N/M) e O(log(N/M)), com ou sem sucesso, dado que o sucesso pode também acontecer numa folha. Não é útil indicar que pode ser metade daqueles valores, porque esse factor multiplicativo não altera o carácter do comportamento assimptótico."

Questão 11 b)

Aqui pedia-se para repetir a análise anterior se a árvore ordenada fosse também balanceada AVL.

"Para árvores ordenadas balanceadas AVL a altura mínima, máxima e média coincidem a menos de um ponto. Ou seja, pode assumir-se que uma árvore AVL tenha sempre altura igual a log(N/M) para todas as entradas da tabela de dispersão.

Assim, a operação de procura tem a mesma complexidade em pior e caso médio. Tal complexidade é O(log(N/M))."

Questão 11 c)

NA EXCLUSIVA PERSPECTIVA DA OPERAÇÃO DE PROCURA, qual preferir? Resolução de colisões em lista simples? Resolução de colisões em árvore ordenada? Resolução de colisões em árvore ordenada balanceada AVL?

"Face à discussão das alíneas a) e b), deverá ser evidente que a melhor escolha para efeitos de complexidade temporal da operação de procura é a terceira opção."

Não faria sentido discutir aqui questões relacionadas com inserção, porque se pedia apenas uma discussão relativa à operação de procura. Também não é correcta a afirmação de que a lista simples ocuparia menos memória que a árvore ordenada. Se por um lado não se pedia tal discussão, a afirmação é falsa. Tecnicamente, uma lista simples ou uma árvore binária contendo o mesmo número de objectos ocupa a mesma memória. Sendo verdade que numa lista só há um ponteiro e numa árvore binária há dois, acontece que cada objecto na lista ou na árvore é apontado por apenas um ponteiro.

Carlos