NÃO NÃO DETERMINISMODETERMINISMO

Curso de Ciência da Computação da Universidade Federal de Pernambuco

Disciplina de Algoritmos e Estruturas de Dados

Recife, 10 de setembro de 1998

Apresentação:

Paulo Gustavo Fell Amado (pgfa@di.ufpe.br) e

Marcus Eduardo Cabral Seabra (mecs@di.ufpe.br)

VISÃO GERAL DA VISÃO GERAL DA APRESENTAÇÃOAPRESENTAÇÃO

INTRODUÇÃO - expressões e convençõesINTRODUÇÃO - expressões e convenções ALGORITMOS DETERMINÍSTICOS E NÃO DETERMINÍSTICOS - ALGORITMOS DETERMINÍSTICOS E NÃO DETERMINÍSTICOS -

Conceitos e comparaçõesConceitos e comparações ESCOLHA NÃO DETERMINÍSTICA - Conceito e aplicaçãoESCOLHA NÃO DETERMINÍSTICA - Conceito e aplicação PROBLEMAS P E NP - Conceito e confrontamentoPROBLEMAS P E NP - Conceito e confrontamento PROBLEMAS NP-DIFÍCEIS E NP-COMPLETOSPROBLEMAS NP-DIFÍCEIS E NP-COMPLETOS APRESENTAÇÃO DE UM PROBLEMA NP-COMLETOAPRESENTAÇÃO DE UM PROBLEMA NP-COMLETO APLICAÇÕES DE NÃO DETERMINISMO EM CIÊNCIA DA APLICAÇÕES DE NÃO DETERMINISMO EM CIÊNCIA DA

COMPUTAÇÃOCOMPUTAÇÃO NÃO DETERMINISMO NA INTERNETNÃO DETERMINISMO NA INTERNET CONCLUSÃOCONCLUSÃO

INTRODUÇÃOINTRODUÇÃO

Existem muitos problemas para os quais não se Existem muitos problemas para os quais não se conhece solução eficiente e para muitos não sabemos conhece solução eficiente e para muitos não sabemos nem ao menos dizer se existe esta solução. Estes nem ao menos dizer se existe esta solução. Estes problemas são bastante comuns.problemas são bastante comuns.

Problemas Algorítmicos:Problemas Algorítmicos:– existe estrutura S que satisfaça propriedades P ? (Decisão)existe estrutura S que satisfaça propriedades P ? (Decisão)– encontre estrutura S que satisfaça propriedades Pencontre estrutura S que satisfaça propriedades P– encontre estrutura S que satisfaça os critérios de otimizaçãoencontre estrutura S que satisfaça os critérios de otimização

INTRODUÇÃOINTRODUÇÃO

Algoritmos que possuem resolução em tempo Algoritmos que possuem resolução em tempo polinomial* são chamados de polinomial* são chamados de Algoritmos eficientesAlgoritmos eficientes e dizemos que este é um e dizemos que este é um problema tratávelproblema tratável..

*Tempo de execução polinomial:*Tempo de execução polinomial:– funciona para n’s grandes;funciona para n’s grandes;– no dia-a-dia nos deparamos na grande maioria das vezes no dia-a-dia nos deparamos na grande maioria das vezes

com problemas com tempo de execução O(n), O(n²);com problemas com tempo de execução O(n), O(n²);– da mesma forma, por conveniência, assumimos que O(nlogn) da mesma forma, por conveniência, assumimos que O(nlogn)

é um tempo de execução polinomial.é um tempo de execução polinomial.

ALGORITMOS DETERMINÍSTICOSALGORITMOS DETERMINÍSTICOS××

ALGORITMOS NÃO ALGORITMOS NÃO DETERMINÍSTICOSDETERMINÍSTICOS

Algoritmo Determinístico:Algoritmo Determinístico:– a qualquer momento da sua lista de operações, o a qualquer momento da sua lista de operações, o

algoritmo só tem um próximo passo predeterminado algoritmo só tem um próximo passo predeterminado a ser tomado;a ser tomado;

– se aplicarmos um algoritmo determinístico duas se aplicarmos um algoritmo determinístico duas vezes ao mesmo problema, teremos duas soluções vezes ao mesmo problema, teremos duas soluções idênticas;idênticas;

– são os algoritmos encontrados na vida prática.são os algoritmos encontrados na vida prática.

ALGORITMOS DETERMINÍSTICOSALGORITMOS DETERMINÍSTICOS××

ALGORITMOS NÃO ALGORITMOS NÃO DETERMINÍSTICOSDETERMINÍSTICOS

Não determinismo: qualidade de uma Não determinismo: qualidade de uma computação que pode apresentar mais de um computação que pode apresentar mais de um resultado.resultado.

Algoritmo Não Determinístico:Algoritmo Não Determinístico:– teremos mais de um próximo passo a ser tomado, o teremos mais de um próximo passo a ser tomado, o

passo correto será apontado por uma ferramenta (não passo correto será apontado por uma ferramenta (não implementável), para cada escolha o algoritmo tomará implementável), para cada escolha o algoritmo tomará rumos diferentes;rumos diferentes;

– esta ferramenta é a esta ferramenta é a escolha não determinísticaescolha não determinística que que vamos chamar de nd-choice.vamos chamar de nd-choice.

ESCOLHA NÃO ESCOLHA NÃO DETERMINÍSTICADETERMINÍSTICA

Quando se deparar com várias opções, o nd-Quando se deparar com várias opções, o nd-choice munirá nosso algoritmo com o poder de choice munirá nosso algoritmo com o poder de fazer a escolha certa, de “adivinhar” o fazer a escolha certa, de “adivinhar” o caminho que possui a solução se ela existir.caminho que possui a solução se ela existir.

O algoritmo seguirá os passos determinísticos O algoritmo seguirá os passos determinísticos normais e intercalará um ou mais usos do nd-normais e intercalará um ou mais usos do nd-choice, de forma a achar pelo menos uma das choice, de forma a achar pelo menos uma das entradas para as quais a resposta ao problema entradas para as quais a resposta ao problema de decisão é SIM e rejeitar todas para as quais de decisão é SIM e rejeitar todas para as quais a resposta é NÃO.a resposta é NÃO.

PROBLEMAS P e PROBLEMAS PROBLEMAS P e PROBLEMAS NPNP

Classe P:Classe P:– Dizemos que um problema pertence à Classe P se Dizemos que um problema pertence à Classe P se

ele puder ser resolvido por um algoritmo ele puder ser resolvido por um algoritmo determinístico em tempo polinomial; determinístico em tempo polinomial;

– É a classe de todos os problemas que podem ser É a classe de todos os problemas que podem ser resolvidos por um algoritmo eficiente.resolvidos por um algoritmo eficiente.

Classe NP:Classe NP:– Quando, para resolver um problema, temos um Quando, para resolver um problema, temos um

algoritmo algoritmo NNão determinístico (usa nd-choice) que ão determinístico (usa nd-choice) que

roda em tempo roda em tempo PPolinomial dizemos que o problema olinomial dizemos que o problema pertence à classe NP.pertence à classe NP.

PROBLEMAS P e PROBLEMAS PROBLEMAS P e PROBLEMAS NPNP

Temos direto da definição que: P Temos direto da definição que: P NP NP

É intuitivo também dizer que: se um problema de decisão É intuitivo também dizer que: se um problema de decisão é NP, então uma resposta SIM ou NÃO para o problema é NP, então uma resposta SIM ou NÃO para o problema pode ser obtida no máximo em tempo exponencial.pode ser obtida no máximo em tempo exponencial.

Nunca foi provado que P=NP, para tanto teríamos que Nunca foi provado que P=NP, para tanto teríamos que mostrar que todo problema em NP pode ser resolvido por mostrar que todo problema em NP pode ser resolvido por um algoritmo determinístico em tempo polinomial. Para um algoritmo determinístico em tempo polinomial. Para provar o contrário, ou seja, que Pprovar o contrário, ou seja, que PNP, teríamos que provar NP, teríamos que provar que dentre todos os algoritmos que resolvem um que dentre todos os algoritmos que resolvem um problema NP nenhum é eficiente. Esta questão continua problema NP nenhum é eficiente. Esta questão continua uma grande incógnita para muitos pesquisadores e é uma grande incógnita para muitos pesquisadores e é chamada de chamada de Problema P=?NPProblema P=?NP..

REDUÇÃO POLINOMIALREDUÇÃO POLINOMIAL Seja L Seja L U o conjunto de todas as entradas de um problema de U o conjunto de todas as entradas de um problema de

decisão cujas respostas são SIM. O problema de decisão é decisão cujas respostas são SIM. O problema de decisão é reconhecer se uma determinada entrada pertence a L. Sejam reconhecer se uma determinada entrada pertence a L. Sejam L1 e L2 dois problemas com entradas nos espaço U1 e U2, L1 e L2 dois problemas com entradas nos espaço U1 e U2, dizemos que L1 é polinomialmente redutível a L2 se existe um dizemos que L1 é polinomialmente redutível a L2 se existe um algoritmo em tempo polinomial que converte cada entrada algoritmo em tempo polinomial que converte cada entrada u1u1 U1 em outra U1 em outra u2u2 U2, tal que U2, tal que u1u1 S1 se e somente se S1 se e somente se u2u2 S2.S2.

Se L1 é redutível a L2 e existe um algoritmo em tempo Se L1 é redutível a L2 e existe um algoritmo em tempo polinomial para L2 então existe um algoritmo polinomial para polinomial para L2 então existe um algoritmo polinomial para L1.L1.

Quando L1 é redutível a L2, temos que L2 é mais difícil que L1.Quando L1 é redutível a L2, temos que L2 é mais difícil que L1.

Se L1 é redutível a L2 e L2 é redutível a L3, então L1 é redutível Se L1 é redutível a L2 e L2 é redutível a L3, então L1 é redutível a L3a L3

NP-DIFÍCIL e NP-NP-DIFÍCIL e NP-COMPLETOCOMPLETO

NP-DifícilNP-Difícil– Um problema X é chamado de NP-Difícil se todos os Um problema X é chamado de NP-Difícil se todos os

problemas da classe NP forem redutíveis a X.problemas da classe NP forem redutíveis a X.– Resolver um problema NP-Difícil em tempo Resolver um problema NP-Difícil em tempo

polinomial tornaria possível resolver todos os polinomial tornaria possível resolver todos os problemas em NP em tempo polinomial.problemas em NP em tempo polinomial.

NP-CompletoNP-Completo– Um problema X é chamado de NP-Completo se (1) Um problema X é chamado de NP-Completo se (1)

pertencer a NP e (2) for NP-Difícil.pertencer a NP e (2) for NP-Difícil.– Um problema X é NP-Completo se Y é redutível a X Um problema X é NP-Completo se Y é redutível a X

para algum problema Y que seja NP-Completo para algum problema Y que seja NP-Completo (transitividade).(transitividade).

TEOREMA DE COOKTEOREMA DE COOK

Em 1971, Stephen A. Cook Em 1971, Stephen A. Cook introduziu o conceito de NP-introduziu o conceito de NP-Completo, provando que o problema Completo, provando que o problema da satisfatibilidade (SAT) pertencia a da satisfatibilidade (SAT) pertencia a esta classe.esta classe.

Para contactar Cook, mande um Para contactar Cook, mande um mail para: sacook@cs.toronto.camail para: sacook@cs.toronto.ca

TEOREMA DE COOK:TEOREMA DE COOK:

O problema SAT é NP-Completo.O problema SAT é NP-Completo.

Com o teorema de Cook, vários outros problemas Com o teorema de Cook, vários outros problemas foram provados pertencer à classe NP-Completo, esses foram provados pertencer à classe NP-Completo, esses problemas possuem uma extrema importância, por existirem problemas possuem uma extrema importância, por existirem em grande número e terem muitas aplicações práticas. No em grande número e terem muitas aplicações práticas. No esquema são representados outros problemas NP-Completos esquema são representados outros problemas NP-Completos ligados numa árvore diretamente ao problema ao qual são ligados numa árvore diretamente ao problema ao qual são redutíveis.redutíveis.

SAT

CLIQUE

COBERTURA DE

VÉRTICES

CICLO HAMILTONIANO

CAIXEIRO VIAJANTE

3SAT

3COLORAÇÃO

MATCHING

TRIDIMENSIONAL

PARTIÇÃO

Problemas NPProblemas NP

Para identificar um problema NP, Para identificar um problema NP, usamos um algoritmo não usamos um algoritmo não determinístico determinístico

O custo do algoritmo torna-se O custo do algoritmo torna-se polinomial polinomial

Algoritmos não-Algoritmos não-determinísticosdeterminísticos

Comandos regulares das Comandos regulares das linguagens determinísticaslinguagens determinísticas

nd-choice -> oráculond-choice -> oráculo

ReconhecimentoReconhecimento

Um algoritmo não-Um algoritmo não-determinístico reconhece determinístico reconhece

(aceita, diz sim) uma (aceita, diz sim) uma entrada x se existir, pelo entrada x se existir, pelo menos, uma maneira do menos, uma maneira do algoritmo chegar a uma algoritmo chegar a uma

resposta simresposta sim.

O PROBLEMA CLIQUEO PROBLEMA CLIQUE

Dado um grafo G(V,E) e um Dado um grafo G(V,E) e um inteiro k <= |v|, existe um inteiro k <= |v|, existe um

subgrafo completo de k subgrafo completo de k vértices de G?vértices de G?

Algoritmo não-determinístico para Algoritmo não-determinístico para CliqueClique

Para v:= 1 até n Para v:= 1 até n

nd-choice {nd-choice {

escolhido[v] := 1;escolhido[v] := 1;

escolhido[v] := 0; }escolhido[v] := 0; }

cont := 0;cont := 0;

para v:= 1 ate npara v:= 1 ate n

cont := cont + escolhido[v];cont := cont + escolhido[v];

se cont != k {se cont != k {

imprima “não existe”imprima “não existe”

exit }exit }

Para v:= 1 até n {Para v:= 1 até n {

se escolhido[v] := 1 se escolhido[v] := 1

cont:= 0;cont:= 0;

para cada vertice w adjacenta a v para cada vertice w adjacenta a v { {

cont := 0;cont := 0;

se escolhido[w] = 1se escolhido[w] = 1

cont := cont + 1;cont := cont + 1;

se cont != k - 1se cont != k - 1

imprima “não imprima “não existeexiste

exit }}exit }}

imprima “existe”imprima “existe”

Não determinismo em Não determinismo em Ciências da ComputaçãoCiências da Computação

Inteligência ArtificialInteligência Artificial

Prolog - Lógica de 1ª ordemProlog - Lógica de 1ª ordem

ConcorrênciaConcorrência

Linguagens (semântica)Linguagens (semântica)

Não determinismo na WebNão determinismo na Web

CONCLUSÕESCONCLUSÕES

Como lidar com os problemas não Como lidar com os problemas não determinísticosdeterminísticos– Trabalhar com o caso médio desenvolvendo Trabalhar com o caso médio desenvolvendo

algoritmos que solucionam a maioria dos casosalgoritmos que solucionam a maioria dos casos– Tentar algoritmos exponenciais tão eficientes quanto Tentar algoritmos exponenciais tão eficientes quanto

possível forpossível for– Algoritmos de AproximaçãoAlgoritmos de Aproximação

Projeto QuantumProjeto Quantum