Um típico problema em que algoritmos gulosos são aplicados é conhecido como agendamento para minimizar o tempo médio de finalização. Várias estraté...

Um típico problema em que algoritmos gulosos são aplicados é conhecido como agendamento para minimizar o tempo médio de finalização. Várias estratégias têm sido propostas para oferecer uma solução em tempo computacionalmente viável. Suponha um conjunto S = { a , b , c , d } de tarefas, cada uma com um tempo de processamento p i e um tempo de vencimento d i . O tempo de vencimento é o prazo final para a conclusão da tarefa. O objetivo é minimizar o tempo médio de finalização das tarefas. Considere as seguintes afirmacoes: I. O algoritmo guloso que seleciona as tarefas em ordem crescente de tempo de processamento é ótimo. II. O algoritmo guloso que seleciona as tarefas em ordem crescente de tempo de vencimento é ótimo. III. O problema de agendamento para minimizar o tempo médio de finalização é um problema NP-completo. IV. O problema de agendamento para minimizar o tempo médio de finalização é um problema NP-difícil. Assinale a alternativa que apresenta a sequência correta.

I. O algoritmo guloso que seleciona as tarefas em ordem crescente de tempo de processamento é ótimo.
II. O algoritmo guloso que seleciona as tarefas em ordem crescente de tempo de vencimento é ótimo.
III. O problema de agendamento para minimizar o tempo médio de finalização é um problema NP-completo.
IV. O problema de agendamento para minimizar o tempo médio de finalização é um problema NP-difícil.
F, V, V, F.
V, F, V, F.
F, V, F, V.
V, F, F, V.