Каковы основные алгоритмы для человечества в последние десятилетия? [закрыто]

40

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

Я думал, что это хорошее общее знание для разработчика, чтобы знать о.

Обновление:
если возможно, пожалуйста, сохраните ответ на конкретный алгоритм программирования .
Я хотел бы получить список самых важных, только один алгоритм на ответ.
Пожалуйста, рассмотрите, чтобы заявить, почему алгоритм важен и важен ...

algorithms problem-solving knowledge Amir Rezaei
источник
2
Это закрыто, потому что (пока) четыре человека считают это «не реальным вопросом», вероятно потому, что у нас нет никакой реальной идеи, что в отдельности является важным алгоритмом программирования.
Дэвид Торнли
2
Это может быть не по теме, но это реальный вопрос.
Джереми
1
+1 Хороший вопрос. Я предлагаю повторно спросить об этом на cstheory.stackexchange.com
Александр Левчук
1
Почему вы отвечаете на свои вопросы? Несколько раз?
2
Нет неправильных ответов + неограниченное количество ответов + однозначный комментарий с просьбой «один на ответ» + автор публикует несколько своих собственных ответов = случай из неконструктивного вопроса в учебнике. Я знаю, что он старый, но давайте, пожалуйста, закроем это.
Aaronaught

Ответы:

59

Шифрование с открытым / закрытым ключом чертовски важно. Интернет-торговля не была бы столь распространенной без нее.

Джереми
источник
4
+1 и добавить к вашему ответу RSA.
Санге
Существует целая группа алгоритмов и лучших практик, связанных с превращением криптографических кодов (таких как RSA) в практические решения.
Донал Феллоуз
37

Алгоритм Дейкстры

Алгоритм существует в каждом маршрутизаторе в мире для определения наилучшего маршрута между двумя узлами в сети.

Амир Резаи
источник
Вы уверены? Большинство маршрутизаторов либо знают, что IP-номер принадлежит ему, и перенаправляет его на компьютер в локальной сети, либо знают маршрутизатор, который знает лучше - маршрутизатор по умолчанию - в этом случае пакет отправляется на этот маршрутизатор. Большие маршрутизаторы могут знать, что для диапазона IP-адресов X1-Y1 пакет должен идти в маршрутизатор R1, для диапазона X2-Y2 пакет должен идти в маршрутизатор R2 и т. Д. В этом не задействован алгоритм Dijkstras.
2
@ Thorbjørn Ravn Andersen: Если бы маршрутизатор знал эту информацию, кому-то в какой-то момент пришлось бы использовать алгоритм Дейкстры. Да, он не используется для фактической маршрутизации каждого отдельного пакета, но он используется для определения таблиц маршрутизации в больших сетях. +1.
Билли ONEAL
@ Билли, где конкретно вы ожидаете, что алгоритм Дейкстры на самом деле используется и кем?
@ Thorbjørn Ravn Andersen: Насколько я понимаю, это играет роль в OSPF, который является основой выбора правильных маршрутов для небольших сетей. Соединения между большими сетями используют BGP, который в большей степени основан на политике. Я не уверен, использует ли BGP алгоритм Дейкстры или нет.
Билли ONEAL
3
@ Билли, но я возражал против того, что «существует в КАЖДОМ роутере в мире». Это, на мой взгляд, явно неправильно.
30

Быстрое преобразование Фурье (БПФ)

БПФ является чрезвычайно важным и широко используемым методом извлечения полезной информации из дискретизированных сигналов .

Быстрое преобразование Фурье (БПФ) является эффективным алгоритмом для вычисления дискретного преобразования Фурье (ДПФ) и его обратного.

Амир Резаи
источник
4
Однажды у меня был начальник, который десятилетиями ранее написал ряд функций FFT для PDP-11. Он продал колоду перфокарт с этими функциями с рекламой в конце Popular Science и сделал довольно серьезный банк. Очевидно, у него были люди, использующие его код для всего: от обработки сигналов до прогнозирования на фондовом рынке.
Дэн Рэй
26

PageRank

PageRank - это алгоритм анализа ссылок, названный в честь Ларри Пейджа, который используется поисковой системой Google в Интернете, который присваивает числовой вес каждому элементу набора документов с гиперссылками, например, World Wide Web, с целью «измерения» его относительного Важность в наборе.

Амир Резаи
источник
ха-ха, наши ответы были разнесены всего на 2 секунды, извините :)
Макси
совершенно никаких проблем! :)
Амир Резаи
36
Я так и не понял, что его назвали в честь Ларри Пейджа. Я всегда предполагал, что это имя как-то связано с веб-страницами.
JohnFx
1
@JohnFx Вау, не шучу!
Марк С
+1: но может ли он быть квалифицирован, если фактический алгоритм не известен человечеству? (Википедия IIRC является приблизительным)
Стивен Эверс
22

Алгоритмы сжатия данных

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

Амир Резаи
источник
2
Именно так и я думаю, базовый алгоритм сжатия LZW можно считать одним из самых красивых алгоритмов в разработке программного обеспечения.
Моджуба
«если возможно, дайте имя конкретному алгоритму»
14

Смит-Уотерман (и Нидлман-Вунш)

Это может быть слишком далеко, поэтому, пожалуйста, прокомментируйте.

Смит-Уотерман: алгоритм выравнивания последовательностей

Я думаю, что одним из таких примеров являются алгоритмы Смита-Уотермана и Нидлмана-Вунша и их аппроксимации. Все они по сути делают одно и то же: они выравнивают две или более строки (последовательности) . В биологии есть значение. Когда последовательности ДНК или белка выровнены - выявляются области структурного, функционального и эволюционного сходства.

БЛАСТ как потомок Смита-Ватермана

Эвристика, которая приближается к Смиту-Уотерману, является BLAST. Это позволяет искать последовательности больших баз данных для биологического сходства. Популярность BLAST действительно велика - скорее всего, это наиболее широко используемый алгоритм в биологии. Новые области в биоинформатике и геномике имеют новые и лучшие приближения алгоритмов Смита-Уотермана / Нидлмана-Вунша, которые более точны, чем BLAST.

Геном Ассамблея как потомок Смит-Уотерман

Высокопроизводительные приближения Смита-Уотермана и Нидлмана-Вунша, которые работают быстрее, чем BLAST, используются для сборки геномов из последовательности дробовика, где продуктом секвенсора является огромное количество, которое ДНК считывает (миллиарды) из произвольных частей генома, которые являются очень короткий (от 50 до 100 нуклеотидов). Этот подход был использован для завершения проекта «Геном человека». Все современные последовательности сделаны таким образом.

Выравнивание нескольких последовательностей - расширение Смита-Уотермана

Существуют многочисленные алгоритмы выравнивания множественных последовательностей - они аппроксимируют многократные версии Смита-Уотермана / Нидлмана-Вунша. Несколько последовательностей выровнены как группа одновременно друг с другом. Это гораздо более сложная проблема, чем попарный аналог, но решения обеспечивают гораздо более глубокое понимание биологической функции, структуры и эволюционной истории связанных последовательностей.

Александр Левчук
источник
Привет и добро пожаловать в Программисты! Возможно, вы захотите разбить этот ответ на один для каждого из алгоритмов, которые вы здесь представляете, как это обычно делается для таких вопросов, как этот, чтобы облегчить голосование и сортировку.
И Цзян
@Yi Jiang: мой пантеон! Я неверно истолковал ваш комментарий как «облегчить рвоту». : - /
доктор Ганнибал Лектер
Здесь я рассуждаю только об одном алгоритме - Смит-Уотерман (и его вариант Needleman-Wunsch)
Александр Левчук
13

Сиам назвал следующие наиболее важные алгоритмы 20-го века:

1946: алгоритм Метрополиса для Монте-Карло . Благодаря использованию случайных процессов этот алгоритм предлагает эффективный способ найти ответы на вопросы, которые слишком сложны для точного решения.

1947: Симплексный метод для линейного программирования . Элегантное решение общей проблемы при планировании и принятии решений.

1950: итерационный метод подпространства Крылова . Техника для быстрого решения линейных уравнений, которых предостаточно в научных вычислениях.

1951: декомпозиционный подход к матричным вычислениям . Набор методов для числовой линейной алгебры.

1957: Оптимизирующий компилятор Fortran . Превращает код высокого уровня в эффективный машиночитаемый код.

1959: Алгоритм QR для вычисления собственных значений . Другая важная матричная операция стала быстрой и практичной.

1962: алгоритмы быстрой сортировки для сортировки . Для эффективной обработки больших баз данных.

1965: быстрое преобразование Фурье . Возможно, самый распространенный алгоритм, используемый сегодня, он разбивает сигналы (например, звук) на периодические компоненты.

1977: Обнаружение целочисленных отношений . Быстрый метод определения простых уравнений, удовлетворяемых наборами, казалось бы, не связанных чисел.

1987: быстрый мультипольный метод . Прорыв в решении сложных вычислений n-тела, применяемых в задачах от небесной механики до сворачивания белков.

Лично я бы заменил Integer Relation Detection на PageRank .

Ясон
источник
1
К этому списку я добавил бы 2 книги, хотя они были больше о «самых важных теоремах» 20-го века: Пять Золотых Правил amazon.com/Five-Golden-Rules-20th-Century-Matmatics/dp/… , и Еще пять золотых правил. amazon.com/Five-More-Golden-Rules-20th-Century/dp/0471395285
Tangurena
Методы Монте-Карло все еще используются, более или менее в первоначальном виде. Это также верно для БПФ и быстрой сортировки. Большинство остальных я просто не знаком с. Метод Simplex для LP не очень хорошо масштабируется по сравнению с более современными методами.
Дэвид Торнли
9

PageRank, любите это или ненавидите это, но это влияет на решения и действия миллионов людей во всем мире, гуглящих ежедневно.

Maksee
источник
9

Если бы мне пришлось перечислить 3 самых важных алгоритма, используемых сегодня в компьютерах, я бы сказал:

  1. Бинарный поиск
  2. Quicksort
  3. Алгоритм Дейкстры

Двоичного поиска используется алгоритм постоянно сужать на элемент в отсортированном списке, большинство поиск по индексу будет использовать что - то вдоль этих линий в какой - то момент. Этот алгоритм обеспечивает поиск упорядоченного списка за o (log n) времени.

Quicksort алгоритм , наконец , удалось получить своего рода вплоть до O (п журнал п) средний случай и O (N ^ 2) худший случай. Сортировка является одной из самых распространенных задач обработки данных в компьютере и одной из самых дорогих, улучшение сортировки в среднем случае стало огромным шагом вперед по эффективности.

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

Orbling
источник
Двоичный поиск должен был бы быть очень, очень старым ... Я имею в виду, он был сформулирован «в прошлом», и это было в «десятилетии», но это было бы в течение многих сотен лет.
Кирк Бродхерст
@Kirk Broadhurst: Тем не менее, это невероятно важный алгоритм для компьютеров. Независимо от того, когда человек впервые задумал это.
Orbling
8

Теорема Байеса

Это, вероятно, больше всего способствовало поддержанию количества спама, потраченного впустую, в моем почтовом ящике на управляемом уровне.

Конечно, я его использовал во многих других полезных приложениях, но SPAM-убийство - мой любимый.

JohnFx
источник
Я бы дал вам большой палец вверх, но это теорема (одна из лучших), а не алгоритм. Однако многие алгоритмы основаны на этой теореме.
Амир Резаи
Я просто пытался объединить их в общую категорию алгоритмов, но технически вы правы.
JohnFx
@AmirR Технически правильно, лучший вид правильно!
Марк С
7

TimSort

Этот алгоритм сортировки сейчас используется в Python , Java 7 и Android

В основном:

  • O (N log N) худший случай (не вырождается)
  • O (N) для почти отсортированного списка (фактически N-1точно в уже отсортированном списке)

И красота этого? Это стабильно ! И поэтому подходит для многопроходной сортировки по различным критериям.

Кстати, если у кого-то есть оптимизированная реализация C ++ под рукой ...

Matthieu M.
источник
Это не может быть Θ (NlogN), так как он имеет лучшее поведение в уже отсортированном списке. O (NlogN) - правильное обозначение здесь.
Donal Fellows
Хотя этот вариант хорош, я бы не назвал его «одним из величайших алгоритмов, изобретенных за последние десятилетия». Mergesort, на котором основан Timsort, является настоящим достижением.
Билли ОНил
6

Все алгоритмы, которые использовались для решения проблемы видимости в 3D компьютерной анимации, кажутся мне решающими.

Алгоритм художника

Алгоритм художника, также известный как приоритетное заполнение, является одним из простейших решений проблемы видимости в трехмерной компьютерной графике. При проецировании 3D-сцены на 2D-плоскость необходимо в какой-то момент решить, какие полигоны видимы, а какие скрыты.

Z-буферизация

В компьютерной графике z-буферизация - это управление координатами глубины изображения в трехмерной (3-D) графике, обычно выполняемой аппаратно, иногда программно. Это одно из решений проблемы видимости, которая заключается в решении вопроса о том, какие элементы визуализированной сцены видимы, а какие скрыты. Алгоритм художника является еще одним распространенным решением, которое, хотя и менее эффективно, также может обрабатывать непрозрачные элементы сцены. Z-буферизация также известна как буферизация глубины.

Определение скрытой поверхности

В трехмерной компьютерной графике определение скрытой поверхности (также известное как удаление скрытой поверхности (HSR), выборка окклюзии (OC) или определение видимой поверхности (VSD) - это процесс, используемый для определения того, какие поверхности и части поверхностей не видны с определенной точки зрения. Алгоритм определения скрытой поверхности - это решение проблемы видимости, которая была одной из первых основных проблем в области трехмерной компьютерной графики. Процесс определения скрытой поверхности иногда называют скрытием, а такой алгоритм иногда называют скрытым Аналогом рендеринга линий является удаление скрытых линий. Определение скрытой поверхности необходимо для правильной визуализации изображения, чтобы, например, нельзя было смотреть сквозь стены в виртуальной реальности.

датчанин
источник
3

Какой из них вам нужен, чтобы решить вашу текущую проблему.

mipadi
источник
1
Это то, что я собирался сказать. Теперь мне не нужно это говорить.
Роберт Харви
Какой бы не хороший ответ. Какие бы алгоритмы не были значимы для человечества.
Амир Резаи
6
Это не конкретный алгоритм, и даже если бы он был, вероятно, не важен для человечества.
Джейсон
3

Soundex - это фонетический алгоритм для индексации имен по звуку.

Сэл
источник
Как soundex помог человечеству?
Барджак
Это улучшило способность использовать естественный язык, исправляя незначительные различия в правописании и региональном произношении.
Сал
3

Алгоритм Витерби

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

Джакомо Вертикаль
источник
+1 Алгоритм Витерби очень важен. @ [Giacomo Verticale], возможно, стоит упомянуть, что это связано со скрытыми марковскими моделями (HMM).
Александр Левчук
3

MP3

Хотя это более общий термин, чем конкретный алгоритм, я бы упомянул MP3 как совокупность различных алгоритмов и методов, которые работают совместно, чтобы создать этот аудиоформат с потерями.

Это, безусловно, было очень важно в «цифровую эпоху».

Йенс Хоффманн
источник
3

Численное интегрирование Рунге-Кутты . Без этого многие симуляции были бы невозможны. Нет космической программы, нет ядерной энергии, нет баллистики, нет спортивных симуляций, нет пуленепробиваемых жилетов, нет симуляции краш-теста, нет симуляции движения жидкости, нет симуляции химического взаимодействия, нет зданий, устойчивых к землетрясениям ... список можно продолжать.

ja72
источник
+1 @ j172 Я знаю это, это действительно полезно для численного анализа и моделирования.
Амир Резаи
2

Алгоритм сортировки.

ТИА
источник
5
это не конкретный алгоритм, хотя ...
Джастин Л.
Да, что сказал Джастин Л., какой алгоритм сортировки?
Доктор Ганнибал Лектер
«Специфический алгоритм» должен быть сортировкой слиянием, первым из n lg n сортировок.
Билли ONEAL
2
@dr Ганнибал Лектер: пузыри вроде как. Все остальное - преждевременная оптимизация.
peterchen
2

Quicksort

Есолик
источник
1
Тьфу! Я, конечно, надеюсь, что люди не используют быструю сортировку в производственном коде. Что еще важнее, mergesort появился раньше и работает почти так же быстро. (Надеюсь, что большинство кода использует какой-то вариант в Introsort)
Билли ONeal
2
@Billy ONeal, сортировка в .NET - это все быстрая сортировка. Таким образом, любая программа, которая вызывает List <T> .Sort (), использует быструю сортировку в производстве.
Стивен Эверс
@SnOrfus: У вас есть доказательства этого заявления? Насколько я понимаю, List <t> .Sort основан на интросорте.
Билли ОНил
3
@Billy ONeal: прямо с msdn
msdn.microsoft.com/en-us/library/b0zbh7b6.aspx
3
@ Thorbjørn: Это все еще не хороший алгоритм общего назначения. Introsort - быстрая сортировка, но она переключается на сортировку кучи, если выходит за пределы заданной глубины рекурсии. Это позволяет иметь хорошие характеристики быстрой сортировки, но всегда позволяет избежать патологических случаев, даже если алгоритм выбирает плохие опорные точки.
Билли ОНил
1

Сортировка вставки

Простая в реализации, очень быстрая в небольших списках и используемая в реализациях Merge Sort / Quicksort для их ускорения. Он стабилен и работает в O (n) в отсортированных списках (при сортировке в порядке возрастания).

Оливер Вейлер
источник
1

Гаусс-Джордан в матричных вычислениях

кспорт
источник
1

Фильтр Калмана

Он активно используется в навигации, отслеживании целей (практически для любого датчика: радар, гидролокатор, FLIR, ладар). Один учебник показывает приложение в контроллере дисковода. Роботизированные системы управления часто используют фильтры Калмана.

Джон Р. Штром
источник
0

Разговорный и письменный язык.

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

Malfist
источник
5
-1: алгоритмы могут быть выражены с использованием естественного языка, но естественные языки не являются алгоритмами.
Стивен Эверс
2
Вы бы сказали, что алгоритмы сжатия не являются алгоритмами? Все, что делает язык - это сжимает информацию, которая передается от источника к получателю. У него есть определенные правила, которые должны соблюдаться (грамматика), как и у любого другого алгоритма, и он принимает данные (ваш опыт) и дает другой результат (знания). Я не вижу, как вы не можете считать язык алгоритмом.
Малфист
Он не соответствует всем стандартным определениям алгоритма по многим направлениям.
Джеймс восстановил Монику Полк
0

Структура данных кучи и связанные с ней алгоритмы построения и обслуживания кучи.

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

Джеймс восстановил Монику Полк
источник
0

Алгоритмы индексирования, такие как B-дерево, B + -дерево, хэш-индекс, бинарный индекс дерева и т. Д. Для индексации огромного количества данных.

хуг
источник
0

MapReduce как способ разделения, завоевания и распараллеливания обработки больших наборов данных.

Джей Элстон
источник
-1

Алгоритм грубой силы!

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

оборота xport
источник
5
Это не алгоритм. Это своего рода алгоритмы.
Адам Лир
Это метод взлома шифрования.
Амир Резаи
Я думаю, что это также классифицируется как алгоритм. «Начни с х по у, сделай что-нибудь». <--- алгоритм правильный?
xport
Алгоритм - это последовательность шагов для выполнения конкретной задачи. Это не конкретное.
Анто
-5

Bubble Sort!

Пузырьковая сортировка не так плоха, как Bogosort . Вот почему я голосую за Bubble.

оборота xport
источник
1
Пожалуйста, подумайте, чтобы заявить, почему алгоритм важен и важен, люди, похоже, просто не согласны с тем, почему Bubble Sort может быть значимым и важным.
Тамара Вийсман
5
Даже Барак Обама знает, что пузырьковая сортировка - неправильный путь .
Джои Адамс
@ TomWij, @Joey: посмотрите мое обновление.
xport