MAC 741 - Introdução a Algoritmos e Arquiteturas Paralelas
Lista de exercícios 5
Seja 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).
Seja B um vetor booleano de tamanho n.
Escreva um algoritmo PRAM CRCW prioritário de tempo O(1) para achar
o menor índice k tal que .
O número total de operações deve ser O(n).
Seja 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.)