2º Exame

1 julho 2013, 16:21 • Carlos Filipe Gomes Bispo

Olá a todos,

Estão afixadas as notas do 2º Exame na secção PAUTAS.

A revisão de provas terá lugar na quarta-feira, dia 3 de Julho, às 10:00 na sala 5.15 da Torre Norte.

Carlos

Exame de Época Especial

27 junho 2013, 19:43 • Carlos Filipe Gomes Bispo

Olá a todos,

Nos registos do sistema Fénix não existe de momento qualquer aluno inscrito para exame de Época Especial.

De acordo com o calendário escolar do IST, os exames de Época Especial têm de ter lugar entre 8 de Julho e 20  de Julho. De acordo com o Conselho de Gestão do IST e porque o segundo exame teve lugar no dia de greve geral, qualquer aluno, de entre os que estavam inscritos no sistema Fénix para o realizar, que faça prova de se ter visto impossibilitado de comparecer à prova devido à greve geral, tem direito à realização do exame de Época Especial.

Assim, solicitam-se duas coisas aos alunos que estejam em situação de poder requerer exame de Época Especial.

1. Que façam a inscrição na secretaria do IST para a prova;

2. Contactem o Prof. Carlos Bispo para se acertar a data da realização da prova.

Carlos

Inscrições para o 2º Exame

19 junho 2013, 03:58 • Carlos Filipe Gomes Bispo

Olá a todos,

Informam-se os alunos interessados que o período de inscrições para o 2º Exame terá início na quarta-feira, dia 19 de Junho às 10:00 e conclui-se às 18:00 do dia 25 de Junho.

Mais uma vez se apela aos alunos para que não deixem para tarde a sua manifestação de intenção de realizar o referido exame.

Está convocada uma greve geral para o dia do 2º Exame. Informo que não irei aderir à greve, pelo que a prova se realizará no dia e hora para que está marcada. Aos alunos que queiram realizar este exame compete assegurarem-se de que têm forma de chegar à escola a horas da prova.

Carlos

Revisões de provas

14 junho 2013, 23:52 • Carlos Filipe Gomes Bispo

Olá de novo,

A revisão de provas do 1º exame terá lugar na sala 5.15 da Torre Norte, na segunda-feira, dia 17/06, às 15:00.

Os alunos de grupos de projecto que pretendam realizar oral de recurso, deverão comunicar a partir de agora essa sua intenção ao docente que avaliou o seu projecto. As orais de recurso terão que ter lugar na semana de 17/06 a 21/06.

Quanto mais cedo entrarem em contacto com o docente em causa, mais cedo se poderão marcar e realizar essas provas.

Carlos

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