Como os números reais são especificados na computação?

27

Essa pode ser uma pergunta básica, mas eu tenho lido e tentado entender artigos sobre assuntos como computação de equilíbrio de Nash e teste de degeneração linear e não tenho certeza de como os números reais são especificados como entrada. Por exemplo, quando se afirma que o LDT possui certos limites inferiores polinomiais, como os números reais são especificados quando são tratados como entrada?

Philip White
fonte
1
Você pode encontrar a discussão aqui de interesse: en.wikipedia.org/wiki/Computable_number
Joseph Malkevitch
Alguém deve juntar esses papéis em um e-book gratuito que pode ser baixado em baixa.
Dilawar 30/01

Respostas:

34

Discordo da sua resposta aceita por Kaveh. Para programação linear e equilíbrios de Nash, o ponto flutuante pode ser aceitável. Mas os números de ponto flutuante e a geometria computacional se misturam muito mal: o erro de arredondamento invalida as suposições combinatórias dos algoritmos, freqüentemente causando o colapso. Mais especificamente, muitos algoritmos de geometria computacional dependem de testes primitivos que verificam se um determinado valor é positivo, negativo ou zero. Se esse valor estiver muito próximo de zero e o arredondamento do ponto flutuante fizer com que ele tenha o sinal errado, coisas ruins podem acontecer.

Em vez disso, as entradas geralmente são assumidas como tendo coordenadas inteiras e os resultados intermediários geralmente são representados exatamente, como números racionais com precisão suficientemente alta para evitar transbordamentos ou como números algébricos. Aproximações de ponto flutuante a esses números podem ser usadas para acelerar os cálculos, mas apenas em situações em que é possível garantir que os números estejam suficientemente longe de zero para que os testes de sinais dêem as respostas corretas.

Na maioria dos trabalhos de algoritmos teóricos em geometria computacional, essa questão é contornada assumindo que as entradas são números reais exatos e que as primitivas são testes exatos dos sinais de raízes de polinômios de baixo grau nos valores de entrada. Mas se você estiver implementando algoritmos geométricos, tudo isso se tornará muito importante.

David Eppstein
fonte
Gostei da parte da resposta de Kaveh, onde ele sugeriu que existem modelos alternativos de computação, pois isso parecia estar alinhado com o que eu havia lido no artigo que estava vendo. Dito isto, eu realmente não sabia a resposta ... Não aceitei a resposta de Kaveh por enquanto. Na verdade, eu suspeitava que os números algébricos tivessem algo a ver com isso. De qualquer forma, obrigado por dedicar um tempo para refletir sobre minha pergunta ... Pensarei e lerei mais antes de aceitar uma resposta.
Philip White
Eu não disse que é um bom modelo para CG, meu argumento foi que, mesmo quando os autores dizem que as entradas são números reais, elas não são realmente números reais . Concordo com você que não deveria ter incluído o CG entre os outros. Eu li um número muito pequeno de trabalhos de computação gráfica, o modelo BSS está bem estabelecido em trabalhos teóricos de computação gráfica?
Kaveh
1
Perdoe minha ignorância, mas o que o BSS representa?
Philip White
1
O modelo BSS é um modelo teórico que assume que números reais arbitrários estão disponíveis. O que é feito no CG envolve implementações reais de um modelo que geralmente é restrito a números algébricos. Além disso, as implementações de CG estão longe do custo unitário por operação. Então eles não são a mesma coisa. Veja, por exemplo, o modelo de número real do LEDA, citeseerx.ist.psu.edu/viewdoc/…
David Eppstein
10
STsSs>tTt
8

Esta não é uma resposta direta à sua pergunta, é mais uma resposta a Rafael . Recentemente, houve bastante trabalho especificando cálculos de números reais usando coindução. Aqui estão alguns artigos sobre o assunto.

Eles dificilmente cobrem todo o espectro da computação em número real, mas estão sendo feitos progressos para reduzir vários problemas.

Dave Clarke
fonte
1
R
Bom ponto. Não sei ao certo quais são as limitações da abordagem coindutiva. A abordagem está em sua infância.
Dave Clarke
7

A complexidade computacional das computações sobre números reais é considerada por Blum, Cucker, Shub e Smale . Aqui está uma descrição parcial do livro:

A teoria clássica da computação tem suas origens nos trabalhos de Goedel, Turing, Church e Kleene e tem sido uma estrutura extraordinariamente bem-sucedida para a ciência da computação teórica. A tese deste livro, no entanto, é que ele fornece uma base inadequada para a computação científica moderna, onde a maioria dos algoritmos são algoritmos de números reais. O objetivo deste livro é desenvolver uma teoria formal da computação que integre os principais temas da teoria clássica e que seja mais diretamente aplicável a problemas em matemática, análise numérica e computação científica. Ao longo do caminho, os autores consideram problemas fundamentais como: O conjunto de Mandelbrot é decidível? Para mapas quadráticos simples, a Julia é um conjunto de paradas? Qual é a real complexidade de Newton? s método? Existe um algoritmo para decidir o problema da mochila em um número nominal de etapas? A Hilbert Nullstellensatz é intratável? O problema de localizar um zero real de um grau quatro polinomial é intratável? A programação linear é tratável sobre os reais?

Você pode encontrar uma resenha deste livro no ACM SIGACT News .

MS Dousti
fonte
Este livro parece muito interessante, obrigado.
Philip White
Você é muito bem-vindo.
MS Dousti 9/10/10
5
Vale a pena notar que o modelo BSS de computação sobre os reais é controverso, por razões muito parecidas com as que David Eppstein se referiu em um comentário acima. Por exemplo: o axioma do BSS que calcula se x <y dá um passo de tempo, para reais arbitrários x e y. Por outro lado, abordagens como a Efetividade do tipo dois (TTE) definem máquinas que tomam como aproximações de entrada os reais e produzem aproximações computáveis ​​para funções sobre os reais. Quanto mais tempo decorrido, melhor as aproximações de entrada e saída podem se tornar. Essa abordagem parece mais realista para mim.
Aaron Sterling
@ Aaron Sterling: você conhece uma boa referência para a eficácia do tipo dois?
10139 Joshua Grochow
3
@ Joshua Grochow: Desculpe, não cheguei a isso mais cedo. O livro ao qual Kaveh se vincula é o "Nielsen e Chuang" da TTE. No entanto, é tão carregado de notações que parece misterioso para um leitor casual. Gostaria de sugerir, em vez disso, os slides seguintes tutoriais de Vasco Brattka: cca-net.de/vasco/cca/tutorial.pdf
Aaron Sterling
7

Editado / corrigido com base nos comentários

Quando os autores falam sobre entradas de números reais na programação linear, computação de equilíbrio de Nash, ... na maioria dos trabalhos (trabalhos que não tratam de computação / complexidade sobre números reais), eles realmente não significam números reais. São números racionais e números que surgem deles devido a suas manipulações (números algébricos). Então você pode pensar nelas como representadas por seqüências finitas.

Por outro lado, se o artigo trata de computabilidade e complexidade na análise , eles não estão usando o modelo usual de computação e existem vários modelos incompatíveis de computação / complexidade sobre números reais.

Se o documento não especificar um modelo de computação sobre números reais, você pode assumir com segurança que é o primeiro caso, ou seja, são apenas números racionais.

Geometria Computacional é diferente. Na maioria dos trabalhos em CG, se os autores não especificarem qual é o modelo que, com relação a ele, a correção e a complexidade de um algoritmo está sendo discutida, pode-se supor que seja o modelo BSS (também conhecido como RAM real).

O modelo não é realista e, portanto, a implementação não é direta. (Essa é uma das razões pelas quais algumas pessoas na CCA preferem modelos teóricos de Ko-Friedman / TTE / Domain , mas o problema com esses modelos é que eles não são tão rápidos quanto a computação em ponto flutuante na prática.) o algoritmo no modelo BSS não transfere necessariamente para a correção do algoritmo implementado.

O livro de Weihrauch contém uma comparação entre diferentes modelos (Seção 9.8). São apenas três páginas e vale a pena ler.

(Também existe uma terceira maneira, que pode ser mais adequada para CG, você pode dar uma olhada neste artigo:

Chee Yap, " Teoria da computação real segundo o EGC "

onde EGC é computação geométrica exata .)

Kaveh
fonte
Acho que o artigo no qual estou interessado principalmente especifica um modelo, uma vez que inclui a frase "Agora definimos formalmente nosso modelo de computação". O artigo chama-se "Limites inferiores para problemas de satisfação" e parece haver alguma discussão sobre árvores de decisão lineares e polinômios de consulta. Então, acho que essa é a resposta que eu estava procurando lá ... obrigado. Vou reler o artigo e ver se consigo entendê-lo.
Philip White
2
Discordo. Este é o modelo errado para geometria computacional. Veja minha resposta mais detalhada abaixo.
David Eppstein
1
@ Kaveh: Eu acho que você deveria dizer que são números racionais , não números de ponto flutuante. Os números racionais exatos são fáceis de representar por seqüências finitas e, em muitas aplicações (por exemplo, aquelas relacionadas à programação linear), os resultados intermediários também serão números racionais se suas entradas forem números racionais. (.. Claro que, como David Eppstein apontou, comp geom é uma exceção notável no sentido de que os resultados intermediários geralmente não são racionais.)
Jukka Suomela
@Jukka: Você está certo, substituirei o ponto flutuante por racional.
Kaveh
5
Não. Quando escrevo "número real", quero dizer realmente "número real", e com isso quero dizer número realmente real, realmente a partir dos reais. Sério. Em particular, no artigo sobre o @Philip, devo assumir que os algoritmos funcionam para entradas reais arbitrárias , para que eu possa aplicar resultados de análises não padronizadas.
Jeffε
3

Eles não são e não podem, em geral. Só podemos tratar um número contável de entradas (e saídas e funções) com nossos modelos de computação. Em particular, qualquer entrada deve ser finita, mas nem todos os números reais têm representações finitas.

Suponho que você poderia assumir algum tipo de oráculo que produz o próximo dígito de um certo número real mediante solicitação (sth como um fluxo). Caso contrário, você terá que conviver com aproximações (arbitrariamente precisas).

Rafael
fonte
Se isso for verdade, como o LDT pode lidar com números reais? Eu li algo sobre "Árvores de Decisão r-Lineares", mas realmente não entendi o que elas estavam falando no artigo "Limites inferiores para problemas lineares de saturação".
Philip White
Aposto que eles não podem ou não usam máquinas de Turing (ou conceitos equivalentes). As outras respostas que não são tão rígidas / gerais quanto as minhas devem esclarecer isso.
Raphael