Prova 1 - 2010-1

Prévia do material em texto

UNIVERSIDADE FEDERAL DE MINAS GERAIS
INSTITUTO DE CIEˆNCIAS EXATAS
DEPARTAMENTO DE CIEˆNCIA DA COMPUTAC¸A˜O
ALGORITMOS E ESTRUTURAS DE DADOS III
Professores: Wagner Meira Jr e Jussara Almeida
Primeiro Teste: 12.5 pontos
Aluno:
Avaliador:
• Durac¸a˜o do teste: 50 minutos.
• Prova individual e sem consulta.
• Faz parte da prova a interpretac¸a˜o das questo˜es. Caso voceˆ ache que falta algum
detalhe nas explicac¸o˜es fac¸a as suposic¸o˜es que achar necessa´rias e documente-as na
resoluc¸a˜o das questo˜es.
1a Questa˜o ( 1+0.5+1+0.5 pontos)
Uma estrate´gia tradicional de aproximar o valor de uma integral de uma func¸a˜o e´
a estrate´gia dos trape´zios, ou seja, divida o intervalo de integrac¸a˜o em um nu´mero
de sub-intervalos e calcule a a´rea do trape´zio formado em cada sub-intervalo. Uma
forma de tornar esse me´todo mais eficiente e preciso e´ realizar refinamentos (ou seja,
subdividir recursivamente) nos intervalos onde a func¸a˜o na˜o for bem aproximada por
uma reta. A aproximac¸a˜o pode ser avaliada pela colinearidade entre um nu´mero
pre´-fixado de pontos do intervalo. Assuma um modelo de memo´ria compartilhada.
Pede-se:
1. Descreva uma estrate´gia baseada em paralelismo de dados
A estrate´gia de paralelismo de dados mais simples e´ dividir o intervalo em p
sub-intervalos, onde p e´ o nu´mero de cores e cada core recebe um sub-intervalo
para calcular a integral parcial daquele intervalo. Ao fim do processo, e´ realizada
uma reduc¸a˜o para chegar ao valor desejado.
Nota Crite´rio S/N
0.5 Conceituou corretamente paralelismo de dados
1.0 Apresentou uma estrate´gia correta de paralelismo de dados
2. Indique uma fonte de degradac¸a˜o de desempenho na sua paralelizac¸a˜o.
A fonte de degradac¸a˜o de desempenho mais prova´vel e´ o desbalanceamento de
carga entre os cores, como consequeˆncia da variac¸a˜o da func¸a˜o a ser integrada,
ou seja, alguns cores trabalham mais pois teˆm que realizar mais refinamentos.
Pode tambe´m haver contenc¸a˜o pela varia´vel compartilhada que acumula a inte-
gral.
Nota Crite´rio S/N
0.25 Indicou uma fonte de degradac¸a˜o de desempenho
0.5 Fonte de degradac¸a˜o de desempenho e´ pertinente
3. Descreva uma estrate´gia baseada em paralelismo de tarefas
A estrate´gia baseada em paralelismo de tarefas usaria uma sacola de tarefas onde
intervalos a serem integrados seriam armazenados. Um core, quando ocioso,
requisitaria um intervalo a` sacola e retornaria o valor da integral parcial ou
intervalos menores a serem armazenados na sacola.
Nota Crite´rio S/N
0.5 Conceituou corretamente paralelismo de tarefas
1.0 Apresentou uma estrate´gia correta de paralelismo de tarefas
4. Indique uma fonte de degradac¸a˜o de desempenho na sua paralelizac¸a˜o.
A fonte de degradac¸a˜o de desempenho mais prova´vel e´ contenc¸a˜o (ou sincro-
nizac¸a˜o), uma vez que a sacola de tarefas e´ um recurso compartilhado e u´nico
no sistema. Da mesma forma, podemos tambe´m ter contenc¸a˜o para acesso a`
varia´vel que armazena o valor da integral.
Nota Crite´rio S/N
0.25 Indicou uma fonte de degradac¸a˜o de desempenho
0.5 Fonte de degradac¸a˜o de desempenho e´ pertinente
2a Questa˜o (1.5+1.5 pontos)
Suponha que voceˆ tenha executado o seu algoritmo de integrac¸a˜o em uma ma´quina
com 8 cores. Os tempos de execuc¸a˜o obtidos foram:
Cores 1 2 3 4 5 6 7 8
Tempo 100 55 40 34 32 31 33 36
Pede-se:
1. Apresente uma poss´ıvel explicac¸a˜o para o fato de que o uso de 2 cores na˜o
reduziu o tempo de execuc¸a˜o pela metade. Deˆ um exemplo de como uma de
suas propostas de paralelizac¸a˜o poderia apresentar esse comportamento.
Uma explicac¸a˜o o´bvia neste caso e´ a frac¸a˜o serial inerente ao problema. Em
ambas as propostas de implementac¸a˜o a varia´vel de reduc¸a˜o, que armazena o
valor da integral representa frac¸a˜o serial.
Nota Crite´rio S/N
0.5 Apresentou uma explicac¸a˜o va´lida
1.5 Identificou a fonte de degradac¸a˜o na implementac¸a˜o
2. Apresente uma poss´ıvel explicac¸a˜o para o fato de que o tempo de execuc¸a˜o
aumenta para mais de 7 cores.
Uma explicac¸a˜o o´bvia neste caso e´ a computac¸a˜o adicional e o tempo de espera.
A contenc¸a˜o pela sacola de tarefas e´ um caso t´ıpico, ale´m do desbalanceamento
de carga no caso do paralelismo de dados.
Nota Crite´rio S/N
0.5 Apresentou uma explicac¸a˜o va´lida
1.5 Identificou a fonte de degradac¸a˜o na implementac¸a˜o
3a Questa˜o ( 1.5+1+1.5+1+1.5 pontos)
Suponha que voceˆ tenha dois conjuntos A e B, cada um contendo n inteiros positivos.
Estes nu´meros podem ser ordenados em qualquer ordem arbitra´ria dentro de cada
conjunto. Dada uma configurac¸a˜o de ordenac¸a˜o, seja ai o i-e´simo elemento de A e
bi o i-e´simo elemento de B. Com base nessa configurac¸a˜o voceˆ recebe um preˆmio de
pini=1a
bi
i . O objetivo e´ maximizar o preˆmio.
Pede-se:
1. Apresente um algoritmo forc¸a-bruta (tentativa e erro) para resolver o problema.
O algoritmo forc¸a-bruta faria todas as permutac¸o˜es poss´ıveis entre os dois ve-
tores, gerando todas os produto´rios poss´ıveis.
Nota Crite´rio S/N
0.5 Identifica a necessidade de fazer as permutac¸o˜es
1.5 Argumenta pela gerac¸a˜o de todos os produto´rios poss´ıveis
2. Qual e´ a complexidade do seu algoritmo? Explique.
Temos dois vetores a serem permutados, cada um de tamanho n. A permutac¸a˜o
de cada vetor gera n! configurac¸o˜es. Para cada permutac¸a˜o do vetor A, temos
n! permutac¸o˜es de B. O resultado e´ O(n!× n!).
Nota Crite´rio S/N
0.5 Identificou a permutac¸a˜o
1.0 Compoˆs as permutac¸o˜es adequadamente
3. Apresente uma estrate´gia gulosa para resolver o problema.
Ordene decrescentemente cada um dos vetores e realize a multiplicac¸ao par a
par. Ordenar crescentemente tambe´m funciona.
Nota Crite´rio S/N
0.5 Estrate´gia e´ gulosa
1.5 Estrate´gia gera soluc¸a˜o
4. Qual a complexidade da sua estrate´gia gulosa?
E´ O(nlogn), o custo de ordenac¸a˜o dos vetores. O ca´lculo do produto´rio tem
custo linear.
Nota Crite´rio S/N
0.5 Identificou o componente de custo
1.0 Calculou a complexidade corretamente
5. A soluc¸a˜o gulosa encontrada e´ o´tima? Por que?
A soluc¸a˜o encontrada e´ o´tima. Considere quaisquer ı´ndices i e j tal que i < j e
os termos abii e a
bj
j . Podemos mostrar que e´ sempre melhor incluir estes pares
do que a
bj
i e a
bi
j , ou seja, a
bi
i a
bj
j ≥ a
bj
i a
bi
j . Uma vez que A e B sa˜o ordenados em
ordem decrescente e i < j, temos que ai ≥ aj e bi ≥ bj. Uma vez que ai e aj sa˜o
positivos e bi− bj ≥ 0, temos que a
bi−bj
i ≥ a
bi−bj
j . Multiplicar ambos os lados por
a
bj
i a
bj
j leva a a
bi
i a
bj
j ≥ a
bj
i a
bi
j provando a otimalidade. Ou seja, a sub-estrutura
o´tima compreende comec¸ar pelas maiores poteˆncias poss´ıveis.
Nota Crite´rio S/N
0.5 Respondeu Sim
1.0 Apresentou a justificativa
Item Nota Observac¸o˜es
1.1
1.2
1.3
1.4
2.1
2.2
3.1
3.2
3.3
3.4
3.5
Total