Limites Inferiores e NP-Completude em Algoritmos

Prévia do material em texto

DCC001 - Ana´lis e Projeto de Algoritmos
Departamento de Cieˆncia da Computac¸a˜o DCC - UFJF
Professor: Leonardo Vieira dos Santos Reis e-mail:lvsreis@ice.ufjf.br
Lista de Exercic´ıos – Limites Inferiores e NP-Completude
1. Considere duas sequeˆncias ordenadas com n elementos cada. Escreva um algoritmo o´timo para
intercalar estas duas sequeˆncias (obs.: voceˆ tem que mostrar que o seu algoritmo e´ o´timo, i.e., que
a complexidade de pior caso e´ a mesma do limite inferior do problema).
2. Dada uma sequeˆncia S = s1, s2, . . . , sn, considere o problema de determinar se esta sequeˆncia esta´
ordenada ou na˜o. Obtenha um limite inferior justo para o nu´mero de comparac¸o˜es necessa´rias para
se resolver este problema.
3. Sabendo que o limite inferior do problema de obter o menor e o segundo menor elemento de uma
sequeˆncia (na˜o ordenada) e´ n + log n− 2 comparac¸o˜es, mostre que esse limite e´ justo.
4. Seja um conjunto S com n nu´meros reais. Sabendo que o nu´mero mı´nimo de comparac¸o˜es para
determinar se todos os elementos de S sa˜o distintos e´ Ω(n log n), apresente um algoritmo o´timo para
esse problema.
5. Seja M(n) o tempo mı´nimo necessa´rio para multiplicar duas matrizes de dimenso˜es n×n, e seja S(n)
o tempo mı´nimo necessa´rio para computar o quadrado de uma matriz de dimensa˜o n × n. Mostre
que M(n) = Θ(S(n)), i.e., mostre que a operac¸a˜o de elevar ao quadrado uma matriz de dimensa˜o
n× n tem a mesma dificuldade que a operac¸a˜o de multiplicar duas matrizes de dimenso˜es n× n.
6. Mostre que o limite inferior para o problema de inverter uma matriz triangular inferior de dimensa˜o
n× n e´ igual ao limite inferior de multiplicar duas matrizes de dimenso˜es n× n.
7. Sejam P e Q dois problemas tais que P pode ser reduzido a Q em tempo linear. Suponha que o
limite inferior de P e´ Ω(n log n). Responda se cada uma das afirmac¸o˜es abaixo e´ verdadeira ou falsa,
justificando a sua resposta:
(a) O limite inferior de Q e´ Ω(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).
8. Seja uma sequeˆncia ordenada e considere o problema de inserir um novo elemento nesta sequeˆncia
mantendo-a ordenada:
(a) Mostre que o limite inferior para este problema e´ Ω(n log n);
(b) Mostre que esse limite e´ justo.
9. Responda se as afirmac¸o˜es abaixo sa˜o verdadeiras ou falsas. Justifique sua resposta.
(a) P ⊆ NP;
(b) Para mostrar que um problema L e´ NP-completo basta mostrar que L pode ser reduzido a um
outro problema conhecidamente em NP-Completo;
(c) Para mostrar que um problema L esta´ em NP basta mostrar que existe um algoritmo na˜o-
determin´ıstico que o resolve;
(d) Todo problema NP-Completo tambe´m e´ NP.
10. Dado um problema P1 e um algoritmo A1 que soluciona P1, responda se as afirmac¸o˜es a seguir sa˜o
verdadeiras ou falsa, justificando sua resposta:
(a) suponha que A1 tem complexidade O(n
2). Isto implica que o limite inferior de de P1 e´ Ω(n
2)?
(b) supondo que o limite inferior de P1 e´ Ω(n log n), enta˜o A1 tem complexidade Ω(n log n)?
(c) supondo que A1 tem complexidade Ω(n log n) e O(n
2) e que o limite inferior do problema P1 e´
Ω(n log n). Podemos afirmar que o algoritmo A1 e´ o´timo?
11. Dada uma sequeˆncia com n nu´meros inteiros, seja P1 o problema de ordenar a sequeˆncia e seja P2 o
problema de encontrar o maior elemento da sequeˆncia. Considere a reduc¸a˜o do problema P1 em P2:
1
DCC001 - Ana´lis e Projeto de Algoritmos
Departamento de Cieˆncia da Computac¸a˜o DCC - UFJF
Professor: Leonardo Vieira dos Santos Reis e-mail:lvsreis@ice.ufjf.br
Lista de Exercic´ıos – Limites Inferiores e NP-Completude
Seja A2 um algoritmo que resolve P2. O problema P1 pode ser reduzido ao problema P2
em tempo linear da seguinte forma:
(a) dada uma sequeˆncia S que se deseja ordenar, passe-a para o algoritmo A2
(b) aplique o algoritmo A2 a` sequeˆncia S para obter o maior elemento da sequeˆncia
(c) troque de posic¸a˜o na sequeˆncia o maior elemento obtido acima com o u´ltimo elemento
da sequeˆncia
(d) repita os passos acima n− 1 vezes
Visto que o passo (a) e´ O(1) e que os passos (c) e (d) sa˜o O(n), enta˜o o problema P1 pode
ser reduzido a P2 em tempo linear. Portanto, como o problema P1 (ordenac¸a˜o) tem limite
inferior Ω(n log n), o limite inferior de P2 tambe´m e´ Ω(n log n).
A demonstrac¸a˜o que o limite inferior do problema P2 e´ Ω(n log n) esta´ correta? Justifique.
12. Sejam P1, P2 e P3 treˆs problemas tais que P1 pode ser reduzido a P2 em tempo O(n) e P2 pode ser
reduzido a P3 em tempo O(n
2). Considerando estas suposic¸o˜es, responda se as afirmac¸o˜es abaixo
sa˜o verdadeiras ou falsas e justifique sua resposta:
(a) se o limite inferior de P1 e´ Ω(n log n), enta˜o o limite inferior de P2 e P3 tambe´m e´ Ω(n log n);
(b) se P1 e´ um problema NP-Completo, enta˜o P2 e P3 tambe´m sa˜o NP-Completos;
(c) se o limite inferior de P1 e´ Ω(2
n) e P3 e´ NP-Completo, enta˜o P 6= NP;
(d) se o problema SAT pode ser reduzido ao problema P2 em tempo polinomial e existe um algoritmo
determin´ıstico que soluciona P3 em tempo polinomial, enta˜o P = NP;
(e) se P3 e´ NP-Completo, enta˜o existem algoritmos determin´ısticos de complexidade polinomial que
resolvem P1 e P2.
13. Sabendo que existe reduc¸a˜o polinomial do problema da satisfatibilidade (SAT) para o problema Q,
considere as seguintes afirmac¸o˜es:
1. Q pertence a classe de problemas P;
2. Q pertence a classe de problemas NP;
3. Q pertence a classe de problemas NP-Completos;
4. P = NP.
Considerando cada uma das suposic¸o˜es a seguir, indique quais dessas afirmac¸o˜es sa˜o verdadeiras,
falsas ou que na˜o ha´ argumentos suficientes para decidir:
(a) suponha que voceˆ conseguiu elaborar um algoritmo determin´ıstico de complexidade polinomial
que soluciona o problema Q;
(b) suponha que voceˆ conseguiu elaborar um algoritmo na˜o-determin´ıstico de complexidade polino-
mial que soluciona o problema Q;
(c) suponha que voceˆ conseguiu mostrar que o limite inferior do problema Q e´ Ω(2n).
14. Sejam os problemas P1 e P2 assim enunciados:
• Problema P1: Dado um grafo G = (V,E) e um inteiro positivo K, determinar se existe um
subconjunto S ⊆ V cujo tamanho seja no mı´nimo K de modo que para quaisquer elementos,
u ∈ S e v ∈ S, na˜o exista arestas entre eles, ou seja (u, v) /∈ E;
• Problema P2: Dado um grafo G = (V,E) e um inteiro positivo K, determinar se existe um
subconjunto S ⊆ V cujo tamanho seja no mı´nimo K de modo que para quaisquer elementos,
u ∈ S e v ∈ S, exista arestas entre eles, ou seja (u, v) ∈ E;
Sabendo que o problema P1 e´ um problema NP-Completo, mostre que o problema P2 tambe´m e´ um
problema NP-Completo.
2