Ep e página

[Alfredo Goldman <gold@ime.usp.br>]

Caros alunos,
      Primeiro gostaria de avisarq eu havia um erro nos links
da minha página, acho que foram todos corrigidos (o material de
árvores está disponível on-line). Tambem vou colocar no ar (em minutos)
o código da minha inserção em arvore 2-3.
      Para quem ainda tem dúvidas com relação ao Ep fiz vários testes.
Que podem ajudar:

Vejamos primeiro o exemplo do próprio EP:

3
001
 0  1  2  3  4  5  6  7
 8  0  9 10 11 12 13 14
15 16  0 17 18 19 20 21
22 23 24  0 25 26 27 28
29 30 31 32  0 33 34 35
36 37 38 39 40  0 41 42
43 44 45 46 47 48  0 49
50 51 52 53 54 55 56  0
111 011

Neste exemplo digo que vou trabalhar com um hipercubo com 2^3=8
vertices.

Na primeira parte peço a árvore de comunicação a partir do vértice
001. Para a segunda parte, é fornecida toda a matriz de comunicação, e
pergunta-se a soma das mensagens que passa pela a aresta 111->011 
(isto é deve se considerar também o sentido 011->111).

A solução do progama da Marina foi:

(001| (000| (010| (110)), (100)), (011| (111)), (101))

------------------------

Total de mensagens 111 - 011:
A[7][0] + A[7][1] + A[7][2] + A[7][3] + A[3][4] + A[3][5] + A[3][6] + A[3][7]   = 312



Mudando um pouco a entrada (apenas a aresta para calcular a soma). Os
seguintes dados fornecem o seguinte resultado:


(001| (000| (010| (110)), (100)), (011| (111)), (101))

------------------------

Total de mensagens 001 - 000:
A[1][0] + A[3][0] + A[7][0] + A[5][0] + A[0][1] + A[2][1] + A[6][1] + A[4][1]   = 207


Notem que mudando o sentido não muda o resultado final:

------------------------

Total de mensagens 000 - 001:
A[1][0] + A[3][0] + A[7][0] + A[5][0] + A[0][1] + A[2][1] + A[6][1] + A[4][1] +  = 207


Só para acabar, dois exemplos menores (fáceis de desenhar):
Extrada:
2
00
 0  1  2  3
 4  5  6  7
 8  0  9 10
 11 12 13 14
10 11

Saída:

(00| (01| (11)), (10))


------------------------

Total de mensagens 10 - 11:
A[3][2] + A[1][2] + A[2][3] + A[0][3] +  = 32

e

Entrada:
1
1
 0  1 
 2  3
1 0

Saída:
(1| (0))


------------------------

Total de mensagens 1 - 0:
A[1][0] + A[0][1] +  = 3

Por curiosidade, fiz a geração aleatória da matriz para ver até que
ponto o programa da Marina aguentaria:

com 2^10 vertices:
gold:~/Cursos/2002/mac2301/eps$ time  a.out teste4.txt


------------------------

Total de mensagens 0000000000 - 0000000001:
 = 524288


real    0m1.928s
user    0m1.340s
sys     0m0.550s
gold:~/Cursos/2002/mac2301/eps$



com 2^15 vertices fiz a minha sessao de X windows cair :)

Alfredo