Descrever algoritmo (s) recursivo (s) que computem a folga livre e a folga garantida de uma rede PERT.

Passo 1

Beleza, vamos lá! Você precisa descrever algoritmos recursivos que calculam a folga livre e a folga garantida em uma rede PERT. PERT é uma técnica usada para planejar e coordenar grandes projetos, e as folgas ajudam a entender quanto tempo uma tarefa pode atrasar sem afetar o projeto como um todo. Para resolver isso, vamos precisar entender os conceitos de tempos mais cedo e mais tarde para cada atividade na rede.

Passo 2

Primeiro, precisamos calcular os Tempos Mais Cedo ™ para cada atividade. O TM de uma atividade é o tempo mais cedo que ela pode começar sem atrasar o projeto. Vamos usar um algoritmo recursivo que, para cada atividade, verifica todas as atividades que a precedem e escolhe o maior TM entre elas, somando ao tempo de duração da atividade atual.

Passo 3

Agora, vamos calcular os Tempos Mais Tarde (TT), que é o tempo mais tarde que uma atividade pode começar sem atrasar o projeto. Para isso, começamos pela última atividade da rede e, de forma recursiva, para cada atividade, olhamos para as que a seguem e pegamos o menor TT delas, subtraindo o tempo de duração da atividade atual.

Passo 4

Com os TM e TT calculados, podemos determinar a Folga Garantida (FG) e a Folga Livre (FL):
  • Folga Garantida (FG): É a diferença entre o TT e o TM de uma atividade.
    FG = TT - TM
  • Folga Livre (FL): É a menor diferença entre o TM da próxima atividade e o TM da atividade atual mais sua duração.
    FL = min(TMpróxima) - (TMatual + Datual) ó

Passo 5

Vamos implementar esses cálculos com dois algoritmos recursivos:
  1. Algoritmo Recursivo para Tempos Mais Cedo ™:
def calcular_TM(atividade, rede, memo_TM):
    if atividade in memo_TM:
        return memo_TM[atividade]
    predecessoras = rede.get_predecessoras(atividade)
    if not predecessoras:
        memo_TM[atividade] = rede.duracao(atividade)
    else:
        tm_max = max(calcular_TM(p, rede, memo_TM) for p in predecessoras)
        memo_TM[atividade] = tm_max + rede.duracao(atividade)
    return memo_TM[atividade]
  1. Algoritmo Recursivo para Tempos Mais Tarde (TT):
def calcular_TT(atividade, rede, memo_TT, tm_total):
    if atividade in memo_TT:
        return memo_TT[atividade]
    sucessoras = rede.get_sucessoras(atividade)
    if not sucessoras:
        memo_TT[atividade] = tm_total
    else:
        tt_min = min(calcular_TT(s, rede, memo_TT, tm_total) for s in sucessoras)
        memo_TT[atividade] = tt_min - rede.duracao(atividade)
    return memo_TT[atividade]

Resposta

Com esses algoritmos, você consegue calcular os Tempos Mais Cedo e Mais Tarde para cada atividade na rede PERT de forma recursiva. Depois, aplicando as fórmulas de Folga Garantida e Folga Livre, você determina quanto cada atividade pode atrasar sem impactar o projeto. Isso ajuda no planejamento eficiente e na identificação de caminhos críticos.

Exercícios relacionados