1. 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 estr...

1. 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 = ｛ a1, a2, …, an ｝ de tarefas, em que cada tarefa ai demanda pi unidades de tempo para ser concluída a partir do momento em que é iniciada. As tarefas podem ser executadas apenas uma por vez. Seja ci o tempo para finalização da tarefa ai, isto é, o tempo em que a tarefa ai completa seu processamento. Considerando que o objetivo é minimizar o tempo médio para finalização de todas as tarefas, ou seja, minimizar: Analise as afirmativas a seguir e marque V (verdadeira) ou F (falsa): I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem finalizadas (pi), então a complexidade do algoritmo será O(n log n). II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de pi obtém a solução ótima para qualquer conjunto de tarefas. III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 = 5, o tempo médio de finalização de S é independente da ordem de execução das tarefas. IV. ( ) Uma solução gulosa baseada no tempo de processamento de cada tarefa apresenta uma estrutura local ótima em cada iteração. Agora, assinale a alternativa que apresenta a sequência correta.

I. ( ) Se as tarefas forem ordenadas pela quantidade de unidades de tempo para serem finalizadas (pi), então a complexidade do algoritmo será O(n log n).
II. ( ) Um algoritmo guloso que processa as tarefas em ordem crescente de pi obtém a solução ótima para qualquer conjunto de tarefas.
III. ( ) Considerando S composto apenas de duas tarefas a1 e a2 com p1 = 3 e p2 = 5, o tempo médio de finalização de S é independente da ordem de execução das tarefas.
IV. ( ) Uma solução gulosa baseada no tempo de processamento de cada tarefa apresenta uma estrutura local ótima em cada iteração.
F, F, V, V.
V, V, F, V.
V, F, V, F.
F, V, F, V.