Exercícios de Fixação 06 - Programação Dinâmica - Gabarito
12 pág.

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


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização3 páginas
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:
\u2022 Escolher o primeiro item e depois, os r-1 itens dos n-1 itens restantes;
\u2022 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 \u2013 1) + c [tarefa sua efetuar os cálculos] \u2013 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:
\u2022 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
\u2022 Em vez de retornar um valor, o armazenamos na memória auxiliar;
\u2022 Definimos o caso base para iniciar a memória auxiliar;
\u2022 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 \u2190 0 a n-r faça
M[i, 0] \u2190 1
para i \u2190 0 a r faça
M[i, i] \u2190 1
para j \u2190 1 a r faça
para i \u2190 j + 1 a n-r+j faça
M[i, j] \u2190 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 \u2013 1) + pascal(linha \u2013 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;
\uf051(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) \u2265 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 · \u2026 · Mj, para 1 \u2264 i \u2264 j \u2264 n, tem-se
mij=
0, se i= j
mini\u2a7dk< j(mik+mk +1, j+d i\u22121dk d j), se j>i
O termo mik representa o custo mínimo para calcular M\u2019 = Mi · Mi+1 · \u2026 · Mk. O segundo termo, mk+1,
j representa o custo mínimo para calcular M\u2019\u2019 = Mk+1 · Mk+2 · \u2026 · Mkj. O terceiro termo, di-1 · dk · dj, representa
o custo de multiplicar M\u2019[di-1, dk] por M\u2019\u2019[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 \u2013 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, \u2026, 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] \u2013 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 \u2013 x) + 1 faça{
j = i + x \u2013 1
m[i, j] = \u221e
para k = i até j \u2013 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 dos