Baixe o app para aproveitar ainda mais
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 (r1, n1) + escolhaDeC (r, n1) } 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. 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; • 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 1 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 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 nr 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 nr+j faça← M[i, j] T[i1, j1] + T[i1, j]← retorne M[n, r] } b) Implemente o algoritmo escolhaPD e efetue a análise de sua complexidade assintótica de tempo. 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 2 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 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. a) Elabore um algoritmo eficiente baseado em Programação Dinâmica que resolva o problema; b) Indique a sua complexidade computacional; c) Defina uma instância do problema e aplique a sua soluçã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 M i · 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 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 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 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 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. 4 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computaçã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. 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 campos 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. 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 deforma que os produtos feitos das peças resultantes deem a soma máxima de preços de venda? Justifique. 5 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 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. 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é n1 faça L[i, 1] = 0 para j = 0 até m1 faça L[1, j] = 0 para i = 0 até n1 faça para j = 0 até m1 faça se xi = yj então L[i,j] = L[i1, j1] + 1 senão L[i,j] = max{L[i1, j], L[i, j1]} retorna arranjo L a) O algoritmo utiliza a técnica de programação dinâmica? Justifique. 6 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação b) Determine a complexidade assintótica do algoritmo. 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. 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. 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 7 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 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 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. 8 ANÁLISE DE ALGORITMOS Bacharelado em Ciências da Computação 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. 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). 9 Lista de Exercícios de Fixação 06
Compartilhar