Вероятностные (рандомизированные) алгоритмы до появления «современной» информатики

27

Изменить: я выбираю ответ с наибольшим количеством баллов до 6 декабря 2012 года.

Это мягкий вопрос.

Концепция (детерминированных) алгоритмов восходит к BC. Как насчет вероятностных алгоритмов?

В этой статье в вики в качестве первого рандомизированного алгоритма (год ???) был задан алгоритм Рабина для задачи ближайшей пары в вычислительной геометрии. Lipton представил алгоритм Рабина как начало современной эпохи случайных алгоритмов здесь , но не так , как первый. Я также знаю много алгоритмов для вероятностных конечных автоматов (очень простая вычислительная модель), открытых в 1960-х годах.

Знаете ли вы какие-либо вероятностные / рандомизированные алгоритмы (или метод) еще до 1960-х годов?

или

Какой вывод можно рассматривать как первый вероятностный / рандомизированный алгоритм?

ds.algorithms reference-request big-list randomized-algorithms ho.history-overview Abuzer Yakaryilmaz
источник
25
Вековая идея дегустации ложки кипящего супа для проверки правильности вкуса - это, по сути, случайная выборка, вероятностный алгоритм с доказуемыми гарантиями.
Арнаб
3
Алгоритм Рабина был опубликован в 1976 году, задолго до того, как «современная» информатика стала общепризнанной.
Джеффс
Не могли бы вы уточнить, существуют ли какие-либо критерии, которые вы хотели бы навязать «алгоритмам», чтобы уточнить, думаете ли вы, например, что природные явления, которые предшествуют человечеству на миллиарды лет, представляют собой «алгоритмы», как предлагается в некоторых ответах ниже?
Ниль де Бодрап,
@NieldeBeaudrap: То, что я думаю, было математически хорошо определенными алгоритмами. (Но лично мне очень нравится ответ Арнаба :))
Abuzer Yakaryilmaz

Ответы:

33

Это немного обсуждается в моей статье с Х. К. Уильямсом, "Факторинг целых чисел перед компьютерами"

В статье 1917 года Х. К. Поклингтон обсудил алгоритм нахождения sqrt (a) по модулю p, который зависел от случайного выбора элементов для получения нерезидентного числа определенной формы. В нем он сказал: «Мы должны сделать это [найти нечетный остаток] путем испытания, используя закон квадратичной взаимности, который является недостатком метода. Но что касается каждого значения u, то половина значений t подходит, Там не должно быть никаких трудностей в поиске одного ".

Так что это одно из первых явных упоминаний рандомизированного алгоритма.

Джеффри Шаллит
источник
3
Это действительно хорошая ссылка. Был ли алгоритм Поклингтона с тех пор дерандомизирован? Тангенциально, я люблю вашу работу - как в CS, так и вне ее - в частности, ваш алгоритм гипотезы Баше (хотя в статье трудно было найти копию!), Но также и ваши гражданские свободы. Вы смотрели «Мистер Смерть» Эррола Морриса?
Росс Снайдер
интересный. это напоминает рандомизированное тестирование простоты
Сашо Николов
3
И алгоритм Лас-Вегаса тоже! Хорошая ссылка.
Дэвид Эппштейн
Очень хорошая ссылка.
Жереми
Говоря о факторинге перед компьютерами, кто-нибудь знает, что Лемер знал об алгоритме Поклингтона или о любых других рандомизированных алгоритмах, или Лемер вообще когда-либо реализовывал его на своем ситовом факторинге ? эти два, очевидно, имеют какое-то отношение к тесту первичности Поклингтона-Лемера согласно Википедии
vzn
28

Алгоритм Буффонса для оценки , в основном метод Монте-Карло , был опубликован в 1777 году. Обратите внимание, что методы Монте-Карло датируются 1940-ми годами в рамках проекта атомной бомбы США «Манхэттен» и были изобретены Уламом, фон Нейманом и Метрополисом.π

ВЗН
источник
8
На самом деле это связано с вопросом, который я задал . Никто точно не знает, кто разработал алгоритм, который многие люди считают иглой Буффона в наши дни.
Жереми
точнее говоря, есть четкий алгоритм иглы Буффона, который включает в себя бросание игл на полоски, и, очевидно, сильно отличающийся алгоритм «случайная точка против круга», как вы упоминаете в этом вопросе, который, как кажется, некоторые люди неправильно приписывают Буффону, с другой, более современное, но неопределенное происхождение.
vzn
19

Алгоритм Метрополиса-Гастингса был опубликован в 1953 году и датируется ранее Манхэттенского проекта, задолго до Рабина. Как и многие ранние рандомизированные методы, приведенные в других ответах, это алгоритм Монте-Карло.

Возможно ли, что утверждение на странице Википедии является искаженной формой утверждения о том, что Рабин был первым алгоритмом Лас-Вегаса ?

Дэвид Эппштейн
источник
11

Gaussian нормальное кривое / распределение статистики может быть «вычислено» многими очень простыми физическими процессами. Одним из самых простых является доска с массивом штифтов в треугольной сетке (также известная как «ящик Галтона», датируемая 1800-ми годами), где штифты смещены на 1/2 квадратного расстояния в чередующихся рядах. Сбрасывая шарики несколько раз из одной и той же позиции, шарики случайным образом смещаются влево или вправо с вероятностью 0,5. Кумулятивное распределение, записанное в нижних позициях, дает кривую Гаусса / нормаль.

взн
источник
+1 только потому, что я в настоящее время разрабатываю логотип для нашей исследовательской группы по статистике, и Galton Box была нашей первой идеей (но оказывается слишком сложной для логотипа).
Конрад Рудольф
10

На мой взгляд, естественная эволюция - это хороший и довольно старый вероятностный алгоритм :-)

Марцио Де Биаси
источник
1
+1 хотя описание процесса как вероятностного нам гораздо более свежее. ;-)
Конрад Рудольф
7
«Алгоритм» предполагает, что существует проблема, которую он пытается решить; но это не так. Это даже не «попытка» сделать животных, которые лучше выживают; создание животных, адаптированных к окружающей среде, является просто побочным продуктом (который не всегда достигается, как показывают события вымирания и массового вымирания). В этом отношении эволюция не более алгоритм, чем гравитация; это как раз то, что происходит.
Ниль де Бёдрап,
MDB мертв! Эволюция - это генетический алгоритм, который выбирает эволюционное приспособление, и наука все еще догоняет все последствия этого ... т.е. его активная область исследований. на это не указывалось много или широкое признание, но феноменальный успех ГА в КС на самом деле является сильным математическим / научным доказательством реальности теории биологической эволюции. однако, признайте, что он определенно отличается от других «алгоритмов» в некоторых ключевых аспектах.
августа
2
@vzn: «генетический алгоритм», прежде всего, выбирает для фитнес-функции, которую мы навязываем для конкретной цели. Мы используем эволюцию как инструмент, чтобы сделать что-то в этом случае. Но это не значит, что биологическая эволюция - это алгоритм для чего-либо. Если снова использовать аналогию гравитации, есть ли смысл в том, что все водопады являются алгоритмами, просто потому, что мы иногда используем водопады для производства электричества?
Ниль де Бодрап,
4
@vzn: Я просто утверждаю, что «алгоритм» должен включать в себя четко определенные параметры вероятности успеха, не говоря уже о том, что должен быть агент, который его выполняет . Единственным «агентом», который, как можно сказать, осуществляет «эволюцию», была бы целая экосистема. Что мы должны сказать, что экосистема "пытается" достичь? Я бы с готовностью сказал, что вы антропоморфизирующая натура. Я только требую, чтобы «применение алгоритма» повлекло за собой некоторую целенаправленную интенциональность, применяемую людьми или нет. В каком смысле процесс без цели может представлять собой «алгоритм»?
Ниль де Бёдрап,
6

Есть статья о рандомизированных алгоритмах в «примитивных» культурах .

Использование оракулов (например, куриных костей, камней) для выбора места для охоты можно рассматривать как рандомизированный алгоритм. Можно утверждать, что рандомизация охотничьих угодий предотвращает адаптацию игры и чрезмерную охоту.

adrianN
источник
0

одна из «чудесных» работ Эйнштейна 1905 г. была посвящена броуновскому движению , классическому физическому примеру случайного блуждания, и дает формулу (т. е. в основном алгоритм, если физический процесс является «компьютером») для оценки / вычисления частицы (молекулы) диаметр с учетом других известных физических констант и наблюдения / измерения (случайного) смещения частиц во времени. эта статья также послужила ранним теоретическим / экспериментальным / основополагающим доказательством атомной теории материи.

ВЗН
источник
4
Как и в случае с эволюцией: хотя движение может быть случайным и моделироваться случайным блужданием, какой алгоритм это представляет? Хотя некоторые алгоритмы используют случайные обходы, это не означает, что все случайные обходы представляют собой алгоритмы (больше, чем любая строка слов на английском языке представляет прозу только потому, что вся английская проза состоит из слов на английском языке).
Ниль де Бодрап,
-4

nini

машина также имеет некоторое сходство с дифференциальным двигателем Бэббиджа (~ 1830-е годы). не исключено, что Бэббидж или Лавлейс могли представить что-то похожее на вероятностные алгоритмы. машина (ы), безусловно, может быть использоваться для реализации вероятностных алгоритмов, заимствуя современную теорию и накладывая ее на прошлое.

[1] Лемер-факторинг

[2] Бэббидж движок


Lehmer mod n & factoring machine

оборота взн
источник
1
Можете ли вы описать смысл вычисления вероятностных ответов для больших чисел? Быстрый поиск не кажется, что я не могу найти ссылки на это онлайн.
Ниль де Бёдрап,
Насколько я понимаю, он использовался [среди других целей], чтобы найти меньшие факторы больших количеств тестов, аналогичные решету из эратосфена. если пропущено большое число, оно «вероятно, не составное», «возможно, простое» или «главный кандидат». к сожалению, интернет не очень хорош с историческими ссылками и происхождением [даже википедии], книги лучше. подробности внизу этой страницы , «типы проблем, которые пытался решить Лемер », доктор Майк Уильямс, главный куратор музея компьютерной истории CA
vzn
1
машина (ы), безусловно, может быть использована для реализации вероятностных алгоритмов - так? В отличие от других машин, которые не могут?
Джеффс
2
хотя терминология того времени, возможно, не относилась к «вероятностным алгоритмам», в некоторых случаях она могла использоваться таким образом - [цитата необходима] Если у вас есть доказательства того, что «возможно простое» является формальным утверждением о вероятности, а не просто эвристическое описание, пожалуйста, приведите это. В противном случае, пожалуйста, прекратите спекулировать.
Джеффс
n1∗n2∗n3∗nxx на машине, и сделал какое-то разумное наблюдение за результатом, не обязательно записанным .... мне кажется правдоподобным ....
vzn
-6

Вот несколько случаев раннего и даже древнего / доисторического начала концепций, связанных с рандомизированными алгоритмами.

  • n/2

  • азартные игры и азартные игры являются очень древними. из современной теории игры имеют сильное сходство, если не прямые связи с алгоритмами. Известно, что игральные / игровые кости имеют возраст не менее пяти тысячелетий .

  • у греков и римлян также была концепция рисования соломинок, когда человек, вытягивавший самую короткую соломку, терял. Подобно игре в кости, в некотором смысле это самый простой из возможных алгоритмов, позволяющий сделать один случайный выбор.

  • полное раскрытие, есть оттенок кровавой истории и связи. в другом ответе MDB упоминает эволюцию . Часть эволюции - это естественный отбор, который также имеет параллели с человеческой войной - по-видимому, неотъемлемая часть эволюции человеческих городов / обществ. в некотором смысле война - это грубый полуслучайный алгоритм «чего-то», который социологи и историки до сих пор спорят о точных причинах. кражи / грабежи? выделять ресурсы? территория? политическая сила? рабы? (и т. д.) у римлян также была ужасная практика, называемая уничтожением(современное слово фактически происходит из этимологии от древнего!), в котором в качестве наказания за мятеж или трусость каждый 10-й солдат, выбранный случайным образом, был казнен оставшимися солдатами. Это может показаться забытой и атавистической практикой, но похоже, что она имеет некоторую параллель с современной русской рулеткой , «современной» рандомизированной квазиигрой для самоубийства.

оборота взн
источник
1
Это не то, о чем я спрашиваю; Я спрашиваю, рассуждали ли они об относительной частоте составных чисел так, как вы описываете.
Ниль де Бодрап,
1
Боюсь, меня не интересуют смутные обобщения, и кажется совершенно очевидным, что мы принципиально не согласны с тем, что такое «алгоритм». Я заинтересован не только в «явлениях». В противном случае мы можем также привести все квантово-механические события после Большого взрыва в качестве примеров «рандомизированных алгоритмов», что делает весь предмет тривиальным.
Ниль де Бёдрап,
1
«мягкий вопрос» не означает вопрос с бесконечно гибкими границами; «Исторический обзор» - это не то же самое, что исторический ревизионизм.
Ниль де Бёдрап,
2
Ваш «намек» на эволюцию, ни то, что вы тратите меня на трату времени на вопрос, который мне не нравится, ни ваше уклонение от моего предыдущего вопроса, были почтительными. И на самом деле, ваши предположения о том, что греки, вероятно, знали о том, о чем вы говорите, но не удосужились написать об этом, - это как раз та вещь, на которую может ссылаться «исторический ревизионизм». (Возможно, Архимед изобрел десятичную нотацию, но не удосужился сделать какую-либо запись; в конце концов, Sand Reckoner довольно близок к позиции нотации, и греки действительно использовали систему, подобную Base-10. Но стоит ли нам серьезно относиться к этой идее? ? Нет.)
Ниль де Бёдрап,
1
Я согласен, что это возможно, и что это даже не очень надумано - кроме, конечно, того факта, что у нас, кажется, нет никаких записей о греках, говорящих о вероятности как таковой. Но если есть реальная запись об этом, вы должны быть в состоянии указать на это. В противном случае, это предположение, а не история.
Ниль де Бодрап,
-7

JS упоминает теорию чисел. Ферма приписывают с критерий примитивности Ферма , вероятностный алгоритм, который датируется 1600-ми годами и служит предшественником более современных тестов примитивности, таких как Соловей-Штрассен и Миллер-Рабин. [понадобился бы историк, специализирующийся на математике и теории чисел, чтобы попытаться точно определить, что Ферма знал об этом, по сравнению с современными знаниями, которые гораздо более полны о структуре его псевдопреобразований (ложных срабатываний) и т. д.]

ВЗН
источник
2
Можете ли вы назвать Ферма как использовавшего его тест как способ отфильтровывать случайно выбранные целые числа как не простые числа (в отличие от просто интересного свойства, которым обладают простые числа)? Или, может быть, привести раннего автора, который предлагает это сделать?
Ниль де Бёдрап,
как заявлено, точные детали лучше оставить профессиональному историку. однако обратите внимание [приложение; должен был упомянуть это] простой исторический факт, что ферма считают основателем теории вероятностей наряду с паскалем, заложив основу в серии писем в середине 1600-х годов.
2012 г.
2
на самом деле неуместно предлагать ответы, основываясь на том, что, по вашему мнению, может показать кто-то другой. Опять же, это спекуляция.
Ниль де Бёдрап,
3
@vzn: Если бы Фермат понял, что маленькая теорема Ферма является хорошим тестом на простоту, он бы рассчитал, что 5-е число Ферма не является простым . Это не было сделано до тех пор, пока Эйлер не учел это более чем через 60 лет после смерти Ферма.
Питер Шор
2
@vzn: [необходима цитата]
Джеффс