MO417 - Questão para a prova oral

Número: 

Enunciado: Sobre as representações para conjuntos disjuntos é correto afirmar que :

1. Na representação por listas ligadas é utilizada a heurística weighted-union onde a idéia é sempre concatenar a maior lista no final da menor.
2. Usando a representação por listas ligadas e a heurística weighted-union, uma sequência de m operações (MAKE-SET + UNION + FIND-SET) gasta tempo O(m + mlgm).
3. A representação por disjoint-set forest é uma melhoria assintótica em relação com a representação por listas ligadas, porque utiliza as heurísticas weighted-union e path compression.
4. A idéia da heurística path compression consiste em: ao tentar determinar o representante (raiz da árvore) de um nó fazemos com que todos os nós no caminho apontem para a raiz.
5. NDA.

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Assinale a alternativa falsa:

1. Um algoritmo greedy obtém uma solução ótima para um problema, fazendo uma sequência de escolhas.
2. Com a propriedade greddy-choice se pode montar uma solução globalmente ótima, fazendo escolhas localmente ótimas.
3. Um algoritmo de programação dinâmica procede de baixo para cima (bottom up), enquanto uma estratégia greedy geralmente procede de cima para baixo (top down), fazendo uma escolha greedy depois de outra, reduzindo cada instância do problema dada a um problema menor.
4. Um problema apresenta subestrutura ótima se uma solução ideal para o problema contém em si soluções ótimas para subproblemas.
5. NDA.

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Considere as seguintes afirmações: 
  
  (I)  É possível obter todas as LCS de dois sequências X e Y a partir da matriz de distâncias "c", retornada pelo algoritmo LCS-LENGTH(X, Y).

 (II)  O seguinte algoritmo imprime corretamente uma LCS de dois secuencias X e Y, em O(X.lentgh+Y.length), a partir de a matriz de distâncias "c"  devolvido pelo algoritmo LCS-LENGTH(X, Y):

                            PRINT_LCS( c, X, Y, i, j)

                            1   if  i == 0 or j == 0

                            2       return 

                            3   if  Xi == Yj

                            4       PRINTF_LCS(c, X, Y, i-1, j-1)

                            5       print Xi

                            6   else if  c[i-1][j] ≥ c[i][j-1]

                            7       PRINTF_LCS(c, X, Y, i-1, j) 

                            8   else PRINTF_LCS(c, X, Y, i, j-1)

A primeira chamada do algoritmo é: PRINT_LCS( c, X, Y, X.length, Y.length)

 (III)  O seguinte algoritmo imprime corretamente uma LCS de dois secuencias X e Y, em O(X.lentgh+Y.length), a partir de a matriz de distâncias "c"  devolvido pelo algoritmo LCS-LENGTH(X, Y), em O(X.lentgh+Y.length):

                            PRINT_LCS( c, X, Y, i, j)

                            1   if  i == 0 or j == 0

                            2       return 

                            3   if  Xi == Yj

                            4       PRINTF_LCS(c, X, Y, i-1, j-1)

                            5       print Yj

                            6   else if  c[i-1][j]  <  c[i][j-1]

                            7       PRINTF_LCS(c, X, Y, i, j-1) 

                            8   else PRINTF_LCS(c, X, Y, i-1, j)

A primeira chamada do algoritmo é: PRINT_LCS( c, X, Y, X.length, Y.length)

Assinale a alternatica correta:

1. Somente (I) é verdadeira.
2. Somente (III) é verdadeira.
3. (I) e (II) são verdadeiras.
4. Todas são verdadeiras.
5. NDA

Ideia original de: Jhon Anthony Campos Arteaga