Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 UNIVERSIDADE FEDERAL DE VIÇOSA DEPARTAMENTO DE INFORMÁTICA INF332 - Projeto e Análise de Algoritmos Prof. José Elias C. Arroyo Lista de Exercícios (Entrega 11 de dezembro) Programação Dinâmica, Limite Inferior de Problemas, NP-Completude 1) Problema do troco: Seja d = {d1, d2,..., dn} um conjunto de n valores distintos (moedas) correspondentes a uma unidade monetária. Suponha que existe uma quantidade ilimitada de cada moeda para serem usadas. O problema do troco consiste em formar uma quantidade X utilizando o menor número de moedas. a) Baseado em Programação Dinâmica, determine uma função recursiva para determinar o valor de uma solução (número de moedas utilizadas num troco). b) Escreva o pseudocódigo do algoritmo de Programação Dinâmica. Qual é complexidade do seu algoritmo? c) Seja d = { R$ 0,01; R$0,05; R$0,10; R$0,25; R$0,50; R$1,00; R$2,00; R$5,00; R$10,00; R$20,00; R$50,00; R$100,00}. Utilizando seu algoritmo, determine as soluções ótimas para X = 49,78, X = 995,39 e X = 3149,32 2) Solitaire é um jogo num tabuleiro n×n para um único jogador. Cada campo do tabuleiro possui um número inteiro. O jogador começa escolhendo algum campo do tabuleiro. Depois ele pode repetidamente mover 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. O valor do jogo é igual à soma dos campos (números) 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 2 começando da posição (2,3) com 9, indo para baixo, e depois para direita, baixo, direita(ou baixo) obtêm-se uma solução com valor: 9 – 3 – 5 + 2 + 0 = 3. a) Baseado em Programação Dinâmica, defina uma função recursiva para determinar o valor de uma solução (valor do melhor jogo). Sugestão: Calcule o valor máximo da solução partindo da posição (i, j), ∀i, j=1,..n. Inicie os cálculos a partir da posição (n, n). b) Utilize a função recursiva para obter a solução ótima do exemplo dado acima. c) Apresente o pseudocódigo do algoritmo de PD e determine a complexidade do seu algoritmo. 3) Seja uma sequencia de n números A = [a1, a2, ..., an]. Deseja-se determar a subsequencia crescente máxima, ou seja a subsequencia com o maior número de elementos ordenados de forma crescente. Exemplo: Se A = [5, 2, 8, 6, 3, 6, 9, 7], s = [2, 3, 6, 9] é uma subsequência crescente com 4 elementos. a) Baseado em Programação Dinâmica, escreva uma função recursiva para determinar o valor máximo de uma solução (número de elementos da subsequência). b) Escreva um algoritmo de programação dinâmica para resolver o problema. Qual é complexidade do seu algoritmo? c) Utilizando o algoritmo de PD determine a solução para a sequência x = [5, 2, 8, 6, 3, 6, 9, 7]. 4) Considere uma variante do problema de determinar a melhor agrupação para multiplicar uma sequência de n matrizes de modo a maximizar, em vez de minimizar, o número de multiplicações. Baseado em Programação Dinâmica, escreva uma função recursiva para determinar o número máximo de multiplicações. 5) Desenhe uma árvore binária de decisão para procurar um elemento numa lista ordenada com quatro elementos. 2 6) Seja S = {s1, s2,....,sn} uma sequência ordenada e considere o problema de inserir um novo elemento nesta sequência mantendo-a ordenada. Mostre que o limite inferior para este problema é Ω(logn). Mostre também que este limite é justo. 7) Mostre que o problema de determinar o mediana de um conjunto de n números pode ser reduzido ao problema de ordenação em tempo O(n). a) Ω(nlogn) é um limitante inferior do problema da mediana? b) Desenhe uma árvore de decisão para determinar o número de comparações, no pior caso, para resolver o problema da mediana considerando um conjunto com três elementos {a, b,c}. 8) Determine um limite inferior justo para o problema de encontrar os dois elementos com menor distância numa lista de n números {x1,x2,....,xn}. A distância entre dois números x e y é determinada por |x-y|. 9) Sejam P e Q dois problemas tais que P pode ser reduzido a Q em tempo linear (P ∝O(n) Q) e suponha que o limite inferior de P é Ω(n log n). Responda se cada uma das afirmações abaixo é verdadeira ou falsa. Justifique a sua resposta: a) O limite inferior de Q é Ω(n log n). b) Todo algoritmo que resolve P pode ser usado para resolver Q c) Todo algoritmo que resolve Q pode ser usado para resolver P d) O problema Q pode ser resolvido no pior caso em tempo O(n log n). e) Se Q é resolvido em tempo O(log n), então P também será resolvido em tempo O(log n). f) Um limite superior para P é O(f(n)), onde f(n) = o(n). 10) Sejam P1, P2 e P3 três problemas tais que P1 pode ser reduzido a P2 em tempo O(n) e P2 pode ser reduzido a P3 em tempo O(n2). Considerando estas suposições, responda se as afirmações abaixo são verdadeiras ou falsas, justificando as suas respostas: a) Se o limite inferior de P1 é Ω(n log n) então o limite inferior de P2 e de P3 também é Ω(n log n) b) Se P1 é NP-difícil e se existe um algoritmo não determinístico que resolve P3 em tempo polinomial então os problemas P1, P2 e P3 são NP-completos. c) Se o limite inferior de P1 é Ω(2n) e se P3 é NP-completo então P ≠ NP d) Se o problema SAT pode ser reduzido ao problema P2 em tempo polinomial e se existe um algoritmo (determinístico) que soluciona P3 em tempo polinomial então P = NP e) Se P3 é NP-completo então existem algoritmos determinísticos de complexidade O(n) que resolvem P1, P2 e P3. 11) Dado um problema P1 e um algoritmo A1 que soluciona P1, responda se as afirmações abaixo são verdadeiras ou falsas (justifique as suas respostas): a) Suponha que A1 tem complexidade θ(n2). Isto implica que o limite inferior do problema P1 é Ω(n2). b) Suponha que o limite inferior do problema P1 é Ω(n logn). Isto implica que A1 tem complexidade Ω(n log n). c) Suponha que A1 tem complexidades Ω(n log n) e O(n2) e suponha que o limite inferior do problema P1 é Ω(n log n). Isto implica que o limite inferior do problema P1 é justo. 12) Responda se as afirmações abaixo são verdadeiras ou falsas, justificando suas respostas: a) Para mostrar que um problema L é NP-difícil basta mostrar que L pode ser reduzido a outro problema conhecidamente em NP. b) Para mostrar que um problema L pertence a NP basta mostrar que existe um algoritmo não determinístico que o resolva. c) Todo problema NP-completo é NP-difícil. d) Todo problema NP-Difícil é NP-Completo e) Todo problema da classe P é NP f) Se X e Y são problemas NP-Completos, então XαpY e YαpX (αp = redução em tempo polinomial). g) Se XαpY e Y∈P então X∈P. h) Se X∈NP então Xαp SAT (problema de satisfabilidade). 3 i) Se XαpY, X∈NP-Dificil e Y∈NP, então Y∈NP-Completo. j) Sejam X, Y e Z três problemas tais que X pode ser reduzido a Y em tempo O(n) e Y pode ser reduzido a Z em tempo O(n2). Se o limite inferior de X é Ω(n log n) então o limite inferior de Y e de Z também é Ω(n log n). 13) Mostre que, se X é NP-Difícil e se X αp Y, então Y é NP-Difícil. 14) Quais dos seguintes diagramas não contradizem as definições sobre classes problemas P, NP e NP-Completo?. P = NP = NP-C P = NP NP-C NP P NP-C NP NP-C P NP NP-C P
Compartilhar