Algoritmos probabilísticos (aleatorios) antes de que apareciera la informática "moderna"

27

Editar: elijo la respuesta con la puntuación más alta antes del 06 de diciembre de 2012.

Esta es una pregunta suave.

El concepto de algoritmos (deterministas) se remonta a BC. ¿Qué pasa con los algoritmos probabilísticos?

En esta entrada de la wiki , el algoritmo de Rabin para el problema de par más cercano en geometría computacional se dio como el primer algoritmo aleatorio (año ???). Lipton introdujo el algoritmo de Rabin como el comienzo de la era moderna de los algoritmos aleatorios aquí , pero no como el primero. También conozco muchos algoritmos para autómatas finitos probabilísticos (un modelo computacional muy simple) descubierto durante la década de 1960.

¿Conoces algún algoritmo (o método) probabilístico / aleatorio incluso antes de 1960?

o

¿Qué hallazgo puede verse como el primer algoritmo probabilístico / aleatorio?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
fuente
25
La vieja idea de probar una cucharada de sopa hirviendo para comprobar si sabe bien es esencialmente un muestreo aleatorio, un algoritmo probabilístico con garantías comprobables.
arnab
3
El algoritmo de Rabin se publicó en 1976, mucho después de que la informática "moderna" estuviera bien establecida.
Jeffε
¿Podría aclarar si hay algún criterio que le gustaría imponer a los "algoritmos", para aclarar si piensa, por ejemplo, que los fenómenos naturales que preceden a la humanidad en miles de millones de años representan "algoritmos", como sugieren algunas de las respuestas ¿abajo?
Niel de Beaudrap
@NieldeBeaudrap: Lo que en mi mente eran algunos algoritmos matemáticamente bien definidos. (Pero, personalmente, me gusta mucho la respuesta de
arnab

Respuestas:

33

Esto se discute un poco en mi artículo con HC Williams, "Factorizar enteros antes de las computadoras"

En un artículo de 1917, HC Pocklington discutió un algoritmo para encontrar sqrt (a), módulo p, que dependía de elegir elementos al azar para obtener un no residuo de una determinada forma. En él, dijo, "Tenemos que hacer esto [encontrar el no residuo] por prueba, usando la Ley de Reciprocidad Cuadrática, que es un defecto en el método. Pero en cuanto a cada valor de u, la mitad de los valores de t son adecuados, no debería haber dificultades para encontrar uno ".

Esta es una de las primeras menciones explícitas de un algoritmo aleatorio.

Jeffrey Shallit
fuente
3
Esta es una muy buena referencia. ¿Se ha desrandomizado el algoritmo de Pocklington? Tangencialmente, me encanta su trabajo, tanto dentro como fuera de CS, en particular su algoritmo para la conjetura de Bachet (aunque fue difícil encontrar una copia del documento), pero también su trabajo de libertades civiles. ¿Has visto "Mr. Death" de Errol Morris?
Ross Snider
interesante. es una reminiscencia de las pruebas de
primitivas
3
¡Y un algoritmo de Las Vegas también! Buena referencia
David Eppstein
Muy buena referencia.
Jérémie
Hablando de factoring antes de las computadoras, ¿alguien sabe lo que Lehmer sabía sobre el algoritmo pocklington, o cualquier otro algoritmo aleatorio, o si Lehmer lo implementó en su computadora de factorización de tamiz ? los dos aparentemente tienen alguna conexión con la prueba de primalidad de Pocklington-Lehmer según wikipedia
vzn
28

El algoritmo de la aguja de Buffons para estimar , básicamente un método de Monte Carlo , data de su publicación en 1777. Tenga en cuenta que los métodos de Monte Carlo datan de la década de 1940 con el proyecto de bomba atómica "Manhattan" de EE. UU. Y fueron inventados por Ulam, Von Neumann y Metropolis.π

vzn
fuente
8
En realidad, esto está relacionado con una pregunta que hice . Nadie sabe exactamente quién ideó el algoritmo que muchas personas consideran hoy aguja de Buffon.
Jérémie
dicho más exactamente: hay un algoritmo de aguja de Buffon claro que implica dejar caer agujas sobre rayas, y un algoritmo de "punto aleatorio versus círculo" aparentemente muy diferente como mencionas en esa pregunta que algunas personas parecen atribuir incorrectamente a Buffon, con diferentes, más Orígenes modernos, pero inciertos.
vzn
19

El algoritmo Metropolis-Hastings fue publicado en 1953 y se remonta al proyecto de Manhattan, mucho antes de Rabin. Como muchos de los primeros métodos aleatorios dados en otras respuestas, es un algoritmo de Monte Carlo.

¿Es posible que la afirmación en la página de Wikipedia sea una forma confusa de la afirmación de que Rabin fue el primer algoritmo de Las Vegas ?

David Eppstein
fuente
11

La curva / distribución normal gaussiana de la estadística se puede "calcular" mediante muchos procesos físicos muy simples. Una de las más simples es una placa con una matriz de clavijas en una cuadrícula triangular (también conocida como "caja de Galton" que data del siglo XIX) donde las clavijas están desplazadas 1/2 distancia cuadrada en filas alternas. Al soltar bolas repetidamente desde la misma posición, las bolas se desplazan aleatoriamente hacia la izquierda o hacia la derecha con una probabilidad de 0.5. La distribución acumulativa registrada en las posiciones inferiores produce la curva de Gauss / normal.

vzn
fuente
+1 solo porque actualmente estoy diseñando un logotipo para nuestro grupo de investigación de estadísticas y Galton Box fue nuestra primera idea (pero resulta ser demasiado complejo para un logotipo).
Konrad Rudolph
10

En mi opinión, la evolución natural es un algoritmo probabilístico bueno y bastante antiguo :-)

Marzio De Biasi
fuente
1
+1 aunque la descripción del proceso como probabilístico nos sea mucho más reciente. ;-)
Konrad Rudolph
77
El "Algoritmo" sugiere que hay un problema que está tratando de resolver; Pero no lo es. Ni siquiera está "tratando" de hacer animales que sean mejores para sobrevivir; crear animales que se adapten a su entorno es solo un subproducto (uno que no siempre se logra, ya que los eventos de extinción y extinción masiva lo hacen evidente). A este respecto, la evolución no es más un algoritmo que la gravedad; Es solo esto lo que sucede.
Niel de Beaudrap
MDB está muerto! La evolución es un algoritmo genético que selecciona la aptitud evolutiva y la ciencia aún se está poniendo al día con todas las implicaciones de esto ... es decir, es un área activa de investigación. no se ha señalado mucho o muy apreciado, pero el éxito fenomenal de los GA en CS es en realidad una fuerte evidencia matemática / científica de la realidad de la teoría de la evolución biológica. sin embargo, reconozca que es definitivamente diferente a otros "algoritmos" en algunos aspectos clave.
vzn
2
@vzn: un "algoritmo genético", en primer lugar, selecciona una función de aptitud que imponemos para un propósito específico. Utilizamos la evolución como herramienta para hacer algo en ese caso. Pero eso no significa que la evolución biológica sea un algoritmo para hacer algo. Usando la analogía de la gravedad nuevamente, ¿hay un sentido significativo en el que todas las cascadas son algoritmos, solo porque a veces las usamos para generar electricidad?
Niel de Beaudrap
44
@vzn: Simplemente afirmo que "un algoritmo" debería implicar parámetros bien definidos de probabilidad de éxito, sin mencionar que debería haber un agente que lo lleve a cabo . El único 'agente' que podría decirse que lleva a cabo la "evolución" sería un ecosistema completo. ¿Qué deberíamos decir que el ecosistema está "intentando" lograr? Yo diría fácilmente que estás antropomorfizando la naturaleza. Solo exijo que "aplicar un algoritmo" implique cierta cantidad de intencionalidad orientada a objetivos, aplicada por humanos o no. ¿En qué sentido puede un proceso sin un objetivo representar un "algoritmo"?
Niel de Beaudrap
6

Hay un artículo sobre algoritmos aleatorios en culturas 'primitivas' .

El uso de oráculos (por ejemplo, huesos de pollo, piedras) para decidir dónde cazar puede verse como un algoritmo aleatorio. Se puede argumentar que aleatorizar los terrenos de caza impide la adaptación del juego y la caza excesiva.

adrianN
fuente
0

uno de los documentos de "milagro" de Einsteins 1905 fue sobre el movimiento browniano , un ejemplo físico clásico de una caminata aleatoria y produce una fórmula (es decir, básicamente un algoritmo, si el proceso físico es la "computadora") para estimar / calcular la partícula (molécula) diámetro dado otras constantes físicas conocidas y la observación / medición del desplazamiento de partículas (aleatorio) a lo largo del tiempo. Este artículo también sirvió como evidencia teórica / experimental / fundacional temprana para la teoría atómica de la materia.

vzn
fuente
44
De nuevo como con la evolución: aunque el movimiento puede ser aleatorio, y puede ser modelado por una caminata aleatoria, ¿qué algoritmo representa esto? Si bien algunos algoritmos usan caminatas aleatorias, esto no significa que todas las caminatas aleatorias representen algoritmos (al igual que ninguna cadena de palabras en inglés representa la prosa solo porque toda la prosa en inglés consiste en palabras en inglés).
Niel de Beaudrap
-4

ninyo y aplica el resto chino thm . para números más grandes, calcula respuestas probabilísticas a preguntas de teoría de números, incluida la factorización. aunque la terminología en ese momento puede no haberse referido a "algoritmos probabilísticos", posiblemente se usó de esta manera en algunos casos. (de esta manera también tiene cierta similitud con la prueba de probabilidad probabilística de Fermat).

La máquina también tiene cierta similitud con el motor diferencial Babbage (~ 1830). No es del todo inconcebible que Babbage o Lovelace hayan imaginado algo similar a los algoritmos probabilísticos. la máquina (s) ciertamente puede usarse para implementar algoritmos probabilísticos, tomando prestada la teoría moderna y superponiéndola al pasado.

[1] Máquina de factorización Lehmer

[2] Motor de babbage


Lehmer mod n y factoring machine

revs vzn
fuente
1
¿Puedes describir el sentido en el que calculó las respuestas probabilísticas para grandes números? Una búsqueda rápida no parece que no puedo encontrar ninguna referencia a eso en línea.
Niel de Beaudrap
Según tengo entendido, se usó [entre otros propósitos] para encontrar factores más pequeños de grandes números de prueba similares al tamiz de eratóstenes. Si se pasa el número grande, es "probablemente no compuesto" o "posiblemente primo" o "candidato principal". desafortunadamente internet no es muy bueno con referencias y orígenes históricos [incluso wikipedia], los libros son mejores. más detalles en la parte inferior de esta página , "tipos de problemas que Lehmer intentaba resolver" por el Dr. Mike Williams, curador jefe del Museo de Historia de la
Computación
1
la (s) máquina (s) ciertamente se pueden usar para implementar algoritmos probabilísticos - ¿Entonces? ¿A diferencia de otras máquinas que no pueden?
Jeffε
2
aunque la terminología en ese momento puede no haberse referido a "algoritmos probabilísticos", posiblemente se usó de esta manera en algunos casos - [cita requerida] Si tiene evidencia de que "posiblemente primar" es una declaración formal sobre la probabilidad, y no simplemente un Descripción heurística, por favor, cítala. De lo contrario, deja de especular.
Jeffε
n1∗n2∗n3∗nxx
-6

Estos son algunos casos de los comienzos antiguos e incluso antiguos / prehistóricos de conceptos relacionados con algoritmos aleatorios.

  • n/2

  • Los juegos de azar y los juegos de azar son muy antiguos. Según la teoría moderna, los juegos tienen fuertes similitudes, si no conexiones directas con los algoritmos. se sabe que los dados de juego / juego tienen al menos cinco milenios edad.

  • los griegos y romanos también tenían el concepto de dibujar pajitas donde la persona que dibujaba el popote más corto perdió. similar a los dados, es en cierto sentido el algoritmo más simple posible para hacer una elección aleatoria única.

  • divulgación completa, hay un tinte de sangrienta historia y conexión. en otra respuesta, MDB menciona la evolución . parte de la evolución es la selección natural que también tiene paralelos con la guerra humana , aparentemente una parte intrínseca de la evolución de las ciudades / sociedades humanas. en cierto sentido, una guerra es un crudo algoritmo semialeatorio para "algo" que los sociólogos e historiadores aún discuten sobre causas exactas. robo / saqueo? ¿distribuyendo recursos? ¿territorio? ¿poder politico? esclavos? (etc.) los romanos también tenían una práctica espeluznante llamada diezmado(¡la palabra moderna en realidad deriva en etimología de la antigua!) en la cual, como castigo por motín o cobardía, cada décimo soldado seleccionado al azar fue ejecutado por los soldados restantes. Puede parecer una práctica olvidada y atávica, pero parece tener cierto paralelismo con la ruleta rusa moderna , un cuasi-juego aleatorio "moderno" para el suicidio.

revs vzn
fuente
1
Eso no es lo que estoy preguntando; Estoy preguntando si razonaron sobre la frecuencia relativa de los números compuestos en la forma que usted describe.
Niel de Beaudrap
1
Me temo que no estoy interesado en generalidades vagas, y parece bastante obvio que no estamos de acuerdo fundamentalmente en qué es un "algoritmo". Estoy interesado en algo más que "fenómenos". De lo contrario, podemos citar todos los eventos de mecánica cuántica después del Big Bang como ejemplos de "algoritmos aleatorios", lo que hace que todo el tema sea trivial.
Niel de Beaudrap
1
"pregunta suave" no significa una pregunta con límites infinitamente flexibles; "panorama histórico" no es lo mismo que revisionismo histórico.
Niel de Beaudrap
2
Tu 'pista' para mí sobre la evolución, ni tu me echaste como perder el tiempo en una pregunta que no me gusta, ni tu evasión de mi pregunta anterior, fueron respetuosos. Y, de hecho, su especulación de que los griegos probablemente sabían de lo que está hablando, pero no se molestaron en escribir sobre eso, es exactamente una de las cosas a las que se puede referir el "revisionismo histórico". (Tal vez Arquímedes inventó la notación decimal, pero no se molestó en hacer ningún registro; después de todo, el Sand Reckoner está bastante cerca de la notación de lugar, y los griegos usaron un sistema similar a la base 10. Pero deberíamos tomar la idea en serio ? No.)
Niel de Beaudrap
1
Estoy de acuerdo en que es concebible, y que ni siquiera es muy descabellado, aparte, por supuesto, del hecho de que parece que no tenemos ningún registro de que los griegos hablen sobre la probabilidad per se. Pero si hay un registro real de ello, debería ser capaz de señalarlo. De lo contrario, es especulación, no historia.
Niel de Beaudrap
-7

JS menciona la teoría de números. A Fermat se le atribuye la prueba de primalidad de Fermat , un algoritmo probabilístico que data del siglo XVII y sirve como precursor de pruebas de primalidad más modernas como Solovay-Strassen y Miller-Rabin. [se necesitaría un historiador especializado en matemática y teoría de números para tratar de determinar exactamente lo que Fermat sabía al respecto versus el conocimiento moderno, que es mucho más completo sobre la estructura de sus pseudoprimos (falsos positivos), etc.]

vzn
fuente
2
¿Puedes citar a Fermat como haber usado su prueba como una forma de filtrar enteros seleccionados al azar como no primos (en lugar de solo una propiedad interesante que tienen los primos)? ¿O quizás citar a un autor temprano que sugiere hacerlo?
Niel de Beaudrap
Como se dijo, los detalles exactos se dejan mejor a un historiador profesional. sin embargo, tenga en cuenta [adenda; debería haber mencionado esto] el simple hecho histórico de que Fermat es acreditado como el coinventor fundador de la teoría de la probabilidad junto con Pascal, sentando las bases en una serie de cartas a mediados del siglo XVII.
vzn
2
No es realmente apropiado proponer respuestas basadas en lo que crees que alguien más podría mostrar. De nuevo, eso es especulación.
Niel de Beaudrap
3
@vzn: Si Fermat se hubiera dado cuenta de que el Pequeño Teorema de Fermat era una buena prueba de primalidad, habría calculado que el quinto número de Fermat no era primo . Esto no se hizo hasta que Euler lo tuvo en cuenta más de 60 años después de la muerte de Fermat.
Peter Shor
2
@vzn: [cita requerida]
Jeffε