Алгоритмическое

[spamsink]

Бродя по Википедии, набрел на список десяти лучших алгоритмов 20-го века по версии журнала Computing in Science & Engineering. Узнал об алгоритме Фергюсона-Форкейда, благодаря которому выяснили, что координата четвертой бифуркации на логистической диаграмме (там, где отдельные ветви уже практически сливаются в шум) есть корень уравнения 120-й степени с целыми коэффициентами, максимум абсолютных величин которых равен 257³⁰. Восхитился.

Но "если бы директором был я", то в мой список из неупомянутых непременно попали бы методы Лемпеля-Зива и Рида-Соломона. А в ваш?

Upd: текущий список номинантов (в произвольном порядке):

1. Boyer-Moore string search
2. Gouraud shading
3. Lempel-Ziv text compression
4. Reed-Solomon error correction
5. Fast Fourier transform
6. Quicksort, Heap sort, or Merge sort ???
7. RSA encryption

Comments

[ex-java-duk.livejournal.com]

Лемпель-Зив однозначно :)

[solomon2.livejournal.com]

Вероятностный алгоритм Рабина проверки на простоту рулит. Я про него узнал от самого Рабина.

[ygam.livejournal.com]

+1

[spamsink]

В смысле "рулит" или в смысле "узнал от самого Рабина"? :)

Мы пока не голосуем, а номинируем, так что приглашаю назвать еще одного кандидата.

[ivan-ghandhi.livejournal.com]

Вау, и Володя Рохлин там! Рад за него. Я не очень-то был с ним знаком.

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

[spamsink]

Дала ли эта Ира определение азартной игры, прежде чем запрещать?

[boris71.livejournal.com]

Demosaicing...

[cema.livejournal.com]

Очень уместный вопрос! :-)

[spamsink]

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

[arno1251.livejournal.com]

+1

[spamsink]

А свою собственную номинацию?

[arno1251.livejournal.com]

Недостаточно копенгаген для этого, и прислушиваюсь к мнениям людей понимающих :)

[raindog-2.livejournal.com]

А лучших - по важности или по красоте? Если по важности, то LZ. А если по красоте, то Burrows-Wheeler Transform.

[spamsink]

Если верить википедии, то В.В.Рохлин - внучатый племянник Корнея Чуковского!

[spamsink]

Хотелось бы, конечно, какое-то разумное сочетание. Что до BWT, то когда я в 1994 году читал их technical report, я от восхищения чуть до потолка не прыгал. Но по важности, пожалуй, не дотягивает до первой десятки.

[boris71.livejournal.com]

Кажется мне, что алгоритм быстрой сортировки, указанный в статье не имеет в своем названии имени. А можно было бы написать - алгоритм Байера для demosaicing (признаться, не знаю, как это по-русски)...

Собственно, мне сей алгоритм (Байера) представляется важным не с точки зрения его красоты, скорости или еще какой чисто-научной перспективы. Он просто чрезвычайно полезен и весьма распространен.

[spamsink]

Прошу номинировать что-нибудь, еще не упомянутое.

[spamsink]

Он полезен и распространен, но уж очень узкоспециален. Как и уже упомянутый Бэрроуза-Уилера, он, как мне кажется, не обладает необходимым для попадания в первую десятку universal appeal.

[boris71.livejournal.com]

Ну наше дело предложить... Ваше дело вы сами знаете... ;-)

[ygam.livejournal.com]

RSA

[spamsink]

Если вместо Rabin's primality test, как объемлющий его - принимается. Я обновил запись, добавив список "номинантов". Из каких бы областей еще три взять?

[sab123.livejournal.com]

На самом деле Лемпель-Зива в этот список можно писать только вместе с Уэлчем. А без него у них был полнейший ужас-ужас, на практике почти что неприменимый.

[spamsink]

Вот тут я позволю себе не согласиться. LZW, хоть и реализуется проще и работает быстрее, отвратительно ведет себя на данных, близких к случайным. А все современные архиваторы на LZ-алгоритмах (zip/gzip, rar) пользуются дериватами оригинальной идеи.

[sab123.livejournal.com]

У Уэлча имеется две отдельных идеи:

1. Построение словаря виденных подстрок
2. Реализация этого словаря через хэш-таблицу

Лемпель и Зив же строили дерево и потом странным образом кодировали представление его узлов в числа. Разве кто-то все еще строит деревья? То есть, я сам на gzip/rar не смотрел, не знаю. Но алгоритм, который в популярных книжках рассказывается как LZ, на самом деле - LZW.

[spamsink]

LZW - это конкретная, пригодная для хардвера, реализация LZ78, в отличие от LZ77, которым пользуются нынешние программы.

http://en.wikipedia.org/wiki/LZ77_and_LZ78

[sab123.livejournal.com]

А, значит они еще одну бумагу написали в 1978 году. Я только патент ихний читал от 1977 года, и он на удивление невнятный и путанный.

Извините, за оффтоп.

[shalti-bolti.livejournal.com]

... смотрю, что тема про алгоритмы.
Придумал алгоритм факторизации - предлагаю посмотреть (http://shalti-bolti.livejournal.com/130077.html).