NÃO DETERMINISMO
Apresentação:
Paulo Gustavo Fell Amado ([email protected]) e
Marcus Eduardo Cabral Seabra ([email protected])
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
VISÃO GERAL DA
APRESENTAÇÃO









INTRODUÇÃO - expressões e convenções
ALGORITMOS DETERMINÍSTICOS E NÃO DETERMINÍSTICOS Conceitos e comparações
ESCOLHA NÃO DETERMINÍSTICA - Conceito e aplicação
PROBLEMAS P E NP - Conceito e confrontamento
PROBLEMAS NP-DIFÍCEIS E NP-COMPLETOS
APRESENTAÇÃO DE UM PROBLEMA NP-COMLETO
APLICAÇÕES DE NÃO DETERMINISMO EM CIÊNCIA DA
COMPUTAÇÃO
NÃO DETERMINISMO NA INTERNET
CONCLUSÃO
INTRODUÇÃO

Existem muitos problemas para os quais não se conhece
solução eficiente e para muitos não sabemos nem ao menos
dizer se existe esta solução. Estes problemas são bastante
comuns.

Problemas Algorítmicos:
– existe estrutura S que satisfaça propriedades P ? (Decisão)
– encontre estrutura S que satisfaça propriedades P
– encontre estrutura S que satisfaça os critérios de otimização
INTRODUÇÃO

Algoritmos que possuem resolução em tempo polinomial*
são chamados de Algoritmos eficientes e dizemos que
este é um problema tratável.

*Tempo de execução polinomial:
– funciona para n’s grandes;
– no dia-a-dia nos deparamos na grande maioria das vezes com
problemas com tempo de execução O(n), O(n²);
– da mesma forma, por conveniência, assumimos que O(nlogn) é um
tempo de execução polinomial.
ALGORITMOS DETERMINÍSTICOS
×
ALGORITMOS NÃO DETERMINÍSTICOS

Algoritmo Determinístico:
– a qualquer momento da sua lista de operações, o algoritmo
só tem um próximo passo predeterminado a ser tomado;
– se aplicarmos um algoritmo determinístico duas vezes ao
mesmo problema, teremos duas soluções idênticas;
– são os algoritmos encontrados na vida prática.
ALGORITMOS DETERMINÍSTICOS
×
ALGORITMOS NÃO DETERMINÍSTICOS


Não determinismo: qualidade de uma computação que
pode apresentar mais de um resultado.
Algoritmo Não Determinístico:
– teremos mais de um próximo passo a ser tomado, o passo
correto será apontado por uma ferramenta (não implementável),
para cada escolha o algoritmo tomará rumos diferentes;
– esta ferramenta é a escolha não determinística que vamos
chamar de nd-choice.
ESCOLHA NÃO DETERMINÍSTICA

Quando se deparar com várias opções, o nd-choice
munirá nosso algoritmo com o poder de fazer a
escolha certa, de “adivinhar” o caminho que possui a
solução se ela existir.

O algoritmo seguirá os passos determinísticos
normais e intercalará um ou mais usos do nd-choice,
de forma a achar pelo menos uma das entradas para
as quais a resposta ao problema de decisão é SIM e
rejeitar todas para as quais a resposta é NÃO.
PROBLEMAS P e PROBLEMAS NP

Classe P:
– Dizemos que um problema pertence à Classe P se ele puder
ser resolvido por um algoritmo determinístico em tempo
polinomial;
– É a classe de todos os problemas que podem ser resolvidos
por um algoritmo eficiente.

Classe NP:
– Quando, para resolver um problema, temos um algoritmo
Não determinístico (usa nd-choice) que roda em tempo
Polinomial dizemos que o problema pertence à classe NP.
PROBLEMAS P e PROBLEMAS NP

Temos direto da definição que: P  NP

É intuitivo também dizer que: se um problema de decisão é NP,
então uma resposta SIM ou NÃO para o problema pode ser
obtida no máximo em tempo exponencial.

Nunca foi provado que P=NP, para tanto teríamos que mostrar
que todo problema em NP pode ser resolvido por um algoritmo
determinístico em tempo polinomial. Para provar o contrário, ou
seja, que PNP, teríamos que provar que dentre todos os
algoritmos que resolvem um problema NP nenhum é eficiente.
Esta questão continua uma grande incógnita para muitos
pesquisadores e é chamada de Problema P=?NP.
REDUÇÃO POLINOMIAL

Seja L  U o conjunto de todas as entradas de um problema de
decisão cujas respostas são SIM. O problema de decisão é
reconhecer se uma determinada entrada pertence a L. Sejam L1 e L2
dois problemas com entradas nos espaço U1 e U2, dizemos que L1 é
polinomialmente redutível a L2 se existe um algoritmo em tempo
polinomial que converte cada entrada u1  U1 em outra u2  U2, tal
que u1  S1 se e somente se u2  S2.

Se L1 é redutível a L2 e existe um algoritmo em tempo polinomial
para L2 então existe um algoritmo polinomial para 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 a L3
NP-DIFÍCIL e NP-COMPLETO

NP-Difícil
– Um problema X é chamado de NP-Difícil se todos os
problemas da classe NP forem redutíveis a X.
– Resolver um problema NP-Difícil em tempo polinomial
tornaria possível resolver todos os problemas em NP em
tempo polinomial.

NP-Completo
– Um problema X é chamado de NP-Completo se (1) pertencer
a NP e (2) for NP-Difícil.
– Um problema X é NP-Completo se Y é redutível a X para
algum problema Y que seja NP-Completo (transitividade).
TEOREMA DE COOK

Em 1971, Stephen A. Cook introduziu o
conceito de NP-Completo, provando que o
problema da satisfatibilidade (SAT)
pertencia a esta classe.

Para contactar Cook, mande um mail
para: [email protected]

TEOREMA DE COOK:
O problema SAT é NP-Completo.
Com o teorema de Cook, vários outros problemas foram
provados pertencer à classe NP-Completo, esses problemas possuem
uma extrema importância, por existirem em grande número e terem
muitas aplicações práticas. No esquema são representados outros
problemas NP-Completos ligados numa árvore diretamente ao
problema ao qual são redutíveis.
SAT
CLIQUE
COBERTURA
DE
VÉRTICES
CICLO
HAMILTONIANO
CAIXEIRO
VIAJANTE
3SAT
3COLORAÇÃO
MATCHING
TRIDIMENSIONAL
PARTIÇÃO
Problemas NP

Para identificar um problema NP,
usamos um algoritmo não
determinístico

O custo do algoritmo torna-se
polinomial
Algoritmos não-determinísticos

Comandos regulares das linguagens
determinísticas

nd-choice -> oráculo
Reconhecimento
Um algoritmo nãodeterminístico reconhece
(aceita, diz sim) uma entrada
x se existir, pelo menos, uma
maneira do algoritmo chegar
a uma resposta sim.
O PROBLEMA CLIQUE
Dado um grafo G(V,E) e um
inteiro k <= |v|, existe um
subgrafo completo de k
vértices de G?
Algoritmo não-determinístico para Clique
Para v:= 1 até n
Para v:= 1 até n {
nd-choice {
se escolhido[v] := 1
escolhido[v] := 1;
cont:= 0;
escolhido[v] := 0; }
para cada vertice w adjacenta a v {
cont := 0;
cont := 0;
para v:= 1 ate n
se escolhido[w] = 1
cont := cont + escolhido[v];
cont := cont + 1;
se cont != k {
se cont != k - 1
imprima “não existe”
imprima “não existe
exit }
exit }}
imprima “existe”
Não determinismo em
Ciências da Computação

Inteligência Artificial

Prolog - Lógica de 1ª ordem

Concorrência

Linguagens (semântica)
Não determinismo na Web
CONCLUSÕES

Como lidar com os problemas não
determinísticos
– Trabalhar com o caso médio desenvolvendo algoritmos que
solucionam a maioria dos casos
– Tentar algoritmos exponenciais tão eficientes quanto
possível for
– Algoritmos de Aproximação

Projeto Quantum