MAC 741 - Introdução a Algoritmos e Arquiteturas Paralelas
Lista de exercícios 5
um vetor de elements
tirados de um conjunto linearmente ordenado.
O problema de mínimo prefixo é
calcular para cada i, 
,
o elemento mínimo entre
.
Desenvolva um algoritmo paralelo
de tempo O( 
) para resolver o problema
de mínimo prefixo usando um total
de O(n) operações.
Diga também o modelo em que roda seu algoritmo.
(Dica: rever antes o algoritmo de soma prefixa (seção 2.1.1).
.
O número total de operações deve ser O(n).
um vetor de elements
tirados de um conjunto linearmente ordenado.
O menor-esquerda de 
, para 
, é o
elemento 
, se existir, tal que k é o maior índice
satisfazendo 
e 
.
Escreva um algoritmo PRAM CRCW prioritário
que obtenha todos os menores-esquerdas de A em
tempo O(1) usando O( 
) operações.
(Dica: use o exercício anterior.)