Algoritmos probabilísticos (randomizados) antes do surgimento da ciência da computação "moderna"

27

Edit: Eu escolhi a resposta com a pontuação mais alta até 06 de dezembro de 2012.

Esta é uma pergunta suave.

O conceito de algoritmos (determinísticos) remonta a BC. E os algoritmos probabilísticos?

Em esta entrada wiki , o algoritmo de Rabin para o problema mais próximo par de geometria computacional foi dado como o primeiro algoritmo randomizado (Ano ???). Lipton introduziu o algoritmo de Rabin como o início da era moderna de algoritmos aleatórios aqui , mas não como o primeiro. Também conheço muitos algoritmos para autômatos finitos probabilísticos (um modelo computacional muito simples) descobertos durante a década de 1960.

Você conhece algum algoritmo (ou método) probabilístico / randomizado antes dos anos 1960?

ou

Qual descoberta pode ser vista como o primeiro algoritmo probabilístico / randomizado?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
fonte
25
A idéia milenar de provar uma colher cheia de sopa fervente para verificar se está bem é essencialmente amostragem aleatória, um algoritmo probabilístico com garantias comprováveis.
arnab
3
O algoritmo de Rabin foi publicado em 1976, muito depois de a ciência da computação "moderna" estar bem estabelecida.
Jeffε
Você poderia talvez esclarecer se há algum critério que gostaria de impor aos "algoritmos", a fim de esclarecer se pensa, por exemplo, que fenômenos naturais que antecedem a humanidade em bilhões de anos representam "algoritmos", conforme sugerido por algumas das respostas abaixo?
Niel de Beaudrap 13/09/12
@NieldeBeaudrap: Na minha opinião, alguns algoritmos matematicamente bem definidos. (Mas, pessoalmente, eu gosto arnab resposta 's muito :))
Abuzer Yakaryilmaz

Respostas:

33

Isso é discutido um pouco no meu artigo com HC Williams, "Factoring Inteiros Before Computers"

Em um artigo de 1917, HC Pocklington discutiu um algoritmo para encontrar o sqrt (a), módulo p, que dependia da escolha aleatória de elementos para obter um não-resíduo de uma determinada forma. Nele, ele disse: "Temos que fazer isso [encontrar o não-resíduo] por julgamento, usando a Lei da Reciprocidade Quadrática, que é um defeito no método. Mas, como para cada valor de u, metade dos valores de t são adequados, não deve haver dificuldade em encontrar um ".

Portanto, essa é uma das primeiras menções explícitas a um algoritmo aleatório.

Jeffrey Shallit
fonte
3
Esta é uma referência muito legal. O Algoritmo de Pocklington já foi des randomizado? Tangencialmente, adoro o seu trabalho - tanto dentro como fora do CS - em particular o seu algoritmo para a conjectura de Bachet (foi difícil encontrar uma cópia do artigo!), Mas também as suas liberdades civis funcionam. Você já assistiu "Mr. Death?", De Errol Morris?
Ross Snider
interessante. é uma reminiscência de teste de primalidade randomizado
Sasho Nikolov
3
E um algoritmo de Las Vegas também! Boa referência.
David Eppstein
Referência muito agradável.
Jérémie
falando em fatorar antes dos computadores, alguém sabe o que Lehmer sabia sobre o algoritmo de pocklington, ou qualquer outro algoritmo aleatório, ou se ele realmente o implementou em seu computador de fator de peneira ? os dois, aparentemente, ter alguma ligação com o primality teste Pocklington-Lehmer acc a wikipedia
vzn
28

O algoritmo de agulha de Buffons para estimar , basicamente um método de Monte Carlo , data da publicação em 1777. observe que os métodos de Monte Carlo datam da década de 1940 com o projeto de bomba atômica "Manhattan" dos EUA e foram co-ventilados por Ulam, Von Neumann e Metropolis.π

vzn
fonte
8
Na verdade, isso está relacionado a uma pergunta que eu fiz . Ninguém sabe exatamente quem criou o algoritmo que muitas pessoas consideram ser a agulha de Buffon atualmente.
Jérémie
mais exatamente - existe um algoritmo claro de agulha de Buffon que envolve soltar agulhas nas listras e um algoritmo aparentemente muito diferente de "ponto aleatório versus círculo", como você menciona na pergunta que algumas pessoas parecem atribuir incorretamente a Buffon, com diferentes e mais origens modernas, mas incertas.
vzn
19

O algoritmo Metropolis-Hastings foi publicado em 1953 e remonta ao projeto de Manhattan, muito antes de Rabin. Como muitos dos métodos aleatórios iniciais dados em outras respostas, é um algoritmo de Monte Carlo.

É possível que a afirmação na página da Wikipedia seja uma forma ilegível de que Rabin's foi o primeiro algoritmo de Las Vegas ?

David Eppstein
fonte
11

A curva / distribuição normal gaussiana de estatísticas pode ser "computada" por muitos processos físicos muito simples. Uma das mais simples é uma placa com uma matriz de pinos em uma grade triangular (também conhecida como "caixa de Galton" datada de 1800), na qual os pinos são deslocados em meia distância quadrada em linhas alternadas. Soltando bolas repetidamente da mesma posição, as bolas deslocam-se aleatoriamente para a esquerda ou direita com probabilidade 0,5. A distribuição cumulativa registrada nas posições inferiores produz a curva gaussiana / normal.

vzn
fonte
+1 apenas porque atualmente estou projetando um logotipo para o nosso grupo de pesquisa estatística e a Galton Box foi nossa primeira ideia (mas acaba sendo muito complexa para um logotipo).
11139 Konrad Rudolph
10

Na minha opinião, a evolução natural é um algoritmo probabilístico bom e bastante antigo :-)

Marzio De Biasi
fonte
1
+1, embora a descrição do processo como probabilística nos seja muito mais recente. ;-)
Konrad Rudolph
7
O "algoritmo" sugere que há um problema que ele está tentando resolver; mas não é Nem está "tentando" criar animais melhores para sobreviver; criar animais adaptados ao ambiente é apenas um subproduto (que nem sempre é alcançado, como evidenciam os eventos de extinção e extinção em massa). Nesse sentido, a evolução não é mais um algoritmo do que a gravidade; é exatamente isso que acontece.
Niel de Beaudrap 13/09/12
MDB está morto! evolution é um algoritmo genético que seleciona a aptidão evolutiva e a ciência ainda está alcançando todas as implicações disso ... isto é, é uma área ativa de pesquisa. não foi apontado muito ou amplamente apreciado, mas o sucesso fenomenal dos AGs no CS é na verdade uma forte evidência matemática / científica da realidade da teoria da evolução biológica. no entanto, admita que é definitivamente diferente de outros "algoritmos" de algumas maneiras importantes.
vzn
2
@vzn: um "algoritmo genético", antes de tudo, seleciona uma função de condicionamento físico que impomos para uma finalidade específica. Usamos a evolução como uma ferramenta para fazer algo nesse caso. Mas isso não significa que a evolução biológica seja um algoritmo para fazer qualquer coisa. Usando a analogia da gravidade novamente, existe um sentido significativo em que todas as cachoeiras são algoritmos, apenas porque às vezes usamos cascatas para gerar eletricidade?
Niel de Beaudrap 13/09/12
4
@vzn: Apenas afirmo que "um algoritmo" deve incluir parâmetros bem definidos de probabilidade de sucesso, sem mencionar que deve haver um agente que o execute . O único 'agente' que se poderia dizer realizar a "evolução" seria um ecossistema inteiro. O que devemos dizer que o ecossistema está "tentando" alcançar? Eu diria que você é da natureza antropomorfizadora . Só exijo que "aplicar um algoritmo" envolva uma certa quantidade de intencionalidade orientada a objetivos, aplicada por humanos ou não. Em que sentido um processo sem objetivo pode representar um "algoritmo"?
Niel de Beaudrap 15/09/12
6

Há um artigo sobre algoritmos aleatórios em culturas 'primitivas' .

O uso de oráculos (por exemplo, ossos de galinha, pedras) para decidir onde caçar pode ser visto como um algoritmo aleatório. Pode-se argumentar que a randomização dos locais de caça impede a adaptação e a caça excessiva.

adrianN
fonte
0

um dos artigos de "milagre" de Einsteins 1905 estava em movimento browniano , um exemplo físico clássico de uma caminhada aleatória e produz uma fórmula (isto é, basicamente um algoritmo, se o processo físico é o "computador") para estimar / calcular partículas (molécula) diâmetro dado outras constantes físicas conhecidas e observação / medição do deslocamento (aleatório) de partículas ao longo do tempo. este artigo também serviu como evidência teórica / experimental / fundamental para a teoria atômica da matéria.

vzn
fonte
4
Novamente, como na evolução: embora o movimento possa ser aleatório e possa ser modelado por uma caminhada aleatória, que algoritmo isso representa? Embora alguns algoritmos usem passeios aleatórios, isso não significa que todos os passeios aleatórios representam algoritmos (assim como qualquer sequência de palavras em inglês representa prosa apenas porque toda a prosa em inglês consiste em palavras em inglês).
Niel de Beaudrap 13/09/12
-4

nini

a máquina também possui alguma semelhança com o mecanismo diferencial Babbage (~ 1830s). não é inteiramente inconcebível que Babbage ou Lovelace possam ter imaginado algo semelhante aos algoritmos probabilísticos. as máquinas podem certamente ser usadas para implementar algoritmos probabilísticos, emprestando a teoria moderna e superpondo-a ao passado.

[1] Máquina de fatoração Lehmer

[2] motor Babbage


Lehmer mod n & máquina de factoring

vzn
fonte
1
Você pode descrever o sentido em que calculou respostas probabilísticas para grandes números? Uma pesquisa rápida não parece encontrar referências a essa linha.
Niel de Beaudrap 15/09/12
pelo que entendi, foi usado [entre outros propósitos] para encontrar fatores menores de grandes números de testes semelhantes à peneira de eratóstenes. se o número grande passou, "provavelmente não é composto" ou "possivelmente principal" ou "candidato principal". infelizmente, a internet não é muito boa com referências e origens históricas [até mesmo na wikipedia], os livros são melhores. mais detalhes no fundo da presente página , "tipos de problemas Lehmer foi a tentativa de resolver" pelo Dr. Mike Williams, curador chefe do museu de história do computador do CA
vzn
1
a (s) máquina (s) certamente podem ser usadas para implementar algoritmos probabilísticos - Então? Ao contrário de outras máquinas que não podem?
Jeffε
2
embora a terminologia da época não tenha se referido a "algoritmos probabilísticos", ela foi usada dessa maneira em alguns casos - [citação necessário] Se você tiver evidências de que "possivelmente primo" é uma declaração formal sobre probabilidade, e não simplesmente uma descrição heurística, por favor, cite-a. Caso contrário, por favor, pare de especular.
Jeffε
n1∗n2∗n3∗nxx
-6

Aqui estão alguns casos do início e até da antiguidade / pré-história de conceitos relacionados a algoritmos aleatórios.

  • n/2

  • jogos de azar e jogos de azar são muito antigos. da teoria moderna, os jogos têm fortes semelhanças, senão conexões diretas com algoritmos. sabe-se que os dados de jogo / jogo têm pelo menos cinco milênios .

  • os gregos e romanos também tinham o conceito de desenhar canudos onde a pessoa que desenhava o menor canudo perdia. semelhante aos dados, em certo sentido, é o algoritmo mais simples possível para fazer uma única escolha aleatória.

  • divulgação completa, há um toque de história sangrenta e conexão. em outra resposta, o MDB menciona evolução . parte da evolução é a seleção natural, que também tem paralelos com a guerra humana - aparentemente uma parte intrínseca da evolução das cidades / sociedades humanas. de certo modo, uma guerra é um algoritmo semi-aleatório bruto para "algo" que sociólogos e historiadores ainda discutem sobre causas exatas. roubo / pilhagem? Alocando recursos? território? poder político? escravos? (etc.) os romanos também tinham uma prática horrenda chamada dizimação(a palavra moderna na verdade deriva em etimologia da antiga!), na qual, como castigo por motim ou covardia, todo décimo soldado selecionado aleatoriamente era executado pelos soldados restantes. pode parecer uma prática esquecida e atávica, mas parece ter alguma paralela à roleta russa moderna , um quase-jogo aleatório "moderno" para o suicídio.

vzn
fonte
1
Não é disso que estou perguntando; Estou perguntando se eles argumentaram sobre a frequência relativa dos números compostos da maneira que você descreve.
Niel de Beaudrap 13/09/12
1
Receio não estar interessado em generalidades vagas, e parece óbvio que discordamos fundamentalmente do que é um "algoritmo". Estou interessado em mais do que apenas "fenômenos". Caso contrário, podemos citar todos os eventos da mecânica quântica após o Big Bang como exemplos de "algoritmos aleatórios", o que torna o assunto trivial.
Niel de Beaudrap 13/09/12
1
"pergunta suave" não significa uma pergunta com limites infinitamente flexíveis; "visão histórica" ​​não é o mesmo que revisionismo histórico.
Niel de Beaudrap 13/09/12
2
Sua 'dica' para mim sobre evolução, nem o fato de me desperdiçar um tempo com uma pergunta que eu não gosto, nem a evasão da minha pergunta anterior eram respeitosos. E, de fato, especular que os gregos provavelmente sabiam sobre o que você está falando, mas não se preocuparam em escrever sobre isso é exatamente uma das coisas às quais o "revisionismo histórico" pode se referir. (Talvez Arquimedes tenha inventado a notação decimal, mas não se incomodou em fazer nenhum registro; afinal, o Sand Reckoner está muito perto de colocar a notação, e os gregos usaram um sistema parecido com a base 10. Mas devemos levar a sério a idéia ? Não.)
Niel de Beaudrap
1
Concordo que é possível e que nem sequer é exagero - além, é claro, do fato de que não parecemos ter nenhum registro dos gregos falando sobre probabilidade em si. Mas se houver um registro real, você deve ser capaz de apontar. Caso contrário, é especulação, não história.
Niel de Beaudrap 13/09/12
-7

JS menciona a teoria dos números. Fermat é creditado com o teste de primalidade de Fermat , um algoritmo probabilístico que data de 1600 e serve como precursor de testes de primalidade mais modernos, como Solovay-Strassen e Miller-Rabin. [seria necessário um historiador especializado em matemática e teoria dos números para tentar identificar exatamente o que Fermat sabia sobre ele versus o conhecimento moderno, que é muito mais completo sobre a estrutura de seus pseudo-tempos (falsos positivos) etc.]

vzn
fonte
2
Você pode citar Fermat como tendo usado seu teste como uma maneira de filtrar números inteiros selecionados aleatoriamente como não primos (em oposição a apenas uma propriedade interessante que os primos possuem)? Ou talvez cite um autor anterior que sugere fazê-lo?
Niel de Beaudrap 13/09/12
como afirmado, é melhor deixar os detalhes exatos para um historiador profissional. no entanto, note [adendo; deveria ter mencionado isso] o simples fato histórico de que fermat é creditado como o mentor fundador da teoria das probabilidades junto com pascal, estabelecendo as bases de uma série de cartas em meados dos anos 1600.
vzn
2
não é realmente apropriado propor respostas com base no que você acredita que outra pessoa possa mostrar. Novamente, isso é especulação.
Niel de Beaudrap 15/09/12
3
@vzn: Se Fermat tivesse percebido que o pequeno teorema de Fermat era um bom teste de primalidade, ele teria calculado que o 5º número de Fermat não era primo . Isso não foi feito até Euler consignar isso mais de 60 anos após a morte de Fermat.
quer
2
@vzn: [citação necessário]
Jeffε 15/09/12