Вероятностные алгоритмы: какие бывают и где найти полный их список?

Question

[Сергей]

Вот есть например:
Фильтр Блума
или
Марковские цепи

А где можно посмотреть полный список подобных разработок ?
Интересует прежде всего задачи хранения, кластеризации и классификации информации.

Answer 1

[Сергей]

Здесь буду собирать ссылки на вероятностные алгоритмы:
1. Фильтр блума https://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%BB%D...
2. MinHash habrahabr.ru/post/115147
3. LogLog: находим число уникальных элементов -- habrahabr.ru/post/119852
3.1 HyperLogLog
4. Поиск похожих документов с MinHash + LHS: habrahabr.ru/post/250673
5. https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch -- приближенный сбор частот событий в потоке.
6. Алгоритм Рабина — Карпа: поиск подстрок в строке через хеширование. https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D...

https://en.wikipedia.org/wiki/Category:Probabilist...

Answer 2

[man0xff]

вот что нашел https://gist.github.com/debasishg/8172796

в свое время тоже искал. ключевое слово - streaming algorithms, sketching data structures

Comments

[Сергей]

Полезно. Спасибо.

Answer 3

[afiskon]

В действительности очень многие алгоритмы имеют вероятностный характер. Даже TCP и UDP пакеты имеют контрольную сумму, которая помогает найти ошибку только с некоторой (довольно большой) вероятностью. Еще из той же серии можете посмотреть распределенные алгоритмы - Gossip, Raft и так далее. Из менее сетевых - алгоритмы сжатия (с потерями и без), генетические алгоритмы, нейронные сети.

Comments

[Сергей]

Я на самом деле, возможно, немного не точно сформулировал вопрос. Меня интересуют прежде всего алгоритмы на подобии фильтра Блума, например:
вероятностный счетчик ( habrahabr.ru/post/208268 ) и т.п. т.е. все таки больше применение к теории информации, хешированию и т.п. нежели к проверке стат гипотез и т.п.
Вот что еще в этой области можно найти ?

Ген алгоритмы, нейронные сети, сжатие с потерями - это немного не то, это сугубо заточенные под задачу вещи.

Answer 4

[inggris]

есть вот такое место:
discopal.ispras.ru/%D0%91%D0%BB%D0%BE%D0%B3:Advanc...

вообще это страничка одного курса в московском Физтехе, среди материалов есть кое-чего оп вероятностным алгоритмам