MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa correta:

1.)Se um problema P1 se reduz a um problema P2 en tempo polinomial, então P2 é NP 
2.)Se um algoritmo verifica um problema P1 em tempo polinomial, então P1 é NP
3.)Se um algoritmo verifica um problema P1, então P1 é NP-Completo
4.)Se qualquer problema NP-difícil pode ser reducido a B em tempo polinomial, então P = NP
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido G=(V,E):
 

  

Seja w e W a função de peso e a matriz de pesos do grafo G respetivamente. Suponha que seu vetor de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa correta sobre os caminhos mais curtos entre todos os pares de vértices do grafo G: 

1.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16. 

2.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em Θ( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.

3.)Johnson(G,w) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5³), também o caminho mais longo dos caminhos mais cortos é  d_ea= 16.
4.)Floyd-Warshall(W) calcula todos os caminhos mais curtos entre todos os pares de vértices de G em O( 5² lg 5 + 45), também o caminho mais longo dos caminhos mais cortos é  d_ed= 15.
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga

MO417 - Questão para a prova oral

Número: 

Enunciado: Dado o seguinte grafo dirigido A=(V,E)  :

  

Y os seguintes algoritmos:

DFS(G)                                                      

1 for each vertex u ∈ G.V                         

2       u.color = WHITE                            

3       u.π = NIL                                        

4 time = 0                                                 

5 for each vertex u ∈ G.V                          

6       if u.color == WHITE                       

7           DFS-VISIT(G,u)                        

                                                                                                                         
DFS-VISIT(G,u)  

1 time = time + 1
2 u.d = time
3 u.color = GRAY 
4 for each v ∈ G.Adj[u] 
5       if v.color = = WHITE 
6             v.π = u  
7             DFS-VISIT(G,v) 
8 u.color = BLACK 
9 time = time + 1 
10 u.f = time
  
Suponha que seu vetor de listas de listas de adjacência como seus lista de adjacência de cada vértice estam armazenados em orden alfabética. Assinale alternativa que contém o valor π correto de cada um dos vertices do grafo A, após da execução do algoritmo DFS(A): 

1.)a.π = f, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = b, g.π = NIL
2.)a.π = NIL, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = b, g.π = NIL
3.)a.π = NIL, b.π = a, c.π = b, d.π = d, e.π = NIL, f.π = b, g.π = NIL
4.)a.π = NIL, b.π = a, c.π = d, d.π = b, e.π = NIL, f.π = NIL, g.π =b
5.)NDA

Ideia original de: Jhon Anthony Campos Arteaga

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

MO417 - Questão para a prova oral

Número: 

Enunciado: Considere as seguintes afirmações: 
  
  (I)  Para localizar simultaneamente o elemento mínimo e o elemento máximo de um vetor com n elementos, onde n é impar, tem 3*(floor(n/2)) comparações. Se removemos o primeiro elemento do vetor o número de comparações para localizar simultaneamente o elemento mínimo e o elemento máximo é  3*(floor(n/2))  - 7/2.

 (II)  O algoritmo RANDOMIZED-SELECT pode encontrar o i-th elemento mais large de um vetor em Θ(n)

(III)  O tempo de execução do algoritmo RANDOMIZED-SELECT quando o vetor de entrada é ordenada em forma crescente é Θ(n²)

Assinale a alternatica correta:

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

Ideia original de: Jhon Anthony Campos Arteaga