MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: O problema do ciclo de Hamiltoniano (HAM-CYCLE) e o problema do caixeiro viajante (TSP) são bastantes conhecidos da teoria de NP-completude. Sabendo que HAM-CYCLE é NP-completo e que TSP é NP, para provar que TSP é NP-completo, basta mostrar que TSP é NP-difícil apresentando uma redução polinomial do HAM-CYCLE para o TSP. Quantas arestas são necessárias adicionar ao grafo abaixo para realizar tal redução? 

 

 

Observação: o grafo acima apresenta HAM-CYCLE.

1. 1
2. 3  
3. 10
4. 12
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: No grafo abaixo, execute o algoritmo básico de Ford-Fulkerson para resolver o problema do fluxo máximo, onde o nó S é a origem e o nó T é o solvedor.

Supondo que na primeira iteração do algoritmo foi selecionado o caminho aumentante S → V3 → V2 → T e na segunda iteração foi selecionado o caminho aumentante S → V2 → V1 → T, marque a alternativa correta contendo apenas capacidades de fluxo de arestas do grafo residual após a execução das duas primeiras iterações do algoritmo.

1.  c_f(S,V2) = 2,  c_f(V2,S) = 5, c_f(V1,T) = 5, c_f(T,V1) = 10;
2.  c_f(S,V2) = 5,  c_f(V2,S) = 2, c_f(V1,T) = 5, c_f(T,V1) = 10;
3. c_f(V2,T) = 2,  c_f(T,V2) = 8, c_f(V1,T) = 10, c_f(T,V1) = 5;
4. c_f(V2,T) = 8,  c_f(T,V2) = 2, c_f(V1,T) = 5, c_f(T,V1) = 10;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Um grupo de pesquisadores desenvolveram um módulo de navegação para robôs, usando o algoritmo de Djikstra, que soluciona o problema do caminho mais curto de única origem. Dois robôs-protótipos, construídos com as mesmas configurações de hardware, foram posicionados em salas diferentes, marcadas com as letras 'A' e 'B', de um labirinto projetado conforme o grafo abaixo. Os robôs se deslocam entre as salas do labirinto, seguindo a direção das arestas do grafo, e percorrendo uma distância equivalente ao peso dessas arestas. 

Sabendo que o robô campeão é quem chega primeiro à sala 'G' e que apenas um robô pode ser campeão, marque a alternativa correta com o percurso do robô campeão, e as respectivas estimativas de caminhos mais curtos de cada sala percorrida.

1. Robô A: A(0) → E(2) → C(4) → D(8) → G(9)
2. Robô A: A(0) → E(2) → C(6) → D(8) → G(9)
3. Robô B: B(0) → F(1) → E(2) → C(4) → D(8) → G(9)
4. Robô B: B(0) → F(1) → D(8) → G(9)
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

 

Enunciado: Dado o grafo abaixo, suponha que tanto o seu vetor de listas de adjacência como cada uma de suas listas de adjacência estão armazenados em ordem alfabética. Após a execução do algoritmo de  busca em profundidade a partir do vértice "a", marque a alternativa que exibe corretamente a estrutura de parênteses.
 

1. (a (b (d d) (c c) a)  b) (e e) (f f)
2. (a (b (c c) (d d) (e e) (f f) b) a)
3. (a (b (c c) (d (e e) (f f) d) b) a)
4. (a (b (d (e e) (f f) d) b) (c c) a)
5. NDA.

 

Ideia original de: Laurindo de Sousa Britto Neto

 

MO417 - QUESTÃO PARA PROVA ORAL

Número: 

Enunciado: O conjunto de chaves { 3, 7, 5, 19, 18, 15, 25, 20, 10} exibe o percurso em pós-ordem de uma árvore de pesquisa binária. Após duas remoções do nó raiz, qual será a nova chave da raiz dessa árvore de pesquisa binária? 

1. 7
2. 15
3. 18
4. 20
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número: 

Enunciado: Para resolver um problema de otimização, foram propostos dois algoritmos: o primeiro utilizando o método de Divisão e Conquista e o segundo baseado em Programação Dinâmica. Dado o enunciado anterior, analise as afirmações abaixo e assinale a alternativa correta:

I.  Ambos os métodos resolvem problemas combinando soluções para subproblemas;

II. Quando a solução de um subproblema depende da solução de outro subproblema, o método de Divisão e Conquista é o mais adequado para resolver o problema; 

III. Memoização é uma abordagem top-down para implementação da Programação Dinâmica de forma recursiva;

IV. Na Programação Dinâmica cada subproblema é resolvido apenas uma vez.

1. Apenas as alternativas I e II estão corretas;
2. Apenas as alternativas I e IV estão corretas;
3. Apenas as alternativas III e IV estão corretas;
4. Apenas as alternativas I, III e IV estão corretas;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Qual modificação devemos realizar no algoritmo PARTITION, para utilizá-lo como rotina auxiliar de um algoritmo que determina o i-ésimo menor elemento de um vetor em tempo linear no pior caso? Observação: pivô é um elemento do vetor ao redor do qual será feito o particionamento.

  PARTITION(A, p, r)

  1. x = A[r]       /* A[r] é o elemento pivô */

  2. i = p - 1

  3. for j = p to r - 1

  4.     if A[j] <= x

  5.         i = i + 1

  6.         exachange A[i] with A[j]

  7. exchange A[i + 1] with A[r]

  8. return i + 1

1. não modifica-se o PARTITION, pois sua modificação não garante uma boa divisão do vetor ao ser particionado;
2. modifica-se o PARTITION para que divida o vetor em 5 partições;
3. modifica-se o PARTITION criando uma rotina auxiliar que seleciona um elemento aleatório  como pivô e faz sua troca antes do particionamento real;
4. modifica-se o PARTITION para que receba como parâmetro de entrada o elemento pivô;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto