Buscar

Lista 3

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

Outros materiais