Enunciado distribuido na sala.
A ordem certa é a seguinte, sendo que as duas primeiras podem ser intercambiadas pois são iguais:
(lg n)lg n
nlg lg n
√ n
2lg* n
Justificativas podem ser dadas em todos os casos tomando o lg dos dois lados.
A questão valia 2,5 pontos. O critério de correção foi: 1,0 ponto pela ordem correta, e mais 0,5 para cada justificativa aceita. Teve gente que colocou coisas do tipo "a função lg* n cresce tão lentamente que mesmo n sendo o número de móleculas no universo ..." mas sem aplicar lg ou log para compará-la com outra. Este tipo de argumentação não foi considerada suficiente.
Esta questão era a mais difícil da prova. O método mestre não pode ser aplicado, pois a recorrência não satisfaz às condições (1), (2) nem (3) cobertas pelo método, já que n lg n não é Ω(n1+ε) para nenhum ε positivo.
Então o remédio é montar a árvore de recursão. Esta árvore tem log3n níveis, sendo que o nível i tem 3i nós com trabalho total n lg(n/3i), exceto o último que é composto de n folhas com trabalho total n.
Assim, a complexidade é dada pela fórmula:
log3n - 1 ∑ (n lg(n/3i)) + n i=0
que, após expansão, dará O(n lg2n).
Esta possibilidade pode ser verificada por substituição supondo T(n) ≤ (n lg2n)/(2 lg 3) + (n lg n)/2 + n. Uma alternativa para quem não quis ou não conseguiu fazer as contas do somatório até o fim seria esta verificação por substituição, ou outra que também funcionasse.
O critério de correção nesta questão ligou-se à árvore de recursão. A fórmula final da complexidade valia 1,0 ponto, e suas duas componentes principais, a saber, a somatória dos níveis e a parcela devida às folhas, valiam 1,0 ponto cada. Além disso, foram dados 0,5 pontos para outras informações importantes, por exemplo, quem tentou fazer pelo teorema mestre e concluiu que ele não podia ser aplicado ganhou 0,5 por esta conclusão.
A questão mais fácil da prova. Os heaps são:
51, 38, 12, 20, 27, 11, 1, 10, 3, 6, 15, 2: heap original
51, 40, 12, 20, 38, 11, 1, 10, 3, 6, 27, 2: após 15 → 40 e rearranjo
40, 38, 12, 20, 27, 11, 1, 10, 3, 6, 2: após remoção do máximo e rearranjo
O critério foi simples: cada heap exceto o original valia 1,0 ponto. Acho que ninguém errou o primeiro. Teve gente que errou o segundo porque não trocou com a última folha (2) para poder remover esta última folha e daí rearranjar, mas já removeu a raiz na maior e rearranjou. Como conseqüência, ficou uma árvore binária incompleta, faltando uma folha no lugar originalmente ocupado pelo 15.
Esta questão também não foi fácil. Pouca gente acertou. A saída era bolar um novo algoritmo, não visto em aula, que vai trocando os registros no próprio arranjo A. Usa-se o fato de que a chave já é a posição final do registro. Uma solução nesta linha seria:
1. for i <- 1 to n do 2. while i <> A[i].key do 3. trocar A[i] <-> A[A[i]]
O critério de correção foi o seguinte. Correção valia 1,0 ponto, rodar em O(n) valia 0,5 pontos e ser local (in place) valia 0,5 pontos. O 0,5 ponto restante ficava como bônus para quem conseguisse as três coisas.
Teve gente que propôs o counting sort, que atende duas das condições mas não é local. Ganharam 1,5 pois está correto e roda em O(n). Teve gente que teve a ideia certa, porém escreveu um algoritmo semelhante à solução que demos acima, mas no lugar do while na linha 3 tinha um if. Infelizmente não funciona, como mostra o exemplo 3,4,2,1: acaba em 2,1,3,4, ou seja, não ordenado. Estes ganharam 1,5 porque considerei 0,5 no quesito "correção".
Teve um colega que fez duas passagens, ou seja, o código acima com if, mas repetido duas vezes. Infelizmente também não funciona, como mostra o exemplo 5,6,7,8,3,4,2,1: acaba em 2,1,3,4,5,6,7,8, ou seja, não ordenado. Mas também ganhou 1,5 na questão.
© 2009 João Meidanis