Número:
Enunciado: Dado um conjunto de tarefas G, suas respectivas durações W e a lista de depêndencias E, pretende-se executar todas as tarefas no menor tempo possível levando em consideração as dependências entre elas. Sabendo que este problema pode ser representado através de um grafo ponderado, direcionado e acíclico G=(V,E) onde as atividades são os vértices, as dependências as arestas e as durações são pesos associados as arestas, analise as afirmações abaixo e assinale a alternativa correta:
I - O problema pode ser visto como um problema de otimização linear cujo objetivo é encontrar o caminho mais longo a partir do vértice fonte.
II - Não existe um algoritmo conhecido capaz de resolver este problema em tempo polinomial.
III - Multiplicando os pesos por -1 seria possível solucioná-lo através do algoritmo de Dijsktra.
IV - A melhor estratégia seria reduzir o problema para a Mochila0-1 para então resolvê-lo utilizando programação dinâmica em tempo pseudo-polinomial.
Alternativas:
a) Somente I está correta
b) I e III estão corretas
c) I, III e IV estão corretas
d) II e IV estão corretas
e) NDA
Idéia original de: Osvaldo Andrade Neto
Enunciado: Dado um conjunto de tarefas G, suas respectivas durações W e a lista de depêndencias E, pretende-se executar todas as tarefas no menor tempo possível levando em consideração as dependências entre elas. Sabendo que este problema pode ser representado através de um grafo ponderado, direcionado e acíclico G=(V,E) onde as atividades são os vértices, as dependências as arestas e as durações são pesos associados as arestas, analise as afirmações abaixo e assinale a alternativa correta:
I - O problema pode ser visto como um problema de otimização linear cujo objetivo é encontrar o caminho mais longo a partir do vértice fonte.
II - Não existe um algoritmo conhecido capaz de resolver este problema em tempo polinomial.
III - Multiplicando os pesos por -1 seria possível solucioná-lo através do algoritmo de Dijsktra.
IV - A melhor estratégia seria reduzir o problema para a Mochila0-1 para então resolvê-lo utilizando programação dinâmica em tempo pseudo-polinomial.
Alternativas:
a) Somente I está correta
b) I e III estão corretas
c) I, III e IV estão corretas
d) II e IV estão corretas
e) NDA
Idéia original de: Osvaldo Andrade Neto
Nenhum comentário:
Postar um comentário