Алгоритмы из Книги.

358

Пол Эрдос говорил о «Книге», где Бог хранит самое элегантное доказательство каждой математической теоремы. Это даже вдохновило книгу (которая, я думаю, теперь в ее 4-м издании): Доказательства из Книги .

Если бы у Бога была подобная книга для алгоритмов, какой алгоритм (ы), как вы думаете, был бы кандидатом (ами)?

Если возможно, пожалуйста, предоставьте интерактивную ссылку и ключевые идеи, которые заставят ее работать.

Только один алгоритм на ответ, пожалуйста.

Aryabhata
источник
11
Отличный вопрос! [Редактировать:} Один вопрос. Где мы проводим грань между алгоритмами и структурами данных? Что если ключевое понимание алгоритма тесно связано с структурой данных (например, UNION FIND в обратной функции Аккермана)?
Росс Снайдер
4
отличный источник и, возможно, кандидат в такую ​​книгу - «Энциклопедия алгоритмов». springer.com/computer/theoretical+computer+science/book/…
Маркос Вильягра,
21
Я немного удивлен, что алгоритмы, которые я считаю довольно хитрыми (KMP, линейные суффиксные массивы), рассматриваются другими как «из Книги». Для меня «из Книги» означает просто и очевидно, но только задним числом. Мне любопытно, как другие интерпретируют "элегантный".
Раду GRIGore
49
@supercooldave Вам не нужно верить в Бога, но вы должны верить в его книгу. ;-)
Росс Снайдер
10
Во время лекции 1985 года Эрдос сказал: «Вам не нужно верить в Бога, но вы должны верить в Книгу».
Роберт Массайоли

Ответы:

116

Union-find - это красивая проблема, чей лучший алгоритм / структура данных ( Disjoint Set Forest ) основан на стеке спагетти. Несмотря на то, что это очень просто и достаточно интуитивно понятно для интеллигентного ребенка, потребовалось несколько лет, чтобы жестко ограничить время его выполнения. В конечном счете, было обнаружено, что его поведение связано с обратной функцией Аккермана, функцией, открытие которой ознаменовало изменение взгляда на вычисления (и фактически было включено в книгу Гильберта « О бесконечности» ).

Википедия предоставляет хорошее введение в Disjoint Set Forests .

Юкка Суомела
источник
109

Сопоставление строк Кнута-Морриса-Пратта . Самые красивые восемь строк кода, которые вы когда-либо увидите.

Юкка Суомела
источник
4
Это ошеломляет, когда я понимаю, что это было нечто неочевидное в то время, и это стало очевидным только сейчас, потому что они придумали это, и мы узнали это ... Я думаю, что мы должны применить теорию истории Карра к математике и информатике ,
Ритвик Бозе
1
По описанию я бы сказал, что это связано с быстрым поиском подстроки Бойера-Мура.
Барт
2
@Mechko Тот факт, что этот алгоритм был открыт одновременно и независимо отдельными людьми, свидетельствует о его очевидной степени. Является ли что-то «очевидным», зависит от ограничений проекта и более широкой среды программирования. Если вам нужен (1) быстрый поиск текста и (2) вы знаете о важности действительно O (n) алгоритмов, и (3) вы встречали текст с частичными совпадениями ранее, и (4) у вас есть время чтобы сделать все правильно, этот алгоритм, вероятно, очевиден.
Мэтт Галлахер
В одном из интервью Кнут сказал, что идея алгоритма возникла из изучения двустороннего конечного автомата Стивена Кука для палиндромов.
Каве
@Kaveh Пожалуйста, прочтите Раздел 7 (Исторические заметки) из оригинальной статьи KMP. У него есть замечательные замечания. О Моррисе, пишущем текстовый редактор, который «был слишком сложен для понимания другими разработчиками системы». О Кнуте «впервые в опыте Кнута теория автоматов научила его, как решать реальную задачу программирования лучше, чем он мог решить ее раньше». И «Кнут был огорчен, узнав, что Моррис уже открыл алгоритм, не зная теорему Кука;». ВЕСЕЛЬЕ.
Хендрик Ян
93

Алгоритм Блюма, Флойд, Пратты, Ривест и Tarjan , чтобы найти K - й элемент несортированного списка в линейное время красивый алгоритм, и работает только потому , что номер только право , чтобы соответствовать в Генеральной теореме. Это выглядит следующим образом:

  1. Сортируйте каждую последовательность из пяти элементов.
  2. Выберите медиану в каждом.
  3. Повторите, чтобы найти медиану этого списка.
  4. Поворот по медиане медиан (как в Quicksort)
  5. Выберите правильную сторону списка и положение в этом списке, и повторите.
Derrick Stolee
источник
3
Это один из моих любимых алгоритмов. Мне нравится интуиция, которую я узнал из книги расхождений Шазель: набор медиан групп элементов подобен -net для интервалов в упорядоченном списке входных чисел. Таким образом, алгоритм следует общей парадигме: вычисление -net fast, решение проблемы в сети, повторение некоторой части ввода для уточнения решения до тех пор, пока у вас не будет точного решения. это очень полезная техникаϵ ϵ1/ϵϵϵ
Сашо Николов
5
Кстати, как только вы параметризуете размер групп, константы не так волшебны. они, конечно, оптимизированы, чтобы дать правильную вещь в теореме Мастера
Сашо Николов
Реализация на Ruby, gist.github.com/chadbrewbaker/7202412 Существует ли версия алгоритма, в которой используется пространство (константа, лог), или вам нужно использовать линейное пространство для хранения медиан?
Чад Brewbaker
2
Утверждение, что «это работает только потому, что числа соответствуют размеру основной теоремы», не совсем верно. Если вы замените число большим числом , легко увидеть, что два числа, сумма которых должна быть меньше сходятся к и , поэтому все достаточно большие работают. - это только первое число, которое работает, но не единственное. н 1 3 / 4 0 п 55n13/40n5
Уилл Савин
88

Бинарный поиск - самый простой, красивый и полезный алгоритм, с которым я когда-либо сталкивался.

оборота мичалмочный
источник
Я бы заменил элегантный на интуитивный. В этом нет ничего такого элегантного; его простота - его настоящая красота.
Роберт Массайоли
@ Роберт Массаили: я заменил элегантное на красивое. Вы были правы насчет этого.
michalmocny
2
И безумно сложно писать правильно - см. « Вы один из 10% программистов, которые могут писать бинарный поиск? »
Джон
В моем первом курсе по выпуску алгоритмов у нас были 15-минутные викторины, где мы должны были решить 2-3 задачи вручную. Первый такой тест включал бинарное дерево поиска и два вопроса о кучах. Я был смущен и встревожен, узнав, что я неправильно понял проблему бинарного поиска, прежде чем мне сказали, что в классе из 30 человек есть два правильных ответа. Но даже зная об этом, тот факт, что профессиональному сообществу потребовалось 15 лет, чтобы получить права, ошеломляет.
Стелла Бидерман,
84

Я удивлен, что не вижу здесь алгоритма Флойда-Варшалла для кратчайших путей всех пар:

d[]: 2D array. d[i,j] is the cost of edge ij, or inf if there is no such edge.

for k from 1 to n:
  for i from 1 to n:
    for j from 1 to n:
      d[i,j] = min(d[i,j], d[i,k] + d[k,j])

Один из самых коротких и ясных нетривиальных алгоритмов, производительность очень быстро, если учесть, что может быть ребер. Это был бы мой плакатный ребенок для динамического программирования!O ( n 2 )O(n3)O(n2)

user651
источник
2
Этот алгоритм также может быть обобщен очень аккуратно. См., Например, r6.ca/blog/20110808T035622Z.html и cl.cam.ac.uk/~sd601/papers/semirings.pdf
Михаил Глушенков
73

Может показаться несколько тривиальным (особенно по сравнению с другими ответами), но я думаю, что Quicksort действительно элегантен. Я помню, что когда я впервые увидел это, я подумал, что это действительно сложно, но сейчас это кажется слишком простым.

Юкка Суомела
источник
10
Быстрая сортировка также поднимает интересные вопросы о том, какова суть алгоритма. Например, стандартная элегантная реализация на Haskell выглядит точно так же, как стандартное определение псевдокода, но имеет другую асимптотическую сложность. Итак, Quicksort - это просто «разделяй и властвуй», или же хитроумная манипуляция указателем на месте является важной частью Quicksort? Может ли Quicksort быть реализован в чисто функциональном окружении или он требует изменчивости?
Йорг Миттаг
2
Идея «сущности» или «морали» алгоритма, конечно же, взята из прекрасной статьи Мелиссы Э. О'Нил «Подлинное сито Эратосфена » ( cs.hmc.edu/~oneill/papers/Sieve-JFP. pdf ), и обсуждение быстрой сортировки происходит из обсуждения этой статьи в LtU ( lambda-the-ultimate.org/node/3127 ), особенно начиная с этого комментария: lambda-the-ultimate.org/node/3127/#comment-45549
Йорг Миттаг
8
@ Jörg: Реализация быстрой сортировки в связанных списках совершенно разумна и имеет то же самое асимптотическое время выполнения, что и ее реализация на месте на массивах (черт, даже наивная нереализованная реализация на массивах имеет одинаковое время выполнения) - оба на средний и в худшем случае. Что касается использования пространства, то оно действительно другое, но следует сказать, что даже версия «на месте» требует непостоянного дополнительного пространства (стек вызовов!), Что легко упустить из виду.
Конрад Рудольф
Также стоит упомянуть о Dual-Pivot Quicksort Владимира Ярославского. Это должно быть не менее 20% быстрее оригинального QuickSort permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/...
SaveTheRbtz
Быстрая сортировка в теории проста (может быть описана в 4 шага) и может быть высоко оптимизирована, но на практике очень трудно правильно написать код. Вот почему он не получил мой голос.
Деннис
50

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

На этой ноте, тест на первичность AKS, который показал, что PRIMES находится в P, обязательно должен быть в Книге!

Юкка Суомела
источник
49

Полиномиальное тестирование с использованием леммы Шварца-Циппеля :

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

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

Не известен детерминированный алгоритм для задачи, который выполняется за полиномиальное время.

Пер Вогсен
источник
Это должно было быть предложено давно! Спасибо!
Арнаб
1
Есть несколько других рандомизированных алгоритмов, которые заслуживают видного места в Книге. Для них контраст между детерминистическими и вероятностными альтернативами менее разителен: детерминистический алгоритм обычно существует, но гораздо сложнее.
Per Vognsen
Я независимо изобрел тот же алгоритм, когда пару лет назад работал над документом, пока кто-то не спросил меня, не правда ли, лемма Шварца-Циппеля? И я сказал, что это? :)
Гелий
46

Глубина Первый Поиск . Это основа многих других алгоритмов. Это также обманчиво просто: например, если вы замените очередь в реализации BFS стеком, получите ли вы DFS?

Раду ГРИГОРЕ
источник
1
Это также основа исполнения Пролога!
Муад
1
Какой смысл в BFS со стеком, который мне не хватает? Я бы подумал, что ответ «да, вы получаете DFS».
Омар Антолин-Камарена
1
Ну, кажется, все считают эту проблему тривиальной. Кроме того, все, кажется, думают, что ответ «да», что неправильно. Ответ на самом деле «зависит от того, с какой реализации BFS вы начинаете». См. Cs.stackexchange.com/questions/329/… (это вопрос, который я разместил, чтобы помочь с бета-фазой CS.SE)
Раду GRIGore
Это также кратко обсуждено здесь: ics.uci.edu//~eppstein/161/960215.html
Раду GRIGore
42

Алгоритм Дейкстры : проблема кратчайшего пути из одного источника для графа с неотрицательными стоимостями ребер. Он используется везде и является одним из самых красивых алгоритмов. Интернет не может быть маршрутизирован без него - он является основной частью протоколов маршрутизации IS-IS и OSPF (Open Shortest Path First).

  1. Назначьте каждому узлу значение расстояния. Установите его в ноль для нашего начального узла и в бесконечность для всех остальных узлов.
  2. Отметить все узлы как не посещенные. Установить начальный узел как текущий.
  3. Для текущего узла рассмотрите все его не посещенные соседи и вычислите их предварительное расстояние (от начального узла). Например, если текущий узел (A) имеет расстояние 6, а ребро, соединяющее его с другим узлом (B), равно 2, расстояние от B до A будет 6 + 2 = 8. Если это расстояние меньше ранее записанного расстояния (бесконечность в начале, ноль для начального узла), перезапишите расстояние.
  4. Когда мы закончим с учетом всех соседей текущего узла, отметьте его как посещенный. Посещенный узел больше не будет проверяться; записанное в настоящее время расстояние является окончательным и минимальным.
  5. Если все узлы были посещены, закончите. В противном случае установите не посещаемый узел с наименьшим расстоянием (от начального узла) в качестве следующего «текущего узла» и продолжайте с шага 3.
Дэвид Сифри
источник
40

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

Схема шифрования обусловлена ​​несколькими острыми наблюдениями.

  • Чтобы получить полностью гомоморфную схему шифрования, нужно только иметь схему, которая гомоморфна над сложением и умножением. Это потому, что сложения и умножения (мод 2) достаточно, чтобы получить вентили И, ИЛИ и НЕ (и, следовательно, полнота Тьюринга).
  • Если такая схема должна была иметь место, но из-за некоторых ограничений она может быть выполнена только для цепей некоторой конечной глубины, то можно гомоморфно оценить процедуру дешифрования и повторного шифрования, чтобы сбросить ограничение глубины схемы без ущерба для конфиденциальности ключа.
  • Таким образом, путем «сжатия» глубинной версии схемы функции дешифрования для схемы можно было бы получить схему, изначально ограниченную конечными мелкими схемами, произвольным числом вычислений.

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

http://crypto.stanford.edu/craig/craig-thesis.pdf

http://eprint.iacr.org/2009/616.pdf

http://portal.acm.org/citation.cfm?id=1666420.1666445

Росс Снайдер
источник
38

Алгоритм Штрассена для умножения матриц.

Kaveh
источник
Вероятно, подождем, пока мы не узнаем, является ли это оптимальным.
Томас Але
Это не оптимально, по крайней мере, асимптотически ... Я думаю, что включение алгоритма Штрассена заставляет вас сначала включить алгоритм Карацубы.
Тимоти Сан
35

Gale-Шепли стабильный брак алгоритм . Этот алгоритм является жадным и очень простым, сначала не очевидно, почему он будет работать, но затем доказательство правильности снова легко понять.

Конрад Свейнпол
источник
+1, потому что в опубликованных доказательствах из книги о браках есть также глава ...
ixtmixilix
34

Алгоритм линейного времени для построения массивов суффиксов действительно прекрасен, хотя на самом деле он не получил признания, которого заслуживал http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf

zotachidil
источник
Я действительно думаю , что это уже получил заслуженное признание - то , что заставляет вас думать иначе? Например, это реализовано в библиотеке анализа последовательностей C ++ SeqAn.
Конрад Рудольф
Стоит отметить, что в настоящее время существует ряд других алгоритмов построения линейных и нелинейных суффиксных временных массивов, которые, хотя и далеко не такие красивые, на практике могут быть намного быстрее. «Эффективный, универсальный подход к сортировке суффиксов», Journal of Experimental Algorithmics (JEA), том 12, июнь 2008 г., имеет некоторые экспериментальные результаты в этом направлении.
Рафаэль
@ Рафаэль: Я немного опасаюсь того, что на с. 3 этой статьи JEA, они дают только то, что, по их мнению, является «свободной» границей O (n ^ 2 log n) ... Знаете ли вы какие-либо работы с доказуемо линейными алгоритмами времени , которые на практике быстрее, чем Алгоритм перекоса?
user651
32

Гауссово исключение. Он завершает обобщение последовательности от алгоритма евклидова GCD до Кнута-Бендикса.

Митч
источник
Кстати, какова последовательность обобщения и где в нее вписывается алгоритм Бухбергера для базиса Гробнера? (Это похоже на Кнут-Бендикса, но я видел упоминание где-то, что оно как бы обобщает исключение Гаусса…)
ShreevatsaR
6
последовательность: Евклидово GCD -> Устранение Гаусса -> Бухбергер -> Кнут-Бендикс. Можно также положить (вместо исключения Гаусса) одномерное полиномиальное деление и по модулю (в порядке обобщения оно «отделено» от исключения Гаусса, GE - многомерная степень 1, кольцо многочленов - одномерная неограниченная степень, множитель Бухбергера - многомерная неограниченная степень. скачок обобщения является наибольшим от EGCD ​​до GE или полиномиального кольца из-за добавления переменных, а затем также велик от Бухбергера до КБ из-за неограниченной сигнатуры
Митч
+1: евклидов алгоритм использует наиболее знаменитое уравнение ax-by = 1 в математике. Почему это не появляется в CS чаще всего, остается загадкой.
Тегири Ненаши
32

Я был впечатлен, когда впервые увидел алгоритм отбора проб из пласта и его доказательство. Это типичная головоломка типа «головоломка для мозга» с чрезвычайно простым решением. Я думаю, что это определенно относится к книге, как для алгоритмов, так и для математических теорем.

Что касается книги, история гласит, что когда Эрдос умер и попал на небеса, он попросил встретиться с Богом. Запрос был удовлетворен, и для встречи у Эрдёша был только один вопрос. "Могу ли я посмотреть в книге?" Бог сказал да и привел Эрдёша к этому. Естественно, очень взволнованный, Эрдеш открывает книгу только для того, чтобы увидеть следующее.

Теорема 1: ...
Доказательство: Очевидное.

Теорема 2: ...
Доказательство: Очевидное.

Теорема 3: ...
Доказательство: Очевидное.

Arnar
источник
4
Теорема 4:… Доказательство: упражнение для читателя.
Джон
31

Черепаха и заяц Алгоритм . Мне это нравится, потому что я уверен, что даже если бы я потратил впустую всю свою жизнь, пытаясь найти его, я никак не мог бы придумать такую ​​идею.

Tobias Neukom
источник
6
Знаете ли вы тупой алгоритм, который решает проблему с той же асимптотикой и следует алгоритмической схеме проектирования? Я говорю об итеративном углублении. В n-й итерации вы начинаете с 2 ^ n-го наследника корня и смотрите 2 ^ n наследников вперед в поисках повторения. Даже при том, что вы повторяете некоторые свои шаги с каждой итерацией, геометрическая скорость роста радиуса поиска означает, что она не влияет на асимптотику.
Per Vognsen
30

Пример столь же фундаментальный и «тривиальный», как и доказательство Евклида бесконечного числа простых чисел:

2-приближение для MAX-CUT - Независимо для каждой вершины, назначьте его одному из двух разделов с равной вероятностью.

arnab
источник
6
Да, очень хороший алгоритм. Менее тривиально, за счет другого фактора, равного 2, этот алгоритм также работает для максимизации любой субмодульной функции, а не только функции обрезки графа. Это результат Фейджа, Миррокни и Вондрака из FOCS 07
Аарон Рот
30

Я всегда был неравнодушен к алгоритму Кристофидеса, который дает (3/2) -приложение для метрики TSP. На самом деле, назовите меня легко угодить, но мне даже понравился алгоритм 2-приближения, который был до него . Уловка Кристофида по созданию остовного дерева минимального веса Эйлера путем добавления соответствия его вершин нечетной степени (вместо дублирования всех ребер) проста и изящна, и для того, чтобы убедиться, что это совпадение имеет не более половины веса, требуется немного оптимального тура.

James King
источник
Действительно, существует также множество других простых и элегантных алгоритмов аппроксимации с приличными гарантиями аппроксимации.
Янне Х. Корхонен
25

Алгоритмы линейного программирования : симплекс, эллипсоид и методы внутренних точек.

http://en.wikipedia.org/wiki/Linear_programming#Algorithms

Kaveh
источник
И действительно, было вручено несколько Нобелевских премий за продвижение нашего понимания этих проблем.
Росс Снайдер
@Ross Kantorovich получил Нобелевскую премию по экономике за изобретение LP и его использование для распределения ресурсов. О каких еще призах вы думали?
Марк Рейтблатт
@Mark Koopermans был удостоен Нобелевской премии с Канторовичем, но с моей стороны все еще было неточно сказать «несколько».
Росс Снайдер
22

Алгоритм Робина Мозера для решения определенного класса экземпляров SAT. Такие случаи разрешимы локальной леммой Ловаша. Алгоритм Мозера действительно является нерандомизацией формулировки леммы.

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

Эта версия является продолжением его оригинальной статьи, написанной Габором Тардосом.

MassimoLauria
источник
21

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

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

Kurt
источник
21

Алгоритм Кнута X находит все решения точной проблемы покрытия . Что такого волшебного в этом - это метод, который он предложил для эффективной реализации: « Танцующие звенья» .

Диего де Эстрада
источник
20

Я думаю, что мы должны включить Schieber-Vishkin 's, который отвечает на запросы самых общих предков в постоянное время, предварительно обрабатывая лес за линейное время.

Мне нравится экспозиция Кнута в томе 4, глава 1, и его размышления . Он сказал, что ему потребовалось два целых дня, чтобы полностью понять это, и я помню его слова:

Я думаю, что это довольно красиво, но удивительно, что у него плохая пресса в литературе (..) Это основано на математике, которая волнует меня.

Диего де Эстрада
источник
10
Подождите, это может быть прекрасно, но если Кнуту потребовалось два целых дня, чтобы полностью понять это, действительно ли это "из книги"?
ShreevatsaR
@ShreevatsaR Книга написана мелким шрифтом в сносках :)
hsmyers