Algoritmo de Hipercubo[RESOLVIDO]

Programação Java
#1

Boa tarde pessoal

É o seguinte, estou precisando criar um algoritmo de hipercubo para um trabalho da faculdade, mas o problema é que não encontro em lugar algum sobre como funciona.

Na verdade, eu entendi mais ou menos…
Pelo que entendi, quando for de natureza,por exemplo 2, terei 4 processos…
Mas não entendi como defino a comunicação entre eles: Quem envia para quem…

Alguém saberia me explicar o funcionamento?

obrigada

#2

Esta apostila pode te dar uma esclaracida nas ideias !!!

http://vigo.ime.unicamp.br/n-sphere.pdf

:smiley:

#3

fiquei interessado nesse assunto…

mais a apostila ta bem difícil de entender, isso ai ta relacionado a desenvolvimento 3d ou algo do tipo?

#4

userguj,

Em primeiro lugar, obrigada por responder…
Mas sinceramente, complicou ainda mais o meu entendimento.

Teria alguma outra forma, não tão difícil?

Porque assim… O que não entendo é: Como definir quem se comunicará com quem?

Obrigada

#5

Um hipercubo de natureza 2 tem 2 ^ 2 = 4 processos (vértices de um quadrado)
Cada vértice se liga aos seus 2 vizinhos.
Um hipercubo de natureza 3 tem 2 ^ 3 = 8 processos (vértices de um cubo)
Cada vértice se liga aos seus 3 vizinhos.
Um hipercubo de natureza 4 tem 2 ^ 4 = 16 processos (vértices de um hipercubo na 4ª dimensão)
Cada vértice se liga aos seus 4 vizinhos.

No caso 2 e 3, é relativamente fácil você desenhar os vértices e arestas. No caso 4, é um pouco mais difícil, mas acho que é assim:

Provavelmente a parte mais chata é definir uma estrutura de dados para representar os processos e indicar seus vizinhos.

#6

http://www.cs.cf.ac.uk/Parallel/Year2/section5.html

(Achei isso com a consulta ao Google “hypercube interconnection network” ).

Ele diz isto aqui:

Acho que com isso seu problema está resolvido. Nada como procurar as coisas em inglês :slight_smile:

#7

entanglement

Obrigada pelo material.
Consegui entender como defino com quem cada um se ligará.
Só preciso conseguir implementar isso…rs

Só mais alguma perguntinha:

Tem alguma função no java que me permite identificar o próximo de um numero que difere apenas um bit(Conforme explicação do hipercubo). Por exemplo :

  • o 2 que é 010 seus vizinhos seriam 000,011,110. Há alguma função que me ajude a calcular isso?

Obrigada

#8

A rigor, não, mas não é difícil você fazer isso. Digamos que você queira determinar os números 0, 3 e 6 a partir do número 2, para um hipercubo de ordem 3 (que é o que você apresentou como exemplo). Você poderia fazer algo como:

int n = 2; // neste caso o número é 010
for (int i = 0; i < 3; ++i) {
    int x = n ^ (1 << i); 
    System.out.println (x); 
}

O primeiro valor mostrado será n XOR 1, que é 3, o segundo valor mostrado será n XOR 2, que é 0, e o segundo valor será n XOR 4, que é 6.
OK?

#9

entanglement,

agora deu uma clareada legal em minha mente…
:slight_smile:

To aqui implementando …

Na verdade já consegui implementar… Facinho…
Fiz dessa forma (Me corrija se estiver algo errado)

[code]int n = 2;
int k = 3;
int x = (int) Math.pow(n, k);
System.out.println("" + x);

    for(int i=0;i<x;i++){
       
        
        for(int j=0;j<3;++j){
            int re = i ^ (1><<j);
            System.out.println(i + " mandou para " + re);
           
        }
         System.out.println("--");
    }

[/code]

Agora é só eu implementar usando socket!!!

#10

s

#11