MO417 - Questão para a prova oral

Número:

Enunciado: Vários departamentos policiais de uma cidade precisam se comunicar sobre ocorrências e para isso foi estabelecida uma rede interligando-os. A comunicação deve ser feita de forma a atender o requisito de que uma mesma ocorrência passe por todos os departamentos uma única vez, partindo sempre do departamento A. A rede estabelecida e representada pelo grafo abaixo ainda não cumpre esse requisito de comunicação. 

Identifique primeiro uma nova conexão que deve ser criada para atender o requisito de comunicação. Em seguida, identifique outra conexão de forma que não só esse requisito seja atendido, como a informação retorne ao departamento de origem A para que este saiba que todos os departamentos receberam com sucesso a informação da ocorrência. 

Qual alternativa contém respectivamente a primeira e a segunda conexão válida para atender o exigido acima?

A) (C,E) e (G,H)

B) (D,G) e (D,F)

C) (D,F) e (E,H)

D) (E,F) e (D,H)

E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Dado uma rede de fluxo abaixo com fonte S e sorvedouro T, após executar o algoritmo de Ford-Fulkerson, qual o corte mínimo correspondente ao fluxo máximo de 12?

A) ({s, a}, {b, c, d, t})
B) ({s, c}, {a, b, d, t})
C) ({s, a, b}, {c, d, t})
D) ({s, c, d}, {a, b, t})
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o grafo direcional ponderado G abaixo, onde a fonte é o vértice t.

Considere as seguintes afirmações abaixo e assinale a alternativa correta:

I) Ao aplicarmos o algoritmo de Bellman-Ford em G, relaxando as arestas na ordem (u,v), (u,x), (u,z), (v,u), (v,z), (v,x), (x,z), (t,u), (t,x), o algoritmo com o código abaixo retorna TRUE.
BELLMAN-FORD(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
para i=1 ate |V[G]| -1
   para cada aresta (u,v) pertencente a E[G]
       RELAX(u,v,w)
   para cada aresta (u,v) pertencente a E[G]
      se (v.d > u.d + w(u,v))
           return FALSE
return TRUE

II) Se eliminássemos a aresta de peso negativo (v,u) do grafo G, poderíamos aplicar o algoritmo de Dijkstra no grafo alterado, G', cujo código segue abaixo.
DIJKSTRA(G,w,s)
INITIALIZE-SINGLE-SOURCE(G,s)
S = vazio
Q = V[G]
while Q != vazio
    u = EXTRACT-MIN(Q)
    S = S U {u}
    para cada vértice v pertencente a G.Adj[u]
         RELAX(u,v,w)
Dado que o laço while itera |V| vezes, após a quarta iteração do laço teríamos a seguinte situação (obs: vertice.d representa o peso de um caminho mínimo da fonte até o vértice v):
S = {t,u,x,v}; t.pai = NILL; t.d = 0; u.pai = t; u.d = 7; v.pai = u; v.d = 15; x.pai = u; x.d = 9; z.pai = u; z.d = 18.

III) Se retirássemos a aresta (v,u) do grafo G, obtendo o grafo G', seria possível fazer uma ordenação topológica dos vértices do grafo G' e encontrar caminhos mínimos de fonte única, obtendo a situação final (obs: vertice.d representa o peso de um caminho mínimo da fonte até o vértice v):
t.pai = NILL; t.d = 0; u.pai = t; u.d = 7; v.pai = u; v.d = 15; x.pai = u; x.d = 9; z.pai = v; z.d = 17.

A) Apenas III é correta
B) Apenas II é correta
C) II e III são corretas
D) I e II são corretas
E) N.D.A


Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere um grafo não orientado G com vértices pertencentes ao conjunto {40, 98, 7, 105, 20, 13, 10, 3, 49, 402} e arestas entre x e y quando x mod y = 0. Considere também a operação CONNECTED-COMPONENTS com o seguinte código abaixo:

CONNECTED-COMPONENTS(G)
para cada vertice v pertencente a V[G]
     MAKE-SET(v)
para cada aresta (u,v) pertencente a E[G]
     if (FIND-SET(u) != FIND-SET(v))
            UNION(u,v)

Com relação às quatro afirmações abaixo, assinale a alternativa correta:
I. O grafo G possui um total de 6 arestas.
II. Durante a execução de CONNECTED-COMPONENTS sobre G, FIND-SET e UNION são chamados respectivamente16 e 6 vezes.
III. O grafo G possui 3 componentes conexas.
IV. Um componente conexo do grafo G é {40, 20, 10}.

A) As afirmações II e IV são corretas
B) As afirmações I, II e IV são corretas
C) As afirmações I e III são corretas
D) Apenas a afirmação I é correta
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Em uma implementação de cache têm-se um espaço fixo que permite armazenar pares compostos por (valor, numero_de_acessos).  Existem algumas restrições quanto à implementação dessa cache:

1. deve sempre conter os elementos mais acessados
2. o tempo para encontrar um elemento qualquer e o tempo para encontrar outro elemento qualquer devem ser os mais próximos possíveis
3. o tempo para encontrar um elemento e o tempo para descobrir se um elemento não se encontra na cache devem ser os mais próximos possíveis
4. periodicamente os elementos menos acessados devem ser descartados, sendo que a eficiência para encontrar esses elementos nao é prioritária em relação aos outros requisitos

Qual é a melhor estrutura de dados a ser utilizada para representar essa cache?

A) Vetor ordenado crescentemente em função do número de acessos.
B) Árvore binária balanceada ordenada pelo número de acessos.
C) Árvore binária balanceada ordenada pelo valor.
D)Vetor ordenado decrescentemente em função do número de acessos.
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Com relação aos algoritmos de divisão e conquista e programação dinâmica, indique a alternativa INCORRETA: 

A) Os algoritmos de divisão e conquista resolvem repetidamente os subproblemas comuns. 
B) Programação dinâmica é aplicada para encontrar uma solução com valor ótimo, que é computado a partir de combinações de soluções ótimas previamente calculadas e memorizadas.
C) Os algoritmos de divisão e conquista são mais indicados em problemas que existem sobreposições de subproblemas.
D) A característica de memorização de soluções previamente calculadas da programação dinâmica é útil quando o número de subproblemas repetidos cresce exponencialmente de acordo com o tamanho da entrada.
E) N.D.A

Ideia original de: Thaís Harumi Ussami

MO417 - Questão para a prova oral

Número:

Enunciado: Considere as seguintes informações sobre o algoritmo de seleção RANDOMIZED-SELECT, cujo código segue abaixo:

RANDOMIZED-SELECT(A,p,r,i)
if (p == r)
   return A[p]
q = RANDOMIZED-PARTITION(A,p,r)
k = q-p-1
if (i == k)
   return A[q]
else if (i < k)
   return RANDOMIZED-SELECT(A,p,q-1,i)
else return RANDOMIZED-SELECT(A,q+1,r,i-k)

I. O algoritmo executa em tempo linear, uma vez que adota premissas sobre a entrada.
II. O algoritmo realiza primeiro uma ordenação dos elementos para então selecionar o i-ésimo menor elemento do arranjo A[p...r].
III. Para determinar qualquer estatística de ordem, considerando elementos distintos do arranjo, o tempo esperado é linear.
IV. O algoritmo utiliza a técnica de divisão e conquista para retornar o i-ésimo menor elemento do arranjo A[p...r].

Assinale a alternativa correta:

A) I e II estão correta.
B) I, III e IV estão corretas.
C) I e III estão corretas.
D) III e IV estão corretas.
E) N.D.A

Ideia original de: Thaís Harumi Ussami