Exercícios de Fixação 06 - Programação Dinâmica - Gabarito

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Lista de Exercícios de Fixação 06
Programação Dinâmica
 1. [Prática] Seja o problema do número de combinações, a seguir. 
Entrada: Dois números inteiros n e r, em que n indica o número de elementos dos quais temos que
escolher r
Saída: O número possível de combinações de r itens
A solução de divisão-e-conquista (DeC) para esse problema, considera duas formas de proceder:
• Escolher o primeiro item e depois, os r-1 itens dos n-1 itens restantes;
• Não escolher o primeiro item e depois, r itens dos n-1 itens restantes.
Tais procedimentos são observados no algoritmo DeC, a seguir.
algoritmo escolhaDeC (r, n){
se r = 0 ou n = r então
retorne 1
caso contrário 
retorne escolhaDeC (r-1, n-1) + escolhaDeC (r, n-1)
}
 a) Implemente o algoritmo escolhaDeC e efetue a análise de sua complexidade assintótica
de tempo. A solução DeC faz cálculos repetidos desnecessários? Justifique.
[Solução livre]
A análise do algoritmo requer a resolução da seguinte relação de recorrência: T(n) =
2T(n – 1) + c [tarefa sua efetuar os cálculos] – o que resulta em O(2n). 
Da mesma forma que no exemplo de Fibonacci, a solução faz cálculos repetidos. Sendo
assim, é viável a programação dinâmica.
Se há subproblemas repetidos, é provável que possamos utilizar memória auxiliar e aplicar
Programação Dinâmica (PD). Existe, portanto, uma forma de transformar um algoritmo DeC em
um algoritmo PD. Veja os passos:
• A parte do algoritmo que corresponde à conquista (recursão) deve ser substituída por uma
olhada na memória auxiliar;
1
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
• Em vez de retornar um valor, o armazenamos na memória auxiliar;
• Definimos o caso base para iniciar a memória auxiliar;
• Determinamos o padrão de preenchimento do restante da memória auxiliar.
Para o algoritmo escolhaDeC, podemos utilizar uma matriz (n+1) x (r+1) para comportar os
cálculos intermediários e o resultado final, e definir o padrão de caminhamento e preenchimento da
matriz, conforme os esquemas a seguir.
Assim, o algoritmo escolhaPD pode ser definido como segue.
algoritmo escolhaPD(r, n){ 
//M[i, j] indica o número possível de combinações para escolher j itens dentre i itens
para i ← 0 a n-r faça
M[i, 0] ← 1
para i ← 0 a r faça
M[i, i] ← 1
para j ← 1 a r faça
para i ← j + 1 a n-r+j faça
M[i, j] ← T[i-1, j-1] + T[i-1, j]
retorne M[n, r]
2
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
}
 b) Implemente o algoritmo escolhaPD e efetue a análise de sua complexidade assintótica de
tempo.
[Solução livre].
O algoritmo é O(nr) [é tarefa sua efetuar os cálculos].
 2. [Prática] O triângulo de Pascal é um triângulo de números em que cada elemento é a soma dos 2
elementos acima, com exceção dos elementos das pontas que têm valor 1. Veja um exemplo do
triângulo de Pascal para n=4. O problema consiste em construir o triângulo de Pascal de altura n.
Considere ainda a implementação, baseada em recursão, a seguir.
public void imprimePascal(){
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
System.out.println(pascal(i,j));
}
public int pascal(int linha, int coluna){
if (linha == 1) || (coluna == 1)
return 1;
eles return pascal(linha, coluna – 1) + pascal(linha – 1 , coluna);
}
Sendo assim, responda o que se pede.
No triângulo de Pascal, cada elemento é a soma dos 2 elementos acima, com a exceção das laterais que são
3
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
sempre 1, conforme exibe a figura. Podemos rotacionar o triângulo e observamos sua similaridade com uma
matriz.
 a) Elabore um algoritmo eficiente baseado em Programação Dinâmica que resolva o problema;
[Solução livre].
 b) Indique a sua complexidade computacional;
(n2)
 c) Defina uma instância do problema e aplique a sua solução.
[Execução da implementação].
 3. [Prática] Considerando o algoritmo que calcula o produto entre duas matrizes Ap x q e Bq x r requer
O(pqr) operações de multiplicação. Por exemplo, M = M1[10, 20] · M2[20, 50] · M3[50, 1] · M4[1,
100], a ordem M = M1 · (M2 · (M3 · M4)) requer 125.000 operações enquanto M = (M1 · (M2 · M3) ·
M4) requer apenas 2.200 operações. Tentar todas as ordens possíveis de multiplicações para avaliar o
produto de n matrizes de forma a minimizar o número de operações f(n) é um processo exponencial
de n, em que f(n) ≥ 2n-2. Porém, usando PD (Programação Dinâmica) é possível obter um algoritmo
O(n3), conforme exibimos a seguir. Considerando mij o menor custo para computar o produto Mi ·
Mi+1 · … · Mj, para 1 ≤ i ≤ j ≤ n, tem-se
mij=
0, se i= j
mini⩽k< j(mik+mk +1, j+d i−1dk d j), se j>i
O termo mik representa o custo mínimo para calcular M’ = Mi · Mi+1 · … · Mk. O segundo termo, mk+1,
j representa o custo mínimo para calcular M’’ = Mk+1 · Mk+2 · … · Mkj. O terceiro termo, di-1 · dk · dj, representa
o custo de multiplicar M’[di-1, dk] por M’’[dk, dj]. Portanto, quando j > i, mij representa o custo mínimo de
4
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
todos os valores possíveis de k entre i e j – 1 da soma dos três termos. Utilizando PD, o cálculo inicia com
mii para todo i, depois mi, i+1 para todo i, depois mi, i+2 e assim sucessivamente. Dessa forma, os valores m ik e
mk+1,j estarão disponíveis no momento de calcular mij. Sendo assim, implemente o algoritmo, a seguir.
Entrada: número n de matrizes e d0, d1, …, dn em que di-1 e di são as dimensões da matriz Mi
Saída: ordem de multiplicação de n matrizes de forma a obter o menor número possível de operações
n = comprimento[d] – 1
para i = 1 até n faça{
m[i,i] = 0 //custo para subproblemas de tamanho 1
}
para x = 2 até n faça{
para i = 1 até (n – x) + 1 faça{
j = i + x – 1
m[i, j] = ∞
para k = i até j – 1 faça{
q = m[i,k] + m[k+1, j] + d[i-1].d[k].d[j]
se q < m[i,j] então{
m[i,j] = q
s[i,j] = k //utilizada para construir a solução ótima
}
}
}
}
retorne m, s
[Solução livre]
 4. Comente os problemas, a seguir, com base na pergunta: O princípio da otimalidade se
aplica? 
 a) Para o problema de encontrar o caminho mais curto entre 2 cidades, se o caminho mais
curto entre Belo Horizonte e Curitiba passa por Campinas, então o caminho entre Belo
Horizonte e Campinas também é o mais curto possível, assim como o caminho entre
Campinas e Curitiba.
5
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
O princípio da otimalidade diz que o valor ótimo global pode ser definido em termos dos valores
ótimos dos subproblemas. Sendo assim, ele se aplica, uma vez que se trata de encontrar o caminho
mais curto entre dois vértices de um grafo (problema de otimização).
 b) Para o problema de encontrar o caminho mais longo entre 2 cidades, usando um dado
conjunto de estradas, um caminho simples nunca visita a mesma cidade duas vezes. Se o
caminho mais longo entre Belo Horizonte e Curitiba passa por Campinas, isso não
significa que o caminho possa ser obtido tomando o caminho mais simples mais longo
entre Belo Horizonte e Campinas, e depois o caminho simples mais longo entre
Campinas e Curitiba.
Quando os 2 caminhos simples são juntados, é pouco provável que o caminho resultante também
seja simples. Portanto, o princípio da otimalidade não se aplica.
 5. Vankin's Mile é um jogo de tabuleiro nxn para um único jogador. O jogador começa
escolhendo algum campo do tabuleiro. Depois, ele pode repetidamente, move uma posição
para a direita ou uma posição para baixo. O jogo termina quando a próxima posição cai fora
do tabuleiro. Cada campo do tabuleiro possui um número inteiro e o valor do jogo é igual a
soma doscampos visitados. O objetivo é encontrar o jogo de maior valor. Por exemplo, no
tabuleiro
3 1 -4 1
5 -1 9 2
6 5 -3 -5
 -8 -9 -7 -9
começando com 9 indo para baixo, e depois para direita, direita vale 9 – 3 – 5 = 1 e a melhor
solução começa com 3 indo para baixo, direita, direita, direita, direita vale 3 + 5 – 1 + 9 + 2
= 18.
Sendo assim, responda: é viável aplicar Programação Dinâmica ao problema? Justifique. 
O problema pode ser resolvido usando PD. Seja vij o valor na célula (i, j) e oij o maior valor
possível partindo da célula (i, j). Os valores o satisfazem
oij=
0,casoi>nou j>n
v ij+max oi+1, j , oi , j+1 , casocontrário
portanto, PD com tempo O(n2) é uma varredura da matriz o no final resolve o problema.
6
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Para obter o melhor caminho podemos armazenar – como sempre – ainda a informação sobre qual
das 2 possibilidades gerou o máximo na segunda linha da recorrência, e extrair este caminho no
final.
 6. É dada uma peça retangular de tecido com dimensões X x Y, onde X e Y são inteiros
positivos, e uma lista de n produtos que podem ser feitos usando o tecido. Para cada produto
i ∈ [1, n] você sabe que um retângulo de tecido de dimensões a i x bi é necessário, e que o
preço final de venda do produto é ci. Considere que ai, bi e ci são todos inteiros positivos.
Você tem uma máquina que pode cortar qualquer peça retangular de pano em duas peças,
horizontal ou verticalmente. É possível aplicar programação dinâmica para o projeto de um
algoritmo que determine o melhor retorno possível sobre a peça de tecido de X x Y, ou seja,
uma estratégia para cortar o tecido de forma que os produtos feitos das peças resultantes
deem a soma máxima de preços de venda? Justifique.
Sim, pois o princípio da otimalidade é aplicável ao contexto e os subproblemas são superpostos.
Afinal, o custo ótimo de cortar uma peça retangular de tecido é a soma dos custos ótimos de cortar 2
partes da peça retangular (e assim por diante).
 7. No problema da maior subsequência comum ou LCS (Longest Common Subsequence), tem-
se duas cadeias de caracteres X = x0x1x2...xn-1 e Y = y0y1y2...ym-1 definidas sobre algum
alfabeto (como o alfabeto {A, C, G, T} – comum em genética computacional) e deseja-se
encontrar a cadeia mais longa S que é uma subsequência de X e Y. 
Uma maneira de resolver o problema é enumerar todas as subsequências de X e escolher a
mais longa que for também uma subsequência de Y. Já que cada caractere de X está ou não
na subsequência, existem potencialmente 2n subsequências diferentes de X, cada uma das
quais requer tempo O(m) para determinar se é uma subsequência de Y. Assim, esta
abordagem de força bruta fornece um algoritmo exponencial executado em tempo O(2nm),
que é ineficiente. Vejamos um exemplo.
7
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
Dado o algoritmo, a seguir, respondam o que se pede.
Algoritmo LCS(X, Y):
Entrada: as cadeias X e Y com n e m elementos, respectivamente;
Saída: para i = 0, 1, …, n-1 e j = 0, 1, …, m-1, o comprimento L[i..j] da cadeia mais longa
que é uma subsequência tanto de X[0..i] = x0x1x2...xi quanto de Y[0..j] = y0y1...yj.
para i = 0 até n-1 faça
L[i, -1] = 0
para j = 0 até m-1 faça
L[-1, j] = 0
para i = 0 até n-1 faça
para j = 0 até m-1 faça
se xi = yj então
L[i,j] = L[i-1, j-1] + 1
senão
L[i,j] = max{L[i-1, j], L[i, j-1]}
retorna arranjo L
 a) O algoritmo utiliza a técnica de programação dinâmica? Justifique. Sim, pois o problema
foi dividido em subproblemas simples e dependentes, em que uma solução ótima para o
problema global deve ser uma composição de soluções ótimas para os subproblemas. 
 b) Determine a complexidade assintótica do algoritmo. O(mn), pois a operação dominante
é a comparação interna aos laços i e j.
 8. Dado o problema: Sejam n itens de tamanhos s1, s2, …, sn. Existe um subconjunto desses
itens com a soma dos tamanhos exatamente igual a S? Defina um algoritmo baseado em
programação dinâmica que resolva este problema e analise a sua complexidade.
Esta é uma variação do problema da mochila. Eis a ideia do algoritmo base para a solução do
problema, a seguir.
mochilaPD(n, S){
 T[0, 0] = true
8
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 for j = 1 to S do
 T[0, j] ← false
 for i ← 1 to n do
 for j ← 0 to S do
 T[i, j] ← T[i-1, j]
 if j – si ≥ 0 then
 T[i, j] ← T[i, j] v T[i-1, j – si]
 return T[n, S]
 9. Imagine uma grandeza que evolui com o tempo, aumentando ou diminuindo uma vez por
dia, de maneira irregular. Dado o registro das variações diárias desta grandeza ao longo de
um ano, queremos encontrar um intervalo de tempo em que a variação acumulada tenha sido
máxima. 
O Problema: Um segmento de um vetor A[p..r] é qualquer subvetor da forma A[i..k], com p
≤ i ≤ k ≤ r. A condição i ≤ k garante que o segmento não é vazio. A soma de um segmento
A[i..k] é o número A[i] + A[i+1] + … + A[k].
A solidez de um vetor A[p..r] é a soma de um segmento de soma máxima. Sendo assim,
propõe-se o seguinte problema:
Problema do Segmento de Soma Máxima: Calcular a solidez de um vetor A[p..r] de números
inteiros. Se o vetor não tem elementos negativos, sua solidez é a soma de todos os
elementos. Por outro lado, se todos os elementos são negativos então a solidez do vetor é o
valor de seu elemento menos negativo.
Considere o exemplo, a seguir. A cor mais clara destaca um segmento de soma máxima. A
solidez do vetor é 35.
Sendo assim, elabore um algoritmo de programação dinâmica para o problema. Em seguida,
apresente a sua complexidade assintótica.
Segue uma sugestão de solução.
SolidezPD (A, p, r)
9
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
1 F[p] ← A[p]
2 para q ← p + 1 até r faça
3 se F[q - 1] > 0
4 entao F[q] ← F[q-1]+A[q]
5 senao F[q] ← A[q]
6 x ← F[p]
7 para q ← p + 1 até r faça
8 se F[q] > x então x ← F[q]
9 devolva x
O consumo de tempo do algoritmo é (n).
 10.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, analise as afirmações abaixo.
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
10
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 11.Com 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
 12.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.
Assinale a alternativa correta.
11
ANÁLISE DE ALGORITMOS
Bacharelado em Ciências da Computação
 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
Referências
Dasgupta, S., Papadimitriou, C., Vazirani, U. Algoritmos. São Paulo: McGraw-Hill, 2009.
Ziviani, N. Projeto de Algoritmos com Implementações em Java e C++. São Paulo: Thomson
Learning, 2007.
Material didático – Análise e Técnicas de Algoritmos, elaborado por Jorge Cesar Abrantes de
Figueiredo, UFCG (Universidade Federal de Campina Grande).
12
	Lista de Exercícios de Fixação 06