RE: Sobre o EP2

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Paulo Eduardo A. Silveira writes:
 > Professor, no Ep que voce colocou na pagina, ele nao esta calculando o
 > numero de minimo de rodadas para chegar ao fim, certo? 

Desculpe, nao entendi direito a pergunta.  O ex11 que está lá página é para
ordenação topológica; ele realmente não faz nada sobre esta tal decomposição
em rodadas etc.  

 > E tambem nao esta
 > falando em qual rodada deve ser executada qual tarefa, ele esta dando
 > apenas a ordem... a gente vai ter que fazer tudo, ne?

Sim, os exemplos dados1.txt e saida1.txt ilustram isto: 

dados1.txt: 

9
1 3
3 7
7 4
4 6
8 6
7 5
5 8
2 8
9 2
9 5

saida1.txt:

Uma decomposicao em rodadas da ordem parcial e como segue:
1: 1 9 
2: 3 2 
3: 7 
4: 5 4 
5: 8 
6: 6 
Vai aqui o caminho que encontrei (6 elementos):
1 3 7 5 8 6 

 > E quanto ao algoritimo usado, so' pode ser aquele?

Acho que é o mais facil e eficiente (=rapido e gasta pouca memoria).

 > E quanto a usar estrutura, eu nao posso usar uma matriz bem grande? Tipo,
 > n por n, onde n eh o numero de tarefas, ai casa a tarefa i sucede a tarefa
 > j eu marco um 1 na posicao i por j... caso contrario eu marco 0... da
 > certo, nao? Eu sei que a estrutura e' vantajosa por causa do ponteiro, mas
 > eu tambem posso definir o tamanho da matriz com malloc so' depois de
 > descoberto o tamanho (de acordo com o arquivo de entrada)...

Em geral, voce teria um monte de 0 na matriz, ocupando espaço
desnecessariamente.  Eu acho que voce teria que usar listas para manter o
conjunto de fontes e o conjunto de sucessores dos vertices para ter acesso
eficiente.  Sem estas estruturas de dados, o seu algoritmo seria
substancialmente menos eficiente (experimente dados7.txt, que é para 5000
elementos).

É claro, voce poderia implementar estas estruturas (conjunto de fontes e
sucessores) com vetores, mas dado que praticamente tudo ja está feito com
listas ligadas em ex11, acho que vale a pena entender como funciona aquela
implementação se inspirar nele para escrever o seu programa.  A implementacao
de filas etc com vetores nao é muito boa em geral.

Boa sorte!

Yoshi

 > Aguardo resposta
 > Paulo
 >  
 > 
 >  -------------------------------------
 >  Paulo Eduardo A. Silveira  
 >  Undergraduating in Computer Science
 >  University of Sao Paulo - IME
 >  http://www.linux.ime.usp.br/~peas
 >  -------------------------------------