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