MC202 EF - Atividade de Laboratório no. 1

Descrição do Problema
Entradas
Exemplo de Entrada
Exemplo de Saída
O algoritmo
Data Limite para Entrega

Descrição do Problema - Ordenação Parcial

Em muitas situações é necessário encadear atividades considerando a precedência entre elas. Por exemplo, a construção de uma casa pode ser descrita por uma série de atividades como
  • elaboração da planta
  • estaqueamento
  • fundação e alicerces
  • levantamento das paredes
  • madeiramento 
  • telhado
  • instalações elétricas e hidráulicas
  • revestimentos
  • pintura
  • entrega das chaves
Muitas vezes o número de atividades é muito grante e as relações de precedência entre elas não permite identificar diretamente a seqüência de execução factível para a conclusão do projeto. A relação de precedência pode ser indefinida para alguns pares de atividades e por essa razão, esse tipo de problema é chamado na literatura de 'Ordenação Parcial' (ou 'ordenação topológica' [em ingles, 'topological sorting'] ).

Esta atividade de laboratório consiste em construir um, dado uma relação de atividades e as relações de precedência entre elas, determinar
  • uma seqüência possível para execução das atividades, executando uma por vez
  • uma seqüência possível para execução das atividades, executando,  as atividades em paralelo de forma a reduzir o tempo de execução ao mínimo.

Entradas

A relação das atividades será através de um arquivo de entrada, 'atividades.txt', contento o seguinte:
  • número de atividades (1 linha)
  • para cada atividade uma linha contendo: [1] número sequencial (1, 2, ...), [2] um código (2 caracteres, exemplo: 'CH', 'MO', 'GI') e [3] a descrição da atividade, limitado a 50 caracteres.
  • relação de precedência entre as atividades, sob a forma de pares como por exemplo '1 2' indicando 'atividade  precede a atividade 2'.  Cada par é colocado numa linha e a última linha contém o par '0 0' indicando 'fim de entrada'. 

    • Exemplo de Entrada 

    	12
    	1 CH montagem do chassi
    	2 CA montagem da carroceria
    	3 CM colocacao do motor
    	4 CR colocacao das rodas
    	5 MM montagem do motor
    	6 MG montagem do girabrequim
    	7 MB montagem das bielas
    	8 MV montagem do comando de valvulas
    	9 MP montagem dos pneus
    	10 CP colocacao das portas
    	11 VG verificacao geral
    	12 CV colocacao dos vidros
    	2 12
    	10 12
    	12 11
    	2 10
    	6 5
    	7 5
    	8 5
    	5 3
    	9 4
    	9 2
    	1 10
    	1 3
    	1 4
    	0 0

    Exemplo de Saída 

                  Lista 1 (atividade por vez)
    	6 MG montagem do girabrequim
    	7 MB montagem das bielas
    	8 MV montagem do comando de valvulas
    	9 MP montagem dos pneus
    	1 CH montagem do chassi
    	5 MM montagem do motor

    	3 CM colocação do motor
    	2 CA montagem da carroceria
    	4 CR colocacao das rodas
    	10 CP colocacao das portas
    	12 CV colocacao dos vidros
    	11 VG verificacao geral
                  Lista 2 (atividades em paralelo - no menor tempo possível)
                  (1,6,7,8,9)
                  (5,4,2)
                  (3,10)
                  (12)
                  (11)

    O algoritmo

    1 - Sugestão para a representação dos dados

    Represente cada atividade por uma estrutura contendo:
  • código
  • número de atividades predecessoras ainda não executadas 
  • lista das atividades para as quais esta é predecessora (lista de 'sucessoras')
  • apontador (a ser usado na construção de uma fila de atividades).

    • Cada nó dessa lista de 'sucessoras' pode ser representado por uma estrutura contendo
  • apontador para a estrutura que descreve a a atividade sucessora.
  • apontador para o próximo elemento da lista.

    • Mantenha as as estruturas que descrevem as atividades  num vetor (alocado dinamicamente).

    2 - Sugestão para a estrutura geral do algoritmo (p/ uma atividade por vez

    0. Criar uma fila F, inicialmente vazia.

    1. Percorrer o vetor de atividades, colocando numa fila F aquelas que já podem ser executadas (não dependem de nenhuma outra atividade).

    2. Enquanto a fila tiver alguma atividade  a ser executada 

    2.1 - retire a primeira atividade A  da fila F e a coloque na saída.

    2.2 - para cada atividade  S, 'sucessora' de A, decremente o contador de predecessoras. Se esse contador chegou a zero, coloque S na fila F (ela já pode ser executada).

    3. Quando a fila F estiver vazia, se o número de atividades escritas na saída for menor que o número de atividades da lista, ocorreu um erro: existe pelo menos um ciclo nas relações de dependência.

    Data Limite para Entrega

    O projeto deverá ser entregue por email ao assistente de ensino  até o dia 30/08/00