----- Original Message -----
Sent: Friday, September 13, 2002 12:26
PM
Subject: [obm-l] Re: [obm-l] Dúvida sobre
sequências randômicas (problema do tipo NP)
No meu ponto de vista, existem infinitos
algoritmos para fazer alguma coisa. Até para não fazer nada.
Por exemplo, um algoritmo para calcular a+b.
Pode-se fazer da maneira tradicional, ou então pode-se fazer um loop
percorrendo os números, subtraindo b e verificando se é igual a
'a'.
Ou então pode-se somar 6 a 'a' somar 'b' ao
resultado e depois subtrair '6'.
Agora, em vez de fazer as operação acima com 6,
faça com todas os outros naturais. Como são constantes, haverá infinitos
algoritmos que fazem a soma.
Enfim, o meu raciocínio é por aí. Esse é mais um
motivo que as classes P e NP, por exemplo, são conjuntos de problemas e
não de algoritmos. Estudar algoritmos pode ser muito mais
complicado.
Formalmente, em teoria da computação, podemos
definir um problema de decisão como uma linguagem. Um problema de decisão é um
cuja resposta é sim ou não. Uma linguagem pode ser considerada como um
conjuntos de seqüências de caracteres de um alfabeto. Podemos sempre escrever
uma instância de um problema como uma string em um alfabeto. Assim
o problema pode ser visto como um mapeamento de tais seqüências em {0,1}.
A linguagem associada ao problema contém todas as seqüências (e somente elas)
que são mapeadas em 1.
Assim todo problema de decisão fica reduzido ao
problema: Essa seqüência pertence a essa linguagem?
Isso facilita bastante a teoria.
Problemas de otimização podem ser reduzidos a
problemas de decisão utilizando busca binária com perguntas do tipo: O melhor
valor é melhor que k?
Uma outra observação é que nem todo problema
pertence necessariamente a NP. Pode ser que vc não consiga um algoritmo
polinomial em uma máquina não-determinística para ele.
Eu não entendi a conclusão: "Logo existem
infinitas alternativas a serem analisadas, ou seja o problema é do tipo
NP."
Poderia tb me explicar o que é "intersecção
aleatória"?
Até mais
Vinicius
----- Original Message -----
Sent: Thursday, September 12, 2002 8:51
PM
Subject: [obm-l] Dúvida sobre
sequências randômicas (problema do tipo NP)
Oi pessoal
Queria perguntar ao Nicolau ou a quem conseguir
me resolver essa pergunta:
Se um algoritmo pode construir uma sequência
randômica, uma sequência qualquer desse tipo com um número finito n de
termos poderia então ser descrita por uma infinidade de algoritmos
diferentes, e esses algoritmos podem ser todos construidos a partir de um
algoritmo.(todos os algoritmos iriam variar de problema para problema).
Ou seja uma sequência pode ser construida por infinitos algoritmos
diferentes, mas todos esses algoritmos podem ser construidos a partir de um
mesmo algoritmo.
A problema é o seguinte: Dada uma sequência
qualquer, qual é o algoritmo que gera todos os outros?
A minha dúvida é que pelo o que posso ver esse
problema é um problema do tipo NP (polinominal não-determinístico), ou seja
a sua resposta existe mas é impossível de ser dada na prática.
O meu raciocínio para chegar a essa conclusão
foi o seguinte:
Primeiro é preciso provar que o problema tem
solução:
Sendo a sequência A=a,b,c,d,e,f,g,...,n (em que
a é o 1º termo, b é o 2º, até n que é o n-ésimo termo).
Sendo B o conjunto de algoritmos que geram
sequências em que quando o primeiro termo é a, o segundo é b e sendo C o
conjunto dos algoritmos para os quais se o 1º termo é b, o 2º é
C.
O algoritmo que descreve a sequência A então
pertence à B intersecção com C. B e C possuem infinitos elementos.
Como a,b,c são 3 números aleatórios, B intersecção com C é aleatório. A
intersecção aleatória de 2 conjuntos infinitos é um conjunto infinito.
Expandindo esse raciocínio, existem infinitos algoritmos que perfazem A.
Logo existem infinitas alternativas a serem analisadas, ou seja o problema é
do tipo NP.
Esse pensamento esta certo?
Já vou agradecendo
André
T.