domingo, 30 de janeiro de 2011

103-2005

MO640 - Questão para a prova oral
Número: 103
Enunciado:
Com relação ao primeiro algoritmo para a construção de árvores PQR, descrito em On the consecutives ones property por Meidanis et al, qual passo do algoritmo não pode ser executado em tempo linear?
  1. Encontrar um conjunto H não-trivial.
  2. Decompor o problema em dois sub-problemas.
  3. Juntar as árvores de cada sub-problema.
  4. Testar se uma coleção prima é trivial.
  5. NDA
Autor(a): Marcelo de Almeida Oliveira

2 comentários:

  1. a) Correta. No presente momento não sabemos se esse passo está em tempo linear.

    b) Errada. Esse passo é em tempo linear, pois
    é a soma do tamanho dos conjuntos.

    c) Errada. Nesse passo, cada operação para juntar as árvores é constante, para cada nó o tempo total é linear.

    d) Errada. Pois esse passo só verifica se possui restrições.

    e) Errada.

    ResponderExcluir
  2. Oi Diego,

    Bom comentário. Só queria que você mudasse o seguinte:

    (a) não se diz "está" em tempo linear. Melhor dizer "pode ser executado" em tempo linear.

    (b) novamente, é melhor trocar "é em tempo linear" por "pode ser executado em tempo linear". E a segunda frase deveria ser mais clara: "pois o esforço necessário é proporcional à soma dos tamanhos dos conuntos".

    (c) Não entendi o que você quis dizer com "para cada nó o tempo total é linear". A operação pode ser executada em tempo constante ou não?

    ResponderExcluir