Exercícios de Programação Paralela e Distribuída

Prévia do material em texto

Lista de exercícios
Programação Paralela e distribuída
Algoritmos para Paralelizar
Nos exercícios abaixo monte a versão sequencial de cada exercício e posteriormente modifique-os para utlizar as bibliotecas
apresentadas em sala.
(1) Crie um programa que possua 3 threads (p, q e r respectivamente), faça com que a thread r imprima somente quando p e
q já tenham impresso ao menos 4 vezes.
(2) Determinante de uma matrizes grandes utilizando o teorema de Laplace.
(3) Caixeiro viajante para um grafo clique com n nós (A quantidade de nós deve ser definida por parâmetro e o peso das
arestas de form aleatória).
(4) Programa para resolver PAs de forma iterativa (os parâmetros devem ser passados por linha de comando) pela fórmula
a1 +
∑n
i=2 r.
(5) Programa para resolver PGs de forma iterativa (os parâmetros devem ser passados por linha de comando) pela fórmula
a1
∏n
i=2 q.
(6) Implemente um programa onde o usuário passa como parâmetro 2 números inteiros num intervalo e apresente ao usuário
as seguintes informações:
1. Quantidade de números primos.
2. Quantidade de números múltiplos de 3.
3. Quantidade de números múltiplos de 7.
4. Soma de todos os números múltiplos de 13.
5. Soma de todos os números múltiplos de 29.
(7) Problema dos filósofos famintos (Passe o número de filósofos por parâmetro de função).
6. Faça uma versão com consistência para evitar deadlocks
(8) Resolva as séries abaixo fazendo com que o número de iterações seja passado como parâmetro
7. ln(1 + x) =
∑n
i=0
(−1)i
1+i (xi+1)
8. cos(x) =
∑n
i=0
(−1)i
(2i)! x
2i
9. cos(x) =
∑n
i=0
(−1)i
(2i+1)!x
2i+1
(9) Implemente o algoritmo de validação de CPF (O CPF deve ser passado como parâmetro).
(10) Implemente o algoritmo de validação de CNPJ (O CNPJ deve ser passado como parâmetro).
(1) Processos e Threads
1. Diferencie a execução de um programa Paralelo e um programa sequencial.
2. Quais as diferenças em nível de S.O. que processos e threads possuem e como os mesmos se correlacionam?
3. O que são regiões com potencial paralelismo dentro de um código?
4. O esforço computacional entre um programa paralelo e sequencial é o mesmo? E o seu tempo de relógio?
(2) Problemas de exclusão mútua
1
5. Apresente 1 contexto em que a exclusão mútua se torna necessária.
6. Apresente as soluções que pertterson surgeriu para o problema da exclusão mútua e quais as suas vantagens /
desvantagens e os problemas no uso de cada um deles.
7. O que é o busy-wait e como semáforos contorname este problema.
8. Quais os 2 métodos existem no uso de semáforos que como estes funcionam?
2