----- 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.