MAC 741 - Introdução a Algoritmos e Arquiteturas Paralelas
Primeira Prova - 9/10/96
(Permitida consulta a livros e notas de aula.)

Nome: _______________________________________________________ Nota: _______

1. (1.5 pontos) Quantos hipercubos de dimensão n disjuntos estão contidos num hipercubo de dimensão m, para ? (Por exemplo, um hipercubo de dimensão 2 contém dois hipercubos de dimensão 1.)
2. (1 ponto) Refaça a questão acima se permitirmos superposição de vértices mas não de arestas. (Por exemplo, um hipercubo de dimensão 2 contém quatro hipercubos de dimensão 1.)
3. (1.5 pontos) Construa o código de Gray refletido (reflected Gray code) de 4 bits.
4. (3 pontos) Mostre que qualquer grafo de Bruijn de n vértices contém uma árvore binária completa de n-1 vértices.
5. (3 pontos)

   Seja dada uma lista linear ligada, em que cada elemento aponta ao próximo elemento, com o último apontando para si próprio. (Para cada elemento i suponha dado sucessor suc(i).) List ranking é o problema de determinar a distância de cada elemento da lista ao último. Escreva um algoritmo paralelo para list ranking usando a técnica de pointer jumping. Seu algoritmo é ótimo? por que?

 
• About this document ...