Algorithmes probabilistes (randomisés) avant l'apparition de l'informatique «moderne»

27

Edit: J'ai choisi la réponse avec le score le plus élevé avant le 06 décembre 2012.

C'est une question douce.

Le concept d'algorithmes (déterministes) remonte à la Colombie-Britannique. Qu'en est-il des algorithmes probabilistes?

Dans cette entrée wiki , l'algorithme de Rabin pour le problème de paire la plus proche en géométrie de calcul a été donné comme le premier algorithme randomisé (année ???). Lipton a présenté l'algorithme de Rabin comme le début de l'ère moderne des algorithmes aléatoires ici , mais pas comme le premier. Je connais également de nombreux algorithmes pour les automates finis probabilistes (un modèle de calcul très simple) découverts au cours des années 1960.

Connaissez-vous des algorithmes (ou méthodes) probabilistes / randomisés avant même les années 1960?

ou

Quelle découverte peut être considérée comme le premier algorithme probabiliste / randomisé?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
la source
25
L'idée séculaire de goûter une cuillerée de soupe bouillante pour vérifier si elle a bon goût est essentiellement un échantillonnage aléatoire, un algorithme probabiliste avec des garanties prouvables.
arnab
3
L'algorithme de Rabin a été publié en 1976, longtemps après que l'informatique "moderne" ait été bien établie.
Jeffε
Pourriez-vous peut-être préciser s'il y a des critères que vous aimeriez imposer aux "algorithmes", afin de préciser si vous pensez par exemple que les phénomènes naturels qui sont antérieurs à l'humanité de milliards d'années représentent des "algorithmes", comme le suggèrent certaines réponses au dessous de?
Niel de Beaudrap
@NieldeBeaudrap: Je pensais à des algorithmes mathématiquement bien définis. (Mais, personnellement, je aime Arnab la réponse de très :))
Abuzer Yakaryilmaz

Réponses:

33

Ceci est discuté un peu dans mon article avec HC Williams, "Factoring Integers before Computers"

Dans un article de 1917, HC Pocklington a discuté d'un algorithme pour trouver sqrt (a), modulo p, qui dépendait du choix des éléments au hasard pour obtenir un non-résidu d'une certaine forme. Dans ce document, il a dit: "Nous devons le faire [trouver le non-résidu] par procès, en utilisant la loi de la réciprocité quadratique, qui est un défaut de la méthode. Mais comme pour chaque valeur de la moitié, les valeurs de t conviennent, il ne devrait pas être difficile d'en trouver un. "

C'est donc l'une des premières mentions explicites d'un algorithme randomisé.

Jeffrey Shallit
la source
3
Ceci est une très belle référence. L'algorithme de Pocklington a-t-il depuis été dérandomisé? Tangentiellement, j'aime votre travail - à la fois dans et hors de CS - en particulier votre algorithme pour la conjecture de Bachet (le papier était difficile à trouver cependant!) Mais aussi votre travail sur les libertés civiles. Avez-vous regardé "Mr. Death" d'Errol Morris?
Ross Snider
intéressant. cela rappelle les tests de primalité randomisés
Sasho Nikolov
3
Et un algorithme de Las Vegas aussi! Belle référence.
David Eppstein
Très belle référence.
Jérémie
Parlant de l'affacturage avant les ordinateurs, quelqu'un sait-il ce que Lehmer savait sur l'algorithme de Pocklington ou tout autre algorithme randomisé, ou si Lehmer l'a réellement implémenté sur son ordinateur d'affacturage par tamisage ? les deux ont apparemment un lien avec le test de primalité de Pocklington-Lehmer selon wikipedia
vzn
28

π

vzn
la source
8
En fait, cela est lié à une question que j'ai posée . Personne ne sait exactement qui a conçu l'algorithme que beaucoup de gens considèrent comme l'aiguille de Buffon de nos jours.
Jérémie
dit plus exactement - il y a un algorithme de l'aiguille de Buffon clair qui implique de laisser tomber des aiguilles sur les rayures, et un algorithme "point aléatoire vs cercle" apparemment très différent comme vous le mentionnez dans cette question que certaines personnes semblent attribuer incorrectement à Buffon, avec différents, plus origines modernes mais incertaines.
vzn
19

L' algorithme Metropolis – Hastings a été publié en 1953 et remonte plus tôt au projet Manhattan, bien avant Rabin. Comme la plupart des premières méthodes randomisées données dans d'autres réponses, il s'agit d'un algorithme de Monte Carlo.

Est-il possible que l'affirmation sur la page Wikipedia soit une forme tronquée de l'affirmation selon laquelle Rabin's était le premier algorithme de Las Vegas ?

David Eppstein
la source
11

La courbe / distribution normale gaussienne des statistiques peut être "calculée" par de nombreux processus physiques très simples. L'une des plus simples est une carte avec un réseau de broches dans une grille triangulaire (également connue sous le nom de "boîte de Galton" datant des années 1800) où les broches sont décalées d'une demi-distance carrée sur des lignes alternées. En laissant tomber les balles à plusieurs reprises de la même position, les balles se déplacent au hasard à gauche ou à droite avec une probabilité de 0,5. La distribution cumulative enregistrée aux positions inférieures donne la courbe gaussienne / normale.

vzn
la source
+1 simplement parce que je suis en train de concevoir un logo pour notre groupe de recherche statistique et que la Galton Box était notre première idée (mais s'avère trop complexe pour un logo).
Konrad Rudolph
10

À mon avis, l'évolution naturelle est un bon algorithme probabiliste plutôt ancien :-)

Marzio De Biasi
la source
1
+1 bien que la description du processus comme probabiliste nous soit beaucoup plus récente. ;-)
Konrad Rudolph
7
"Algorithme" suggère qu'il y a un problème qu'il essaie de résoudre; mais ce n'est pas le cas. Ce n'est même pas "essayer" de faire des animaux qui survivent mieux; créer des animaux adaptés à son environnement n'est qu'un sous-produit (qui n'est pas toujours atteint, comme le montrent les événements d'extinction et d'extinction de masse). À cet égard, l'évolution n'est pas plus un algorithme que la gravité; c'est juste cette chose qui se produit.
Niel de Beaudrap
MDB est mort! L'évolution est un algorithme génétique qui sélectionne la forme physique évolutive et la science est toujours en train de rattraper toutes les implications de cela ... c'est-à-dire que c'est un domaine de recherche actif. cela n'a pas été souligné ni apprécié, mais le succès phénoménal des AG en CS est en fait une preuve mathématique / scientifique solide de la réalité de la théorie de l'évolution biologique. cependant, admettez qu'il est définitivement différent des autres "algorithmes" à certains égards.
vzn
2
@vzn: un "algorithme génétique", tout d'abord, sélectionne une fonction de fitness que nous imposons dans un but précis. Nous utilisons l'évolution comme un outil pour faire quelque chose dans ce cas. Mais cela ne signifie pas que l'évolution biologique est un algorithme pour faire quoi que ce soit. En utilisant à nouveau l'analogie de la gravité, y a-t-il un sens significatif dans lequel toutes les chutes d'eau sont des algorithmes, simplement parce que nous utilisons parfois des chutes d'eau pour produire de l'électricité?
Niel de Beaudrap
4
@vzn: J'affirme simplement qu '"un algorithme" doit impliquer des paramètres de probabilité de succès bien définis, sans parler de la nécessité d'un agent qui le réalise . Le seul «agent» qui pourrait être considéré comme réalisant une «évolution» serait tout un écosystème. Que faut-il dire que l'écosystème «tente» d'atteindre? Je dirais tout aussi volontiers que vous anthropomorphisez la nature. Je demande seulement que «l'application d'un algorithme» implique une certaine quantité d'intentionnalité orientée vers un but, appliquée par les humains ou non. Dans quel sens un processus sans objectif peut-il représenter un "algorithme"?
Niel de Beaudrap
6

Il existe un article sur les algorithmes randomisés dans les cultures «primitives» .

Utiliser des oracles (par exemple, des os de poulet, des pierres) pour décider où chasser peut être considéré comme un algorithme aléatoire. On peut affirmer que la randomisation des terrains de chasse empêche l'adaptation du gibier et la chasse excessive.

adrianN
la source
0

l'un des articles «miracle» d'Einsteins 1905 portait sur le mouvement brownien , un exemple physique classique d'une marche aléatoire et donne une formule (c'est-à-dire, fondamentalement un algorithme, si le processus physique est «l'ordinateur») pour estimer / calculer la particule (molécule) diamètre étant donné d'autres constantes physiques connues et l'observation / mesure du déplacement (aléatoire) des particules dans le temps. cet article a également servi de première preuve théorique / expérimentale / fondamentale pour la théorie atomique de la matière.

vzn
la source
4
Comme pour l'évolution: bien que le mouvement puisse être aléatoire et modélisé par une marche aléatoire, quel algorithme cela représente-t-il? Bien que certains algorithmes utilisent des promenades aléatoires, cela ne signifie pas que toutes les promenades aléatoires représentent des algorithmes (pas plus que n'importe quelle chaîne de mots en anglais ne représente la prose simplement parce que toute la prose anglaise est constituée de mots en anglais).
Niel de Beaudrap
-4

nini

la machine présente également une certaine similitude avec le moteur différentiel Babbage (~ 1830). il n'est pas tout à fait inconcevable que Babbage ou Lovelace aient pu imaginer quelque chose de similaire aux algorithmes probabilistes. la ou les machines peuvent certainement être utilisées pour implémenter des algorithmes probabilistes, empruntant la théorie moderne et la superposant au passé.

[1] Machine d'affacturage Lehmer

[2] Moteur Babbage


Lehmer mod n & machine d'affacturage

vzn
la source
1
Pouvez-vous décrire le sens dans lequel il a calculé les réponses probabilistes pour les grands nombres? Une recherche rapide ne me semble pas trouver de références à cela en ligne.
Niel de Beaudrap du
à ma connaissance, il a été utilisé [entre autres] pour trouver de plus petits facteurs de grands nombres de tests similaires au tamis des ératosthènes. si le grand nombre réussit, c'est "probablement pas composite" ou "éventuellement premier" ou "premier candidat". malheureusement, Internet n'est pas très bon avec des références et origines historiques [même wikipedia], les livres sont meilleurs. plus de détails en bas de cette page , "types de problèmes que Lehmer tentait de résoudre" par Dr mike williams, conservateur en chef du musée d'histoire de l'ordinateur de CA
vzn
1
la ou les machines peuvent certainement être utilisées pour implémenter des algorithmes probabilistes - Alors? Contrairement à d'autres machines qui ne le peuvent pas?
Jeffε
2
bien que la terminologie au moment peut - être pas fait référence aux « algorithmes probabilistes » , il était peut - être utilisé de cette façon , dans certains cas - [citation nécessaire] Si vous avez des preuves que « peut - être le premier » est une déclaration formelle de la probabilité, et non pas simplement une description heuristique, veuillez la citer. Sinon, arrêtez de spéculer.
Jeffε
n1∗n2∗n3∗nxx
-6

voici quelques cas des débuts anciens et même anciens / préhistoriques de concepts liés aux algorithmes randomisés.

  • n/2

  • les jeux de hasard et de jeu sont très anciens. de la théorie moderne, les jeux ont de fortes similitudes sinon des connexions directes aux algorithmes. les dés de jeu / jeu sont connus pour avoir au moins cinq millénaires .

  • les Grecs et les Romains avaient également le concept de dessiner des pailles où la personne tirant la paille la plus courte perdait. semblable aux dés, c'est en quelque sorte l'algorithme le plus simple possible pour faire un seul choix aléatoire.

  • divulgation complète, il y a une teinte d'histoire sanglante et de connexion. dans une autre réponse, MDB mentionne l' évolution . une partie de l'évolution est la sélection naturelle qui a également des parallèles avec la guerre humaine - apparemment une partie intrinsèque de l'évolution des villes / sociétés humaines. dans un sens, une guerre est un algorithme semi-aléatoire grossier pour «quelque chose» que les sociologues et les historiens discutent encore sur les causes exactes. vol / pillage? allouer des ressources? territoire? pouvoir politique? des esclaves? (etc.) les Romains avaient également une pratique macabre appelée décimation(le mot moderne dérive en fait dans l'étymologie de l'ancien!) dans lequel, comme punition pour mutinerie ou lâcheté, chaque 10e soldat choisi au hasard a été exécuté par les soldats restants. cela peut sembler une pratique oubliée et atavique, mais cela semble avoir un parallèle avec la roulette russe moderne , un quasi-jeu aléatoire "moderne" pour le suicide.

vzn
la source
1
Ce n'est pas ce que je demande; Je demande s'ils ont raisonné sur la fréquence relative des nombres composites de la manière que vous décrivez.
Niel de Beaudrap
1
Je crains de ne pas m'intéresser aux vagues généralités, et il semble assez évident que nous ne sommes pas fondamentalement d'accord sur ce qu'est un «algorithme». Je m'intéresse à plus que des "phénomènes". Sinon, nous pouvons aussi citer tous les événements de la mécanique quantique après le Big Bang comme exemples d '«algorithmes randomisés», ce qui rend l'ensemble du sujet trivial.
Niel de Beaudrap
1
«question douce» ne signifie pas une question aux limites infiniment flexibles; "aperçu historique" n'est pas la même chose que le révisionnisme historique.
Niel de Beaudrap
2
Votre «allusion» à moi à propos de l'évolution, ni le fait que vous me jetiez comme du temps perdu sur une question que je n'aime pas, ni votre évasion de ma question précédente, étaient respectueux. Et en fait, votre spéculation selon laquelle les Grecs savaient probablement de quoi vous parliez mais n'ont pas pris la peine d'écrire à ce sujet est exactement l'une des choses auxquelles le «révisionnisme historique» peut se référer. (Peut-être qu'Archimède a inventé la notation décimale, mais n'a pas pris la peine de faire un enregistrement; après tout, le Sand Reckoner est assez proche de la notation de lieu, et les Grecs ont utilisé un système de type 10. Mais devrions-nous prendre l'idée au sérieux ? Non.)
Niel de Beaudrap
1
Je suis d'accord que c'est réalisable, et que ce n'est même pas très farfelu - à part, bien sûr, le fait que nous ne semblons pas avoir de cas où les Grecs parlent de probabilité en soi. Mais s'il existe un enregistrement réel de celui-ci, vous devriez pouvoir le signaler. Sinon, c'est de la spéculation, pas de l'histoire.
Niel de Beaudrap
-7

JS mentionne la théorie des nombres. Fermat est crédité du test de primalité Fermat , un algorithme probabiliste qui remonte aux années 1600 et sert de précurseur à des tests de primalité plus modernes tels que Solovay-Strassen et Miller-Rabin. [il faudrait un historien spécialisé en mathématiques et en théorie des nombres pour essayer de cerner exactement ce que Fermat en savait par rapport aux connaissances modernes qui sont beaucoup plus complètes sur la structure de ses pseudoprimes (faux positifs) etc.]

vzn
la source
2
Pouvez-vous citer Fermat comme ayant utilisé son test comme un moyen de filtrer les entiers sélectionnés au hasard comme des non-nombres premiers (par opposition à une propriété intéressante que les nombres premiers ont)? Ou peut-être citer un des premiers auteurs qui suggère de le faire?
Niel de Beaudrap
comme indiqué, les détails exacts sont mieux laissés à un historien professionnel. notez cependant [addendum; aurait dû mentionner cela] le simple fait historique que fermat est crédité comme le co - inventeur fondateur de la théorie des probabilités avec pascal, jetant les bases d'une série de lettres au milieu des années 1600.
vzn
2
il n'est pas vraiment approprié de proposer des réponses basées sur ce que vous croyez que quelqu'un d'autre pourrait montrer. Encore une fois, c'est de la spéculation.
Niel de Beaudrap
3
@vzn: Si Fermat avait réalisé que le petit théorème de Fermat était un bon test de primalité, il aurait calculé que le 5ème nombre de Fermat n'était pas premier . Cela n'a pas été fait jusqu'à ce qu'Euler en tienne compte plus de 60 ans après la mort de Fermat.
Peter Shor
2
@vzn: [citation nécessaire]
Jeffε