[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[obm-l] Re: [obm-l] Re: [obm-l] Dúvida sobre sequências randômicas (problema do tipo NP)(to vinicius)



Oi para todos
 
Vinicius perguntou o que é uma interssecção aleatória entre 2 conjuntos
 
Imagine que A e B são conjuntos com infinitos elementos. E C é uma interssecção aleatória de A e B. Isso quer dizer que todos os termos de C pertencem a A e B, mas foram escolhidos de forma aleatória, de modo que até o número de elementos de C é aleatório e todas as quantidades de elementos tem a mesma probabiliadde de ocorrer. Como P(x)=n(x)/(E.A). Como E.A é infinito, pois A e B são infinitos, a chance de C ter finitos termos é 0. Por isso se C é uma interssecção aleatória de A e B infinitos, tal que C não é vazio, C possui infinitos elementos.
 
Quanto a 2ª pergunta, se existem infinitos algoritmos capazes de criar a sequência do problema. O algoritmo genérico que criou todos esses algoritmos, só pode ser determinado após a análise de todos os algoritmos (pelo que eu entendi), isso caracteriza um problema do tipo NP.
 
André T.
 
 
 
----- 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?
Maiores informações podem ser encontradas no texto de Cook sobre o problema "P=NP?" no site www.claymath.org/prizeproblems
 
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 -----
From: Wagner
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.