Análise e Complexidade de AlgoritmosUma visão de Intratabilidade, Classes P e NP- redução polinomial- NP-completos e NP-difíceis

http://www.bolinhabolinha.comProf. Rodrigo Rochaprof.rodrigorocha@yahoo.com

Onde Estamos Ementa

• Revisão:Estrutura de dados;Crescimento de funções; Indução matemática e métodos matemáticos.

Medidas de complexidade, análise assintótica de limites de complexidades.

Exemplos de análise de algoritmo iterativos e recursivos. Análise de desempenho de alguns algoritmos clássicos de

busca e ordenação. Introdução aos principais paradigmas do projeto de

algoritmos. Complexidade do Problema: Limites de Complexidade,

Intratabilidade, Classes P, NP, problemas Np completos e NP-difíceis.

Introdução

P vs NP Relativamente fácil compreender o que diz o

problema É possível que seja resolvido com “um boa

idéia”• sem muito conhecimento técnico em matemática

Complexidade na maioria dos problemas• Polinomial ou exponencialEx: pesquisa binária (O(log n)), pesquisa sequencial

(O(n)), ordenação por inserção (O(n2)), e multiplicação de matrizes (O(n3)).

Algumas Definições

Classe dos problemas problemas

• - uma descrição genérica de todos os seus parâmetros;• - especificação das propriedades que a resposta ou solução deve satisfazer.

3 gêneros de problemas• decisão

Saída simples (sim/não) Exemplo:

– Cobertura de vértices de um grafo G = < V, E > é um subconjunto V' ⊆ V tal que toda aresta de E tenha pelo menos uma extremidade em V'.

• localização exige a exibição de uma solução, envolve a procura de um elemento que satisfaça a condição de solução, Exemplo:

• otimização problemas de localização que satisfaçam propriedades de otimização além de mostrar a solução exige que maximize ou minimize algum critério. Seja ótimo

.

Um algoritmo que resolve um problema de localização ou de otimização pode ser modificado para resolver o problema de decisão associado, praticamente sem esforço extra.

Por isso questões como intratabilidade são estudadas no âmbito dos problemas de decisão (que são mais simples).

Assim, as mais importantes classes de problemas, P, NP e NP-completa, são definidas para problemas de decisão.

Para expressar precisamente o requisito de tempo, é preciso ter o cuidado de definir o tamanho da entrada de maneira a levar em conta esses fatores.

O tamanho da entrada de uma instância x de um problema Π é definido como o número de símbolos na descrição de x obtido em um esquema de codificação do problema Π.

Um algoritmo é polinomial sse sua complexidade é de tempo polinomial: Ο( p( n ) ), onde p( n ) é um polinômio, e n representa o tamanho da entrada.

Algoritmos não determinísticos Determinísticos

• resolvem o problema com uma decisão exata a cada passo

Não Determinísticos• Algoritmos teóricos• duas fases

não determinística– geração de dados aleatórios

determinística– algoritmo lê os dados gerados– testa– pode acontecer

» parar com a resposta SIM» para com a resposta NÃO» não parar

Exemplo

Tipos de problemas

Tratáveis• podem ser resolvidos em tempo polinomial

Intratáveis / Difícil• nenhum algoritmo polinomial pode resolvê-lo

Problema algoritmo• Dados• Objetivo• Solução

Caixeiro-viajante Imagine que você é um vendedor sediado em Jundiaí

e tem que ir de carro a outras três cidades Campinas, São Paulo e Ribeirão Preto. Começando e terminando em Jundiaí. Para economizar gasolina e tempo, você deve planejar o trajeto, de forma que a distância percorrida seja mínima.

Jundiaí Campinas SP Rib PretoJundiaí 0 54 17 79

Campinas 54 0 49 104SP 17 49 0 91

Rib. Preto 79 109 91 0

Caixeiro-viajante

Rota Km TotaisJ-C-S-R-JJ-C-R-S-JJ-S-R-C-JJ-S-C-R-JJ-R-C-S-JJ-R-S-C-J

54+49+91+79=27354+104+91+17=26617+91+109+54=27117+49+107+79=24979+109+49+17=25479+91+49+54=273

Caixeiro-viajante

Para 3 cidades• 3 x 2 x 1 = 6três possibilidades, depois duas, depois uma

• E para 10 Cidades10x9x8x7x6x5x4x3x2x1=3.628.800 =10!Levando 1 minuto para calcular cada rota

trabalhando 8h/dia 5 dias 52 semanas por ano=por ano 2080*60 minutos = 124.8003628800/124800 = 29 ... Mais de 20 anos

Introdução Existem problemas computacionais muito difíceis de serem

resolvidos, ou resolvidos em um tempo satisfatório Estudamos as complexidades polinomiais, isto é, pior caso =

O(ne) Algoritmos que não são polinomiais são considerados

exponenciais• exemplo: 2n, 5n

Classes de Complexidade P

• problemas são resolvidos em tempo polinomial NP

• problemas não deterministicamente polinomial• são verificáveis em tempo polinomial

• conjunto de problemas que podem ser resolvidos em tempo polinomial em um computador não determinístico

• são semelhantes a algoritmos que são resolvidos com algoritmos polinomiais

• não foi provado que não existe algoritmo polinomial que o resolva

NP Completos• Os chamados problemas NP-completos são problemas que têm a

questão da complexidade ou tratabilidade não resolvida, pois não se sabe se existe ou não algoritmo polinomial que o resolva.

• é o subconjunto dos "mais difíceis" problemas não-determinísticos polinomiais

• Há dois fatos a considerar: - por um lado, sabe-se que se um problema NP-completo qualquer tiver

um algoritmo polinomial que o resolva então todos os problemas NP-completos (centenas ou milhares) também possuirão algoritmos polinomiais;

- por outro lado, nenhum algoritmo polinomial para esses problemas foi desenvolvido até o momento.

P NP-completo

NP

Stephen Cook• Completude NP• Se a descoberta de um procedimento em tempo

polinomial para sua solução implicar que todos os outros problemas NP podem ser resolvidos por um programa em tempo polinomial.

Discussão do problema aberta em computação NP contém P, mas não se sabe se NP = P

• Vale U$ 1.000.000,00Oferecido pelo milionário americano Landon Clay,

Exemplo clássicos NP completo

Caixeiro Viajante: existe um ciclo que percorra todos os vértices do grafo com um custo ≤ B?

Coloração de Grafos: pode um grafo ser adequadamente colorido com n cores?• Vértices adjacentes com cores diferentes

Mochila: existe uma combinação de itens que dê um lucro ≥ L, respeitando o limite de peso?

Exemplo clássicos NP completo Cobertura de Arestas e Vértices

Ciclo Hamilton• Caminho que passa por todos os vértices uma única vez e

retorna ao vértice inicial.

Clique do Grafo• Toda vértice v´ é adjacente a um grafo completo

Satisfabilidade (SAT)• Verificar se uma expressão pode ser satisfeita

consiste em se verificar se existe alguma forma de se atribuir valores V ou F para as variáveis, de tal forma que a expressão seja verdadeira.

Problema da Parada• Determinar, para um algoritmo determinístico

qualquer A com entrada de dados E, se o algoritmo A termina (ou entra em um loop infinito).

Redução Polinomial

A reduz polinomialmente ao problema B se existir um algoritmo para resolver A que utiliza um número polinomial de vezes um algoritmo para resolver B

BA R→

⇒→

⇒→

⇒→

BA

BA

BA

R

R

R

∃ alg. pol. B∃ algoritmo polinomial para A

∃ algoritmo polinomial para B∃ alg. pol. A

∃ alg. pol. B???

Animações na web

Caixeiro viajante• http://web.telia.com/~u85905224/tsp/TSP.htm

Game• http://www.tsp.gatech.edu/games/tspOnePlayer.ht

ml• http://www-m9.ma.tum.de/dm/java-applets/tsp-

usa-spiel/tsp.html