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