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