Análise de Algoritmos e Teoria da Complexidade

Projeto e Análise de Algoritmos Fátima Duarte Figueiredo fatimafigpucminasbr Pontifícia Universidade Católica de Minas Gerais Instituto de Ciências Exatas e Informática Departamento de Ciência da Computação Mestrado em Informática Projeto de Algoritmos Teoria da Complexidade Parte 3 Teoria da Complexidade 3 Introdução A maioria dos problemas conhecidos e estudados se divide em dois grupos Problemas cuja solução é limitada por um polinômio de grau pequeno Pesquisa binária Θlog n Ordenação Θn log n Problemas cujo melhor algoritmo conhecido é nãopolinomial Problema do Caixeiro Viajante Θn22n 4 Algoritmos Polinomiais X Algoritmos Exponenciais Algoritmos polinomiais são obtidos através de um entendimento mais profundo da estrutura do problema Um problema é considerado tratável quando existe um algoritmo polinomial para resolvêlo Algoritmos exponenciais são em geral simples variação de pesquisa exaustiva Um problema é considerado intratável se ele é tão difícil que não existe um algoritmo polinomial para resolvêlo 5 Algoritmos Polinomiais X Algoritmos Exponenciais Entretanto Um algoritmo Θ2n é mais rápido que um algoritmo Θ n5 para n 20 Existem algoritmos exponenciais que são muito úteis na prática Na prática os algoritmos polinomiais tendem a ter grau 2 ou 3 no máximo e não possuem coeficientes muito grandes n100 ou 1099n2 NÃO OCORREM Decisão x Otimização Em um problema de otimização queremos determinar uma solução possível com o melhor valor Em um problema de decisão queremos responder sim ou não Para cada problema de otimização podemos encontrar um problema de decisão equivalente a ele 7 Problemas SimNão ou Problemas de Decisão Para o estudo teórico da complexidade de algoritmos é conveniente considerar problemas cujo resultado seja sim ou não Exemplo Problema do Caixeiro Viajante Dados Um conjunto de cidades Cc1c2cn uma distância dcicj para cada par de cidades ci cj C e uma constante K Questão Existe um roteiro para todas as cidades em C cujo comprimento total seja menor ou igual a K 8 Classe P e NP Classe P Um algoritmo está na Classe P se a complexidade do seu pior caso é uma função polinomial do tamanho da entrada de dados Classe NP Classe de problemas SimNão para os quais uma dada solução pode ser verificada facilmente 9 Verificação de Ordenação está em NP Complexidade Θn VOrdenacaoAn inicio ordenado verdadeiro para i 1 até n1 faça se Ai Ai1 então ordenado falso fim se fim para se ordenado falso então escreva NAO senão escreva SIM fim se fim 10 Algoritmos Nãodeterministas Um algoritmo nãodeterminista é capaz de escolher uma dentre as várias alternativas possíveis a cada passo 11 Algoritmos Nãodeterministas Utilizam a função escolheC escolhe um dos elementos de C de forma arbitrária SUCESSO sinaliza uma computação com sucesso INSUCESSO sinaliza uma computação sem sucesso Sempre que existir um conjunto de opções que levam a um término com sucesso então este conjunto é sempre escolhido A complexidade da função escolhe é Θ1 12 Exemplo Pesquisa Pesquisar o elemento x em um conjunto de elementos A1n n 1 Complexidade Θ1 Para um algoritmo determinista a complexidade é Θn j escolheAx se Aj x então SUCESSO senão INSUCESSO fim se 13 Exemplo Ordenação Ordenar um conjunto A contendo n inteiros n 1 Complexidade do algoritmo nãodeterminista Θn Complexidade do algoritmo determinista Θn log n B contém o conjunto ordenado A posição correta em B de cada inteiro de A é obtida de forma nãodeterminista NDOrdenacao An inicio para i1 até n faça Bi0 para i1 até n faça inicio j escolheAi se Bj 0 então Bj Ai senão INSUCESSO fim se fim para SUCESSO fim 14 Algoritmos Deterministas X Algoritmos Nãodeterministas Classe P Polynomialtime Algorithms Conjunto de todos os problemas que podem ser resolvidos por algoritmos deterministas em tempo polinomial Classe NP Nondeterministic Polinomial Time Algorithms Conjunto de todos os problemas que podem ser resolvidos por algoritmos nãodeterministas em tempo polinomial 15 Como Mostrar que um Determinado Problema está em NP Basta apresentar um algoritmo nãodeterminista que execute em tempo polinomial para resolver o problema ou Basta encontrar um algoritmo determinista polinomial para verificar que uma dada solução é válida 16 Caixeiro Viajante está em NP Algoritmo nãodeterminista em tempo polinomial Complexidade do algoritmo nãodeterminista Θn Complexidade do algoritmo determinista Θn2 2n NDPCVGnk inicio Soma 0 para i 1 até n faça Ai escolheGn fim para An1 A1 para i 1 até n faça Soma Soma distancia entre Ai e Ai1 fim para se Soma k então SUCESSO senão INSUCESSO fim se fim 17 Caixeiro Viajante está em NP Algoritmo determinista polinomial para verificar a solução Complexidade Θn DPCVVGSnk inicio Soma 0 para i 1 até n faça Soma Soma distancia entre Si e Si1 se Soma k então escreva SIM senão escreva NAO fim 18 P NP ou P NP Como algoritmos deterministas são apenas um caso especial de algoritmos nãodeterministas podemos concluir que P NP O que não sabemos é se P NP ou P NP Será que existem algoritmos polinomiais deterministas para todos os problemas em NP Por outro lado a prova de que P NP parece exigir técnicas ainda desconhecidas 19 Descrição tentativa de NP P está contida em NP Acreditase que NP seja muito maior que P 20 Consequências Existem muitos problemas práticos em NP que podem ou não pertencer a P não conhecemos nenhum algoritmo eficiente que execute em uma máquina determinista Se conseguirmos provar que um problema não pertence a P então não precisamos procurar por uma solução eficiente para ele Como não existe tal prova sempre há esperança de que alguém descubra um algoritmo eficiente Quase ninguém acredita que NP P Existe um esforço considerável para provar o contrário MAS O PROBLEMA CONTINUA EM ABERTO 21 Redução Polinomial Sejam 1 e 2 dois problemas simnão Suponha que exista um algoritmo A2 para resolver 2 Se for possível transformar 1 em 2 e sendo conhecido um processo de transformar a solução de 2 numa solução de 1 então o algoritmo A2 pode ser utilizado para resolver 1 Se estas duas transformações puderem ser realizadas em tempo polinomial então 1 é polinomialmente redutível a 2 1 2 22 Exemplo de Transformação Polinomial Conjunto independente de vértices V V tal que todo par de vértices de V é não adjacente ou seja se vw V vw E a c b g é um exemplo de um conjunto independente de cardinalidade 4 Clique V V tal que todo par de vértices de V é adjacente V é um subgrafo completo ou seja se vw V vw E d b e é um exemplo de um clique de cardinalidade 3 a c d b g f e GVE 23 Exemplo de Transformação Polinomial Instância I do Clique Dados Grafo GVE e um inteiro K 0 Decisão G possui um clique de tamanho k Instância fI do Conjunto Independente Considere o grafo complementar de G e o mesmo inteiro K f é uma transformação polinomial porque 1 pode ser obtido a partir de G em tempo polinomial 2 G possui clique de tamanho k se e somente se possui conjunto independente de vértices de tamanho k 24 Se existir um algoritmo que resolva o conjunto independente em tempo polinomial este algoritmo pode ser utilizado para resolver o clique também em tempo polinomial Exemplo de Transformação Polinomial Clique Conjunto Independente 25 Satisfabilidade Definir se uma expressão booleana E contendo produto de adições de variáveis booleanas é satisfatível Exemplo onde representa variáveis lógicas representa OR representa AND representa NOT Problema Existe uma atribuição de valores lógicos V ou F às variáveis que torne a expressão verdadeira satisfaça x1F x2V x3V Satisfaz Exemplo não é satisfatível 26 Satisfabilidade O algoritmo obtém uma das 2n atribuições possíveis de forma nãodeterminista em On NDAvalEn inicio para i1 até n faça xi escolhetruefalse se Ex1x2xn true então SUCESSO senão INSUCESSO fim se fim SAT NP 27 Teorema de Cook S Cook formulou a seguinte questão em 1971 existe algum problema em NP tal que se ele for mostrado estar em P então este fato implicaria que PNP Teorema de Cook Satisfabilidade está em P se e somente se P NP Isto é Se existe um algoritmo polinomial determinista para a satisfabilidade então todos os problemas em NP poderiam ser resolvidos em tempo polinomial 28 Teorema de Cook SAT está em P se P NP Esboço da prova 1 SAT está em NP Logo se P NP então SAT está em P 2 Se SAT está em P então P NP Prova descreve como obter de qualquer algoritmo polinomial não determinista de decisão A com entrada E uma fórmula QAE de forma que Q é satisfatível se e somente se A termina com sucesso para a entrada E Isto significa que ele mostrou que para qualquer problema NP SAT 29 NPCompleto Um problema de decisão é denominado NPCompleto se 1 NP 2 Todo problema de decisão NP satisfaz Apenas problemas de decisão simnão podem ser NPCompleto 30 Como Provar que um Problema é NPCompleto 1 Mostre que o problema está em NP 2 Mostre que um problema NPCompleto conhecido pode ser polinomialmente transformado para ele Porque Cook apresentou uma prova direta de que SAT é NPCompleto Transitividade da redução polinomial SAT 1 e 1 2 SAT 2 31 Descrição tentativa de NP Se alguém encontrar um algoritmo polinomial que resolva algum problema NPCompleto então todos os problemas em NP também terão solução polinomial ou seja P será igual a NP Se alguém provar que um determinado problema em NP não tem solução polinomial então todos os problemas em NPCompleto também não terão solução polinomial ou seja P será diferente de NP Assumindo que P NP 32 Qual é a Contribuição Prática da Teoria de NPCompleto Fornece um mecanismo que permite descobrir se um novo problema é fácil ou difícil Se encontrarmos um algoritmo eficiente para o problema então não há dificuldades Senão uma prova de que o problema é NPCompleto nos diz que se acharmos um algoritmo eficiente então estaremos obtendo um grande resultado Como Resolver Problemas NPcompletos Quando não existe solução polinomial é necessário usar algoritmos aproximados ou heurísticas que não garantem a solução ótima mas são rápidos Algoritmos Aproximados e Heurísticas Algoritmos aproximados Algoritmos usados normalmente para resolver problemas para os quais não se conhece uma solução polinomial Devem executar em tempo polinomial dentro de limites prováveis de qualidade absoluta ou assintótica Heurísticas Algoritmos que têm como objetivo fornecer soluções sem um limite formal de qualidade em geral avaliado empiricamente em termos de complexidade média e qualidade de soluções É projetada para obter ganho computacional ou simplicidade conceitual possivelmente ao custo de precisão 34