Questões de Revisão - Programação Dinâmica - Gabarito
7 pág.

Questões de Revisão - Programação Dinâmica - Gabarito


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização2 páginas
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Questões de Revisão
Programação Dinâmica
1. Algoritmos criados para resolver um mesmo problema podem diferir de forma drástica
quanto a sua eficiência. Para evitar este fato, são utilizadas técnicas algorítmicas, isto é,
conjunto de técnicas que compreendem os métodos de codificação de algoritmos de forma a
salientar sua complexidade, levando-se em conta a forma pela qual determinado algoritmo
chega à solução desejada. Considerando os diferentes paradigmas e técnicas de projeto de
algoritmos, analisem as afirmações, a seguir.
I. A técnica de tentativa e erro (backtracking) efetua uma escolha ótima local, na esperança
de obter uma solução ótima global. 
II. A técnica de divisão e conquista pode ser dividida em três etapas: dividir a instância do
problema em duas ou mais instâncias menores; resolver as instâncias menores recursivamente; obter
a solução para as instâncias originais (maiores) por meio da combinação dessas soluções.
III. A técnica de programação dinâmica decompõe o processo em um número finito de
subtarefas parciais que devem ser exploradas exaustivamente.
IV. O uso de heurísticas (ou algoritmos aproximados) é caracterizado pela ação de um
procedimento chamar a si próprio, direta ou indiretamente.
É correto apenas o que se afirma em
A. I
B. II
C. I e IV
D. II e III
E. III e IV
2. Analise as afirmativas a seguir.
I. A programação dinâmica é um método ascendente que aborda um dado problema
subdividindo-o em problemas mínimos, soluciona esses subproblemas, guarda as soluções parciais,
combina os subproblemas e sub-resultados para obter e resolver os problemas maiores, até
recompor e resolver o problema original.
II. A divisão e conquista é um método recursivo e, por isso, descendente que decompõe
sucessivamente um problema em subproblemas independentes triviais, resolvendo-os e combinando
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
as soluções em uma solução para o problema original.
III. Um algoritmo guloso sempre faz escolhas que parecem ser as melhores no momento, ou
seja, escolhas ótimas locais acreditando que estas escolhas o levem a uma solução ótima global. Por
essa estratégia, nem sempre asseguram-se soluções ótimas, mas, para muitos problemas, as soluções
são ótimas. Os problemas ideais para essa estratégia não devem ter a propriedade de subestrutura
ótima. A análise permite concluir que
A. todas as afirmativas são verdadeiras.
B. todas as afirmativas são falsas.
C. apenas as afirmativas I e II são verdadeiras.
D. apenas as afirmativas II e III são verdadeiras.
E. apenas a afirmativa III é verdadeira.
3. Cm base nos paradigmas de projeto de algoritmos, relacione a coluna da esquerda com a
coluna da direita.
(I) Tentativa e Erro. (A) Solução com garantia de distância da ótima.
(II) Divisão e Conquista. (B) Subdivisão de problemas em partes menores, de tamanho 
semelhante.
(III) Balanceamento. (C) Calcula a solução para os subproblemas, dos problemas 
menores para os maiores, armazenando os resultados parciais 
durante o processo, reutilizando-os assim que possível.
(IV) Algoritmos Aproximados. (D) Geralmente exaurem-se todas as possibilidades para se 
encontrar uma solução. Todos os passos em direção à solução 
final são registrados. Se alguns dos passos não estiverem 
relacionados com a solução final, podem ser apagados.
(V) Programação Dinâmica. (E) Divide problema em partes menores e combina sua 
solução em uma solução global.
Assinale a alternativa que contém a associação correta.
A. I-A, II-D, III-B, IV-C, V-E.
B. I-B, II-A, III-C, IV-E, V-D.
C. I-B, II-A, III-E, IV-D, V-C.
D. I-C, II-A, III-D, IV-B, V-E.
E. I-D, II-E, III-B, IV-A, V-C.
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
4. Quanto à análise de algoritmos, considere as afirmativas a seguir.
I. A programação dinâmica pode levar a soluções eficientes para algoritmos recursivos com
complexidade exponencial.
II. Os algoritmos tentativa e erro são impraticáveis com solução recursiva, pois são
aplicados exaustivamente.
III. Um algoritmo recursivo tem tempo de execução inferior à codificação iterativa para a
solução do mesmo problema.
IV. Uma árvore binária de pesquisa é adequada para a solução de problemas de natureza
recursiva.
Assinalem a alternativa correta.
A. Somente as afirmativas I e II são corretas.
B. Somente as afirmativas I e IV são corretas.
C. Somente as afirmativas III e IV são corretas.
D. Somente as afirmativas I, II e III são corretas.
E. Somente as afirmativas II, III e IV são corretas.
5. Alice vai sair em uma viagem longa, que começa na estrada no quilômetro 0 (zero). Ao
longo do caminho existem n hotéis, nos quilômetros a1 < a2 < ... < an, onde cada ai é medido
partindo do ponto inicial. Os únicos lugares onde você pode parar são esses hotéis, mas pode
escolher dentre eles em qual parar. Alice tem de parar no hotel final (no quilômetro an), que
é o seu destino. Ela gostaria, idealmente, de viajar 200 quilômetros por dia, mas isso pode
não ser possível (dependendo do espaçamento de hotéis). Se Alice viaja x quilômetros
durante um dia, a penalização para aquele dia é (200 \u2013 x)2. Você quer planejar a sua viagem
para minimizar a penalização total \u2013 ou seja, a soma das penalizações em todos os dias.
Sendo assim, é possível aplicar programação dinâmica para tal problema de modo a
desenvolver um algoritmo eficiente que determine a sequência ótima de hotéis nos quais
parar? Justifiquem. 
Sim, pois se observa o princípio da otimalidade, uma vez que o custo ótimo global consiste
em uma sequência ótima de hoteis \u2013 o que intrinsecamente compreende subproblemas
sobrepostos, afinal incluir ou não um hotel acarreta em penalizações e podem impactar as
demais decições em busca do ótimo global. Pode-se armazenar as penalizações em memória
auxiliar, e numa visão bottom-up calcular as distâncias entre os hotéis e identificar aqueles
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
que minimizam as penalizações com base nos cálculos efetuados.
6. Yuckdonald's está pensando em abrir uma série de restaurantes ao longo da Quaint Valley
Highway (QVH). Os n possíveis lugares estão ao longo de uma linha reta e as distâncias
desses lugares partindo do começo da QVH são, em quilômetros e em ordem crescente, m1,
m2, ..., mn. As restrições são as seguintes:
\u2022 Em cada lugar, Yuckdonald's pode abrir no máximo um restaurante. O lucro esperado de
abrir um restaurante no lugar i é pi, onde pi > 0 e i = 1, 2, ..., n.
\u2022 Quaisquer dois restaurantes devem estar a, pelo menos, k quilômetros um do outro, onde k é
um inteiro positivo.
É viável aplicar programação dinâmica para computar o lucro total esperado máximo sujeito às
dadas restrições? Justifiquem.
Sim, pois se observa o princípio da otimalidade, uma vez que o lucro ótimo global consiste
em uma sequência ótima de locais que provêem lucro máximo \u2013 o que intrinsecamente
compreende subproblemas sobrepostos, afinal decidir sobre o local que garanta um lucro
ótimo local impacta as demais decisões. Sob a visão bottom-up, pode-se calcular os lucros
nos n lugares ao longo da linha rede identificar aqueles que maximizam o lucro global.
7. O seguinte algoritmo é basedo em programação dinâmica? Justifiquem.
algoritmo7 (cn, \u2026, c1, L)
1 para m   1 \u2190 até n faça
2  X[m]   \u2190 \uf0a5
3  k   m\u2190
4  s   c\u2190 m
5  enquanto k > 1 e s   L \u2264 faça
6  X\u2019   (L \u2212 s)\u2190 3 + X[k\u22121]
7  se X0 < X[m] então X[m]   X\u2019\u2190
8  k   k \u2212 1\u2190
9  s   s + 1 + c\u2190 k
10  se s   L \u2264 então X[m]   0\u2190
11 retorna X[1]
Sim, pois se percebe um algoritmo iterativo no qual