MO417 - Questão para a prova oral

Número:

Enunciado: Sabendo que dado um problema A e B podemos reduzir A a B se é possível converter a entrada de A para a entrada de B, resolver o problema B e converter a saída de B para o problema A. Isto é, podemos solucionar o problema A através de B. Então sobre a noção de redução e sobre as classes P e NP podemos afirmar que:

a) P ⊂ NP.
b) Um problema pertence à classe NP se seu problema de decisão é tratável.
c) Se B é um problema pertencente à classe P e podemos reduzir A a B então A também pertence à classe P.
d) Se B é um problema pertencente à classe NP e podemos reduzir A a B então A também pertence à classe NP.
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Dadas as matrizes predecessoras gerada pela execução do algoritmo Floyd-Warshall sobre um grafo orientado, indique qual o caminho mais curto com origem no vértice 3 e destino no vértice 1.

a) 3->2->1
b) 3->2->4->1
c) 3->4->2->1
d)3->1
e) NDA 

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Um grafo bipartido é um grafo cujos vértices podem ser divididos em dois conjuntos disjuntos U e V tais que toda aresta conecta um vértice em U a um vértice em V. Sua bipartição pode ser definida pela paridade das distâncias de todos os vértices em relação a um vértice s escolhido arbitrariamente: o conjunto U consiste dos vértices a uma distância par de s e o conjunto V consiste dos vértices a uma distância ímpar de s. Para calcular as distâncias dos vértices em relação a s pode-se aplicar a busca em largura.

Dado o grafo abaixo determine quais vértices pertencem a U e quais pertencem a V.

a) U={2,4,6} e V={1,3,5}

b) U={1,3,6} e V={2,4,5}

c) U={1,4,5,6} e V={2,3}

d) U={1,3,4,5} e V={2,6}

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere que um vértice s é descoberto na primeira vez em que é encontrado durante o procedimento de busca em largura ou em profundidade. Considere também que quando possível, vértices de numeração menor são descobertos primeiro, ou seja, numa dada interação onde 1 e 2 são vértices adjacentes a s, o vértice 1 é descoberto primeiro.

Dado o grafo abaixo, partindo do vértice 1, defina qual dos dois algoritmos descobre mais rápido os vértices 4, 7 e 8, respectivamente. Isto quer dizer que, o algoritmo X descobre o vértice s percorrendo menos vértices do que o algoritmo Y percorre.

a) busca em profundidade, profundidade e largura

b) busca em profundidade, largura e profundidade

c) busca em largura, profundidade e largura

d) busca em largura, largura e largura
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Em uma representação de conjuntos disjuntos através de grafos não orientado, suponha que é dado um grafo com n vértices.
Determine a quantidade mínima e máxima, respectivamente, de arestas que o grafo pode possuir para obtermos k conjuntos disjuntos.
Considere que não há mais de uma aresta entre dois vértices e que não há laços, ou seja, arestas com vértices idênticos nas extremidades.

a) n-k  e (n-k+1)(n-k)/2
b) n e (n-k)²
c) n-k e n(n-1)/2
d) n+k e n^k
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Sobre programação dinâmica e algoritmos gulosos eh incorreto afirmar que:
a) Ambos os problemas devem possuir subestrutura ótima
b) Ao contrário da programação dinâmica, algoritmos gulosos geram apenas um subproblema não vazio para cada escolha gulosa em um problema.
c) Ambos são utilizados para problemas de otimização.
d) Todo problema que pode ser resolvido com programação dinâmica também pode ser resolvido com algoritmos gulosos.
e) NDA

ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número: 

Enunciado: Existem algumas características ao problema que possibilitam o uso do método de programação dinâmica para sua solução. Marque a alternativa que contém uma dessas características.

a) o problema deve possuir um algoritmo de força bruta, ou seja, que analisa todas as possíveis soluções, que executa em tempo polinomial em relação à entrada.
b) o problema busca uma solução ótima e deve apresentar uma subestrutura ótima.
c) o problema deve ser impossível de resolver pelo método de divisão e conquista.
d) numa abordagem recursiva para o problema, em cada passo são gerados subproblemas absolutamente novos.
e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Assinale a alternativa verdadeira sobre o algoritmo SELECT e o algoritmo RANDOMIZED-SELECT.

a) No pior caso do RANDOMIZED-SELECT, todas as partições dividem o arranjo em 2 subarranjos, sendo um com 0 e outro com n-1 elementos. No SELECT, o método para a escolha do pivô não permite este caso.
b) No pior caso o SELECT possui tempo Θ(n) enquanto o randomized possui tempo Θ(nlgn).
c) No SELECT, se o i-ésimo termo for menor que o pivô X, então ele sera buscado no subconjunto com 5 elementos anterior ao subconjunto que contém X.
d) A recursão do SELECT particiona o problema em 5 subproblemas, enquanto que a recursão do RANDOMIZED-SELECT particiona em 2 subproblemas.
e) NDA.

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o algoritmo do quicksort ligeiramente modificado para sempre eleger o elemento aproximadamente do meio para ser o pivô. Isto é, PARTITION(A,p,r) elege o elemento A[⌈(r-p+1)/2⌉] como pivô. Desta forma, é correto afirmar que:

a) Quando e entrada A está em ordem decrescente o tempo de execução do quicksort é T(n)=Θ(nlgn), refletindo o pior caso.

b) Quando a entrada A está em ordem crescente o tempo de execução do quicksort é T(n)=Θ(n), refletindo o melhor caso.

c) Quando a entrada A está em ordem crescente ou decrescente, no fim de cada execução de PARTITION, o pivô sempre começa e termina na mesma posição.

d) Quando a entrada A está em ordem crescente ou decrescente o tempo de execução do quicksort é T(n)=Θ(nlgn), refletindo o melhor caso.

e) NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:

Enunciado: Considere o algoritmo abaixo para a resolução do problema Torre de Hanoi.

Algoritmo Hanoi (n, ori, des, aux)
 se n = 1
      então “move pino” de ori para des
 senão Hanoi (n − 1, ori, aux, des)
      “move pino” de ori para des
      Hanoi (n − 1, aux, des, ori)

Desta forma, considere a recorrência para este problema:

T(n)=1                 para n=1
T(n)=2T(n-1)+1   para n>1

É correto afirmar que:
a. T(n)=Θ(nlg(n))
b. T(n)=Θ(n²log(n))
c. T(n)=Θ(2ⁿ)
d. T(n)=Θ(n²)
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

MO417 - Questão para a prova oral

Número:


Enunciado:Sobre as seguintes afirmações, NÃO é correto afirmar que:

a. O(g(n)) ∩ Ω(g(n)) = Θ(g(n))
b. o(g(n)) ∩ Θ(g(n)) = ∅
c. o(g(n)) ∩ O(g(n)) = Θ(g(n))
d. o(g(n)) ⊂ O(g(n))
e. NDA

Ideia original de: Jacqueline Midlej do Espírito Santo

Teste

Teste