MO417 - Questão para a prova oral

Número:

Enunciado: Considere os seguintes circuitos:

I.   (x1 OR x2) OR (NOT (x1 OR x2))
II.  NOT((NOT x1) OR (NOT x2))
III. NOT((NOT x1) AND (NOT x2))

Podemos usar alguns deles para reduzir o problema SAT a um problema de satisfabilidade com apenas duas portas lógicas válidas (NOT e AND/OR).

Quais deles podemos usar para provar este problema é NP-completo, e como? Suponha que já temos como validar este problema em O(n^k).

a. circuito I, substituindo a porta AND por ele
b. circuito I, substituindo a porta OR por ele
c. circuito I e II, substituindo a porta AND por I ou a porta OR por III.
d. circuito II e III, substituindo a porta AND por II ou a porta OR por III.
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: As afirmações abaixo descrevem a importância dos conceitos em fluxo maximal (maximum flow). Qual delas está incorreta?

a. Redes residuais (residual networks) são a estrutura usada para encontrar caminhos incrementantes (augmenting paths).
b. Caminhos incrementantes (augmenting paths) descrevem como aumentar o fluxo atual no grafo e a sua ausência indica que encontramos o fluxo maximal.
c. Cortes (cuts) descrevem o movito pelo qual a ausência de caminhos incrementantes implicam que encontramos o fluxo maximal.
d. Arestas antiparalelas (antiparallel edges), superfonte (supersource) e supersorvedouro (supersink) são formas de adaptar um grafo direcionado para que seja possível obter uma rede residual (residual network) a partir dele.
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre o algoritmo de Dijkstra, quais das alternativas abaixo está correta?

a. O algoritmo relaxa cada aresta duas vezes
b. Dijkstra encontra os caminhos mais curtos mesmo com arestas de peso negativo, desde que não possuam ciclos negativos
c. O algoritmo funciona apenas se não houver ciclos, ou seja, se for um DAG (Directed Acyclic Graph)
d. O algoritmo se enquadra como um algoritmo guloso
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: O algoritmo da busca em profundidade (depth-first search) pode classificar uma aresta (u, v) a partir da cor do vértice v. Quais dos critérios abaixo estão corretos?

I - BRANCO indica uma aresta de árvore (tree edge)
II - CINZA indica uma aresta de cruzamento (cross edge)
III - PRETO indica uma aresta de cruzamento (cross edge) ou uma aresta de avanço (forward edge) em grafos direcionados e não ocorre em grafos não-direcionados

a. apenas I
b. apenas II
c. I e II
d. I e III
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o código de Huffman, transcrito abaixo a partir do livro:

  HUFFMAN(C)
  1  n = |C|
  2  Q = C
  3  for i = 1 to n-1
  4       allocate a new node z
  5       z.left = x = EXTRACT-MIN(Q)
  6       z.right = y = EXTRACT-MIN(Q)
  7       z.freq = x.freq + y.freq
  8       INSERT(Q,z)
  9  return EXTRACT-MIN(Q)    //return the root of the tree

Qual das seguintes afirmações é correta?

a. a escolha gulosa consiste em alocar os elementos de menor frequência no topo da árvore
b. pode executar em tempo O(n) se Q tiver os elementos ordenados em ordem crescente
c. executa em tempo O(n lg lg n) utilizando um heap para armazenar os valores de Q
d. o código avalia subproblemas anteriores para fazer as suas escolhas
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre programação dinâmica e divisão-e-conquista, escolha a alternativa correta:

a. ambos são algoritmos aplicáveis à problemas de otimização
b. ambos requerem subproblemas que se sobrepõem para reduzir a complexidade de tempo
c. ambos requerem a presença de subproblemas a serem combinados
d. ambos utilizam uma abordagem de cima para baixo como estrutura inerente de computação
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre a seleção de um elemento em uma sequência, escolha a alternativa incorreta:
a. A seleção de um elemento, quando aleatorizado, ocorre em tempo esperado O(n).
b. A seleção randomizada possui tempo O(n²) no pior caso.
c. O problema da seleção tem tempo teórico O(n) no pior caso.
d. O processo de escolha do pivô, sendo baseado no do quicksort randômico, também ocorre em tempo O(n).
e. NDA

Ideia original de: Jorge Augusto Hongo