Segundo Exercício-Programa

MAC122 - Princípios de Desenvolvimento de Algoritmos

BCC - 2o. Semestre de 1998

Este segundo exercício-programa é um exercício simples de manipulação de listas. Se você entendeu bem o algoritmo de ordenação topológica (por exemplo, implementado em [ex11.dvi | ex11.ps | ex11.pdf | ex11.w | ex11_modif.c], você não deve ter dificuldades.

Número de rodadas em um escalonamento paralelo

Suponha que você tem n tarefas para executar e tem a sua disposição, para isto, muitas máquinas (digamos, n máquinas; cada máquina pode executar uma destas tarefas por vez). As tarefas, entretanto, devem ser executadas respeitando-se uma certa ordem de prioridade, como discutido quando vimos ordenação topológica (a tarefa j depende da tarefa i e portanto podemos executá-la apenas após ter executado i, etc). Suponha que as tarefas são executadas sincronamente, e que cada tarefa demora exatamente uma unidade de tempo. Desta forma, as tarefas são executadas em rodadas. O objetivo deste EP é escrever um programa que

decide qual é o número mínimo necessário de rodadas, digamos r, para se executar um dado conjunto de tarefas,
decide quais devem ser as tarefas a serem executadas em cada uma das r rodadas,
descreve uma seqüência de r tarefas que devem ser executadas seqüencialmente e que desta forma provam que não é possível executar as tarefas dadas em menos do que r rodadas.

Voce deve assumir que a entrada tem o mesmo formato que a entrada dos programas de ordenação topológica que vimos em aula.

Alguns exemplos de entrada e saída

O exemplo da sala de aula: dados1.txt, saida1.txt.
dados2.txt, saida2.txt
dados3.txt, saida3.txt
dados4.txt, saida4.txt
dados5.txt (14k), saida5.txt
dados6.txt, saida6.txt
dados7.txt (956k), saida7.txt (25k)
dados8.txt, saida8.txt
dados9.txt, saida9.txt
dados10.txt (1462k), saida10.txt (379k)

Os dados de entrada de (2) a (7) foram gerados ao acaso. Os dados dos exemplos (8), (9) e (10) representam circuitos booleanos com portas binárias AND, OR, XOR que multiplicam números em base 2. O exemplo (8) corresponde a um circuito para multiplicar 2 números com no máximo 2 bits cada. Os exemplos (9) e (10) correspondem a circuitos que multiplicam 2 números com no máximo 5 e 100 bits cada, respectivamente.

É bastante interessante que para multiplicar 2 números com 100 bits cada (exemplo (10)), é possível projetarmos um circuito cujo número de portas é da ordem de 65.000 e o número de rodadas (ou "ciclos de relógio") é de apenas 43! O algoritmo natural de multiplicação usa pelo menos 100 rodadas.

Prazo de entrega: segunda-feira, 28 de setembro de 1998, até as 18:00. Note que você não tem muito tempo! Entregue seu EP na secretaria do MAC, sala 256, bloco A, antes do término do expediente naquele dia!

Prazo estendido. O prazo de entrega se encerrará dia 5/10/98!

Observações

O EP é estritamente individual. Exercícios semelhantes receberão nota 0.
Exercícios atrasados não serão aceitos.
Exercícios com erros de sintaxe receberão nota 0.
Endente o seu programa sistematicamente. Uma má apresentação do código resultará em nota menor.
Coloque comentários apropriados em seu programa. Programas sem documentação receberão nota baixa.
Coloque o cabeçalho usual em seu programa (como em MAC110), com nome, número USP, curso, data, nome do professor e identificação do EP (EP2). Não esqueça de indicar que compilador que você usou (Turbo C, Quick C, gcc, etc).
Entregue em um envelope (preferencialmente de plástico transparente):
- Um disquete com o código do seu programa. Identifique o disquete com uma etiqueta.
- Uma listagem do programa.
- As saídas correspondentes aos exemplos no enunciado (ainda a serem postos nesta página) e quaisquer outras saídas que você achar importantes (com as respectivas entradas, em forma eletrônica). A abrangência dos seus testes também será considerada na nota. Saber testar bem um programa é também muito importante.
- Guarde uma cópia de seu material até o fim do semestre.
Importante: entregue o seu material também por correio eletrônico para o nosso monitor Ricardo Bueno Cordeiro <rbc@ime.usp.br>, com cópias para <yoshi@ime.usp.br> e <jair@ime.usp.br>. O ideal é que futuramente a entrega de disquetes não fosse mais necessária.

Página principal de MAC122 (BCC - 2o. semestre de 1998).

Y. Kohayakawa <yoshi@ime.usp.br>

Last modified: Thu Sep 24 12:02:18 EST 1998