Divisão e conquista em programação paralela

Prévia do material em texto

Divisão e conquista em programação paralela
Exercícios
1. O termo programação paralela pode ser utilizado em conjunto com computação
paralela, pois se refere a sistemas de alta eficiência. A programação paralela é o
processo que decompõe um problema em tarefas menores, de modo que sejam
executadas simultaneamente, utilizando vários recursos de computação.
Dessa forma, é possível afirmar que:
I. utilizando a programação paralela, as tarefas podem ser paralelizadas, sendo
executadas ao mesmo tempo, a partir do uso de mais computadores ou vários
núcleos de um processador;
II. a programação paralela é importante para grandes projetos, que demandam
velocidade e precisão;
III. mesmo sendo uma tarefa complexa, a programação paralela é fundamental, pois
permite que desenvolvedores, pesquisadores e usuários consigam realizar
pesquisas e análises de maneira mais rápida e eficiente, se comparada a programas
que processam somente uma tarefa por vez;
IV. a programação paralela, apesar de ser uma tarefa simples, é muito importante,
pois permite que desenvolvedores, pesquisadores e usuários consigam realizar
pesquisas e análises de maneira mais rápida e eficiente, se comparada a programas
que processam somente uma tarefa por vez.
Quais afirmativas estão corretas?
Você acertou!
B. I, II e III.
A   programação   paralela   é   uma   tarefa   complexa,   mas   fundamental,   pois   é   muito
importante em projetos que exijam velocidade e precisão. Utilizando-a, as tarefas podem
ser executadas ao mesmo tempo.
2. Hardwick (1997) afirma que o método de divisão e conquista é a técnica mais
conhecida de projetos de algoritmos, pois permite resolver de maneira mais
simples um problema maior.
Sendo assim, assinale a alternativa correta.
Você acertou!
E. Dividir e conquistar pode ser considerada uma variante da técnica de programação de
cima para baixo mais geral.
A opção correta diz que dividir e conquistar é considerada uma variante da técnica de
programação de cima para baixo mais geral.
A  opção  que  diz   ser   importante   que  um  algoritmo  diferente   possa   ser   aplicado  aos
subproblemas  do  problema  original   está   incorreta,  pois  o  mesmo algoritmo  pode  ser
aplicado e não diferentes.
A opção que cita os subproblemas como instâncias do mesmo problema está incorreta,
pois,   apesar   dos   subproblemas   serem   instâncias   do   mesmo   problema,   podem   ser
expressos recursivamente.
A opção que diz ser necessária uma fase de combinação está incorreta, pois o necessário
é uma fase de divisão, para o problema ser dividido em subproblemas e uma fase de
combinação.
A opção que diz que soluções são combinadas está incorreta, pois fala que o processo se
repete até que encontre soluções distintas, sendo que o correto é que ele se repita até
que seja encontrada uma solução única.
3. Entre os modelos de aplicação da programação paralela, o mais comum é o divid-
and-conquer (divisão e conquista). Hardwick (1997) afirma que o método de divisão
e conquista é a técnica mais conhecida de projetos de algoritmos, já que permite
resolver de maneira mais simples um problema maior.
Esse algoritmo funciona seguindo um plano que ocorre na seguinte ordem:
Você acertou!
C. dividir, conquistar e combinar.
Os algoritmos de dividir e conquistar funcionam seguindo o plano de dividir, conquistar e
combinar.  Em "dividir",  o  problema é  dividido  em subproblemas  menores,  sendo eles
geralmente   do   mesmo   tamanho.   Em   "conquistar",   os   subproblemas   são   resolvidos
recursivamente. Em "combinar", as soluções obtidas pelos subproblemas são conectadas,
obtendo a solução do problema original. Não há uma etapa chamada "apresentar" nesse
algoritmo.
4. O pseudocódigo é utilizado como referência para outros métodos, que podem
diferenciar algoritmos de divisão e conquista para sua implementação em
arquiteturas paralelas.
Assinale a alternativa que contém os métodos de divisão e conquista em
programação paralela presentes na literatura, de acordo com Hardwik (1997).
Você acertou!
B. Fator de ramificação; equilíbrio; divisibilidade embaraçosa; dependência de dados da
função   de   dividir;   dependência   de   dados   da   função   de   tamanho;   paralelismo   ou
sequencialidade de controle; e paralelismo de dados.
A opção que cita "fator de ramificação; equilíbrio; divisibilidade embaraçosa; dependência
de dados da função de dividir; dependência de dados da função de tamanho; paralelismo
ou sequencialidade de controle; e paralelismo de dados" é a correta. As demais estão
incorretas,   pois   trocam  alguns  métodos,   como  dependência   de   dados   da   função  de
conquistar (seria dependência de dados da função de dividir); e dependência de dados da
função de combinar (a dependência de dados seria da função de tamanho).
5. Quando o tamanho total dos subproblemas de um algoritmo de divisão e
conquista tem algum nível de dependência dos dados de entrada, ele vai ter uma
função de tamanho dependente dos dados. Com isso, esse algoritmo forma uma
subclasse. Esse modelo de algoritmo adiciona ou descarta elementos, baseando-se
nos dados de entrada, para tentar reduzir o tamanho do problema.
Assinale a alternativa que se refere ao método de dependência de dados da função
de tamanho.
Você acertou!
E. Podem   ser  mais   complexos   para   implementação,   pois   os   desequilíbrios   de   carga
podem surgir na quantidade total dos dados em um processador.
A  opção   correta   que   se   refere  ao  método   de   dependência   de   dados   da   função   de
tamanho é a que diz que este pode ser mais complexo para  implementação,  pois os
desequilíbrios de carga podem surgir na quantidade total dos dados em um processador.
A opção que cita o número de subproblemas em que um problema é dividido se refere ao
método de ramificação. A opção que fala sobre apresentar a vantagem de não necessitar
de balanceamento  de carga está   incorreta,  pois  se  refere ao método de equilíbrio.  A
opção que apresenta que o problema pode ser dividido entre dois ou mais subproblemas
de maneira imediata está incorreta, pois se refere à divisibilidade embaraçosa. Por fim, a
opção que cita que geralmente está presente no estágio de divisão está incorreta, pois se
refere ao paralelismo de dados.
	Divisão e conquista em programação paralela
	Exercícios