MO417 - Complexidade de Algoritmos I Prova Individual - 27/06/2003

Questão 1 (Valor 2,5)

Considere os algoritmos de Prim e Kruskal para a construção de árvores espalhadas mínimas. Supondo que cada um deles seja implementado com as estruturas de dados que resultem em menor complexidade assintótica dentre as vistas no curso, compare as complexidades resultantes. Justifique sua resposta indicando quais estruturas são estas, quais são as complexidades resultantes, e em que situações cada algoritmo seria superior.

Questão 2 (Valor 2,5)

O algoritmo de Floyd-Warshall para calcular caminhos mais curtos entre todos os pares em grafos genéricos utiliza tempo O(V^{3}) e espaço O(V^{2}), independentemente de E. Considere agora o problema restrito a grafos orientados acíclicos. Seria possível resolvê-lo utilizando menos tempo e/ou espaço no caso em que E = o(V^{2})? Justifique descrevendo um algoritmo mais eficiente em termos assintóticos, acompanhado de sua complexidade temporal e espacial, ou argumente porque não seria possível.

Questão 3 (Valor 2,5)

Para a determinação de um fluxo máximo numa rede de fluxo, os algoritmos: (1) básico de Ford-Fulkerson, e (2) de Edmonds-Karp têm complexidade de tempo O(E|f^{∗}|) e O(V E^{2}), respectivamente. No caso de serem aplicados para determinar um emparelhamento máximo num grafo bipartido, conforme visto no curso, qual dos dois é mais eficiente? Justifique sua resposta.

Questão 4 (Valor 2,5)

Para cada uma das afirmações abaixo, diga se é verdadeira ou falsa, justificando.

1. Problemas NP-completos têm enunciados bem diferentes de problemas que têm algoritmos de tempo polinomial.

2. Caminhos simples mais longos, ciclo hamiltoniano e satisfatibilidade 2-CNF são exemplos de problemas NP-completos.

3. Problemas NP-completos são problemas para os quais ainda não se conhece nenhum algoritmo de tempo polinomial para sua solução. Porém são “verificáveis” em tempo polinomial.

4. O caráter NP-completo se aplica diretamente a problemas de decisão, ou seja, problemas cuja resposta é sempre “sim” ou “não”. Contudo, para a grande maioria dos problemas de otimização, existe um problema de decisão com complexidade equivalente ao de otimização, a menos de um fator multiplicativo polinomial.

A questão 4 foi baseada em uma questão oral submetida por Fábio Batista Gomes.