Trabalho de Construção e Análise de Algoritmos

Trabalho de Construção e Análise de Algoritmos

Nícolas F. Iensen
Faculdade de Informática – PUCRS
Caixa Postal 1429
90619-900 – Porto Alegre – Brasil

16 de outubro de 2006

Resumo

Este artigo descreve a solução para o segundo problema proposto na disciplina de Construção e Análise de Algoritmos em 2006/II, problema que se resume na organização de atividades de um projeto. A solução desse problema deve calcular o número mínimo de semanas para que o projeto seja finalizado. Este artigo apresenta a solução para o problema e alguns casos de teste.

Introdução

O segundo problema da disciplina de Construção e Análise de Algoritmos de 2006/II pode ser descrito da seguinte forma: cada uma das atividades do projeto possui os seguintes atributos: número de indentificação, duração em semanas, número de atividades que dependem dela e uma lista dessas atividades. A solução deve encontrar uma maneira de executar essas atividades de forma que o projeto seja terminado no menor tempo possível. Como regra para a solução uma atividade só pode ser iniciada após as suas predecessoras terem sido completas, e nada impede que duas ou mais atividades sejam executadas ao mesmo tempo. Como entrada para a solução temos:

O número n de atividades do projeto (há um máximo de 200 atividades);
O número id de indentificação de cada atividade;
A duração d de cada atividade;
O número k de dependencias de cada atividade;
A lista dpn das atividades dependentes.

A partir dessa entrada descrita acima a solução deve calcular o menor tempo em semanas para o projeto ser finalizado.

Por exemplo, considerando a entrada abaixo:

5
1 3 2 2 4
2 5 3 3 4 5
3 6 1 4
4 2 0
5 9 0

Onde a primeira linha corresponde ao número de atividades do projeto. Cada uma das outras linhas correspondem a uma atividade. A primeira coluna são os números de indentificação, a segunda as durações de cada atividade, a terceira o número de dependências e a partir da quarta coluna