Ваш любимый алгоритм и урок, который он вам преподал

Общий алгоритм:

• Quicksort (и это анализ средней сложности), показывает, что рандомизация вашего ввода может быть хорошей вещью!;
• сбалансированные деревья (например, AVL деревьев ), аккуратный способ сбалансировать затраты на поиск / вставку;
• Алгоритмы Дейкстры и Форда-Фулькерсона на графах (мне нравится тот факт, что второй имеет много приложений);
• семейство алгоритмов сжатия LZ* (например, LZW ), сжатие данных звучало для меня как волшебство, пока я не обнаружил его (давным-давно :) );
• FFT, вездесущий (повторно используемый во многих других алгоритмах);
• симплексный алгоритм, вездесущий также.

Численное отношение:

• Алгоритм Евклида для вычисления gcd из двух целых чисел: один из первых алгоритмов, простой и элегантный, мощный, имеет множество обобщений;
• быстрое умножение целых чисел ( например, Кули-Туки );
• Итерации Ньютона для инвертирования / поиска корня-очень мощный мета-алгоритм.

Связанные с теорией чисел:

• AGM-связанные алгоритмы (примеры): приводит к очень простым и элегантным алгоритмам вычисления pi (и многое другое!), хотя теория довольно глубокая (Гаусс ввел из нее эллиптические функции и модулярные формы, так что можно сказать, что она породила алгебраическую геометрию...);
• сито числового поля (для целочисленной факторизации): очень сложный, но довольно приятный теоретический результат (это также относится к алгоритму AKS , который доказал, что PRIMES находится в P).

Мне также нравилось изучать квантовые вычисления (например, алгоритмы Шора и Дойча-Йоши ): это учит вас мыслить нестандартно.

Как вы можете видеть, я немного предвзято отношусь к математически ориентированным алгоритмам :)

"To iterate is human, to recurse divine"-цитируется в 1989 году в колледже.

P.S. Опубликовано Woodgnome в ожидании приглашения присоединиться

Алгоритм кратчайших путей для всех пар Флойда-Уоршелла

procedure FloydWarshall ()
   for k := 1 to n
     for i := 1 to n
        for j := 1 to n
          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

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

Затем учитель говорит:"Теперь мы хотим решить ту же проблему, но для ALL источников". Вы думаете про себя: "О боже, это будет гораздо более сложная проблема! Это будет как минимум в N раз сложнее, чем алгоритм Дейкстры!!! ".

Затем учитель дает вам Флойд-Уоршолл. И ваш разум взрывается. Затем вы начинаете разрываться от того, насколько красиво прост этот алгоритм. Это просто трижды вложенный цикл. Он использует только простой массив для своей структуры данных.

Самая интересная часть для меня-это следующее осознание: скажем, у вас есть решение проблемы А. Тогда у вас есть большая "superproblem" B, которая содержит проблему A. решение проблемы B может быть на самом деле проще, чем решение проблемы A.

Кодирование Хаффмана будет моим, я изначально сделал свою собственную тупую версию, минимизировав количество битов для кодирования текста с 8 до менее, но не думал о переменном количестве битов в зависимости от частоты. Затем я нашел кодировку Хаффмана, описанную в статье в журнале, и это открыло множество новых возможностей.

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

Это может показаться банальным, но в то время для меня это было откровением. Я был на своем самом первом занятии по программированию (VB6), и профессор только что рассказал нам о случайных числах, и он дал следующие инструкции: "создайте виртуальную лотерейную машину. Представьте себе стеклянный шар, полный 100 шариков для пинг-понга, помеченных от 0 до 99. Выбирайте их случайным образом и показывайте их количество, пока они все не будут выбраны, никаких дубликатов."

Все остальные писали свою программу следующим образом: Выберите шар, поместите его номер в "already selected list", а затем выберите другой шар. Проверьте, чтобы увидеть, если его уже выбрали, если так выбрать другой шар, если не поставить его номер на "already selected list" и т.д....

Конечно, к концу игры они проделали сотни сравнений, чтобы найти те несколько мячей, которые еще не были отобраны. Это было похоже на бросание шаров обратно в jar после их выбора. Мое откровение состояло в том, чтобы выбрасывать мячи после сбора.

Я знаю, что это звучит ошеломляюще очевидно, но именно в этот момент "programming switch" перевернулось у меня в голове. Это был момент, когда Программирование перешло от попыток выучить незнакомый иностранный язык к попыткам решить приятную головоломку. И как только я установил мысленную связь между программированием и развлечением, меня уже ничто не могло остановить.

Линия Bresenham алгоритм рисования заинтересовал меня в реальном времени рендеринга графики. Это можно использовать для визуализации заполненных полигонов, таких как треугольники, для таких вещей, как рендеринг модели 3D.

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

Quicksort в Haskell:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

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

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

Мне почему-то нравится шварцевская трансформация

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

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

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

Для разработки-подход "fib(10) = fib(9) + fib(8)" означает, что fib(9) будет оцениваться как fib(8) + fib(7). Таким образом, оценка fib(8) (и соответственно fib7, fib6) будет оцениваться дважды.

Итерационный метод (curr = prev1 + prev2 в forloop) не имеет такого дерева и не занимает столько памяти, так как это всего лишь 3 переходные переменные, а не n кадров в стеке рекурсии.

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

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

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

Поменять местами 2 целых числа без использования промежуточной переменной (в C++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

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

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

У меня нет фаворита –есть так много красивых вариантов , чтобы выбрать из них, но один из них я всегда находил интригующим–это формула Бейли-Борвейна-Плуффа (BBP), которая позволяет вычислить произвольную цифру pi, не зная о предыдущих цифрах.

Это очень медленный процесс :)

Я узнал много нового как о C, так и о компьютерах в целом, поняв устройство Даффов и XOR свопов

EDIT:

@ Jason Z , это мой XOR swap:) круто, правда?

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

Это не научило меня многому,но алгоритм Джонсона-Троттера никогда не подводит меня.

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

Чему они меня научили:

• компактное представление любой проблемы важно; малое-прекрасно
• для этого можно использовать небольшой набор ограничений/сокращений, применяемых рекурсивно
• для задач с симметриями первым шагом к рассмотрению должно быть преобразование в каноническую форму
• не всякую литературу читают. Кнут узнал о BDD через несколько лет после их invention/introduction. (и провел почти год, исследуя их)

Больше всего я гордился решением, написав что-то очень похожее на пакет DisplayTag. Это научило меня многому о дизайне кода, ремонтопригодности и повторном использовании. Я написал его задолго до DisplayTag года, и он был погружен в соглашение NDA, поэтому я не мог открыть его исходный код, но я все еще могу говорить о нем с восторгом в интервью для работы.

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

Map/Reduce. две простые концепции, которые подходят друг к другу, чтобы облегчить распараллеливание нагрузки задач обработки данных.

О... и это только основа массово-параллельной индексации:

http://labs.google.com/papers/mapreduce.html

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

Итерационный метод (curr = prev1 + prev2 в forloop) не имеет такого дерева и не занимает столько памяти, так как это всего лишь 3 переходные переменные, а не n кадров в стеке рекурсии.

Вы же знаете, что Фибоначчи имеет замкнутую форму решения, которая позволяет напрямую вычислить результат за фиксированное число шагов, не так ли? А именно, (phi ⁿ - (1-phi) ⁿ) / sqrt(5). Мне всегда кажется несколько удивительным, что это дает целое число, но это так.

ФИ - это, конечно, золотое сечение; (1 + sqrt(5)) / 2.