PERGUNTA 1

Inúmeras personalidades contribuíram para a introdução do método científico na administração de empresas, que levaram ao desenvolvimento de algoritmos utilizados no planejamento de tarefas. As afirmações abaixo envolvem algumas dessas personalidades.

Frederick Taylor, nascido em 1856, é reconhecido por ter introduzido o método científico na administração de empresas.
Henry Gantt, nascido em 1861, é reconhecido por ter criado o diagrama que Gantt como uma ferramenta visual para o planejamento e o controle do trabalho.
Selmer Johnson, nascido em 1916, é reconhecido por ser o pioneiro em expressar uma solução algorítmica para o problema de agendamento de tarefas.
Selmer Johnson, nascido em 1916, é reconhecido por ser o pioneiro a provar que é possível obter soluções ótimas para um problema de agendamento de tarefas.
Escolha a alternativa que reúne as afirmativas verdadeiras.


Apenas I, II e III.


Apenas I e II.


Apenas III e IV.


Todas são verdadeiras.


Apenas I, III e IV.

1,25 pontos

PERGUNTA 2

Selmer Johnson propôs um algoritmo que corresponde à solução ótima para definir a ordem na qual um conjunto de objetos passa por duas máquinas (uma depois da outra), com tempos diferentes em cada máquina

Dadas máquinas M1 e M2 que operam em sequência M1 → M2

Dada uma lista de objetos e o tempo que utiliza de cada máquina

Selecionar o objeto que utiliza o menor tempo possível independentemente da máquina

Se o tempo for na M1: alocar esse objeto primeiro

Se o tempo for na M2: alocar esse objeto por último

… e repetir o processo



Considere o cenário daquele dia em que vamos lavar e secar toda a roupa da casa. Organizamos a roupa suja em vários conjuntos de peças de roupa (por cor, por tipo, por quantidade de sujeira etc.). Cada um desses conjuntos deve passar primeiro pela máquina de lavar e depois pela máquina de secar, e cada um consome um tempo diferente em cada máquina. O algoritmo de Selmer Johnson ajuda a definir a ordem em que vamos lavar os conjuntos de modo a terminar a tarefa toda o mais rápido possível.

Como exemplo, para os conjuntos de roupas abaixo, a ordem que define o menor tempo é CORES, CAMA, BANHO, BRANCAS.

BRANCAS: lavar 45 min, secar 25 min
CORES: lavar 20 min, secar 30 min
BANHO: lavar 40 min, secar 40 min
CAMA: lavar 35 min, secar 50 min
A ordem que terminar a tarefa em menor tempo é: CORES, CAMA, BANHO, BRANCAS.

Sejam as seguintes afirmações:

O conjunto CORES é o primeiro da sequência porque ele tem o menor tempo na máquina de lavar.
O conjunto BRANCAS é o último da sequência porque ele tem o menor tempo na máquina de secar.
O conjunto BRANCAS é o último da sequência porque ele tem o maior tempo na máquina de lavar.
O conjunto CAMA é o segundo da sequência porque ele tem o maior tempo na máquina de secar.
O conjunto BANHO é o terceiro da sequência porque ele o mesmo tempo nas duas máquinas.
Selecione a alternativa que lista as afirmações verdadeiras.


I, II e III são verdadeiras.


I, II, III e IV são verdadeiras.


I, II e V são verdadeiras.


I e II são verdadeiras.


Todas são verdadeiras.

1,25 pontos

PERGUNTA 3

Sempre que temos um conjunto de tarefas para fazer, sabemos que demoramos um certo tempo para realizar cada tarefa. Sempre que pretendemos realizar todas elas, a ordem em que vamos realizá-las não interfere no tempo total que dedicaremos: o tempo total é a soma do tempo de todas as tarefas.

Mas, e se cada tarefa tiver uma data-limite para ser entregue? Nesse caso, podemos considerar uma estratégia que minimize o tempo total de eventuais atrasos que tenhamos relativamente às datas-limite de cada tarefa. Essa estratégia é definida pelo algoritmo de Data devida mais próxima.

Algoritmo Data devida mais próxima

Dada a lista de tarefas e as datas-limite de cada tarefa:

Ordenar a lista de tarefas em ordem crescente relativamente às datas-limite de cada tarefa.
Realizar as tarefas de acordo com a ordem definida.


Seja o conjunto de tarefas e número de dias que faltam para elas sejam concluídas:

TM: faltam 13 dias.
TK: faltam 21 dias.
TX: faltam 18 dias.
TR: faltam 15 dias.
A ordem sugerida pelo algoritmo de Data devida mais próxima é:


TM, TR, TK, TX


TM. TK, TX, TR


TK, TX, TR, TM


TR, TX, TM, TK


TM, TR, TX, TK

1,25 pontos

PERGUNTA 4

O algoritmo de Dijkstra calcula a menor distância entre dois nós em um grafo cujas arestas possuem pesos. O grafo ilustrado na figura representa um conjunto de cidades e o custo das conexões entre elas.



Considerando a aplicação do algoritmo de Dijkstra no grafo, quais das afirmações são verdadeiras?

A distância computada pelo algoritmo entre os nós 0 e 1 é igual a 3.
A distância computada pelo algoritmo entre os nós 0 e 2 é igual a 5.
A distância computada pelo algoritmo entre os nós 0 e 3 é igual a 4.
A distância computada pelo algoritmo entre os nós 0 e 4 é igual a 5.

Todas são verdadeiras.


Apenas IV é verdadeira.


III e VI são verdadeiras.


Apenas I é verdadeira.


II e V são verdadeiras.