Алгоритм

Последовательность действий для задачи

Блок-схема использования последовательных вычитаний для нахождения наибольшего общего делителя чисел r и s

В математике и информатике алгоритм ( / ˈ æ l ɡ ə r ɪ ð əm /​ ^ⓘ ) — это конечная последовательностьматематически строгихинструкций, обычно используемая для решения класса конкретныхзадачили выполнениявычислений.^[1]Алгоритмы используются в качестве спецификаций для выполнениявычисленийиобработки данных. Более продвинутые алгоритмы могут использоватьусловные выражения, чтобы перенаправить выполнение кода по различным маршрутам (так называемоеавтоматическое принятие решений) и сделать правильныевыводы(так называемыеавтоматические рассуждения), в конечном итоге достигаяавтоматизации. Использование человеческих характеристик в качестве метафорического описания машин уже практиковалосьАланом Тьюрингомс такими терминами, как «память», «поиск» и «стимул».^[2]

Напротив, эвристика — это подход к решению проблем, который может быть не полностью определен или не может гарантировать правильные или оптимальные результаты, особенно в проблемных областях, где нет четко определенного правильного или оптимального результата. ^[3] Например, рекомендательные системы социальных сетей полагаются на эвристику таким образом, что, хотя в популярных средствах массовой информации 21-го века их широко называют «алгоритмами», они не могут дать правильные результаты из-за характера проблемы.

В качестве эффективного метода алгоритм может быть выражен в пределах конечного объема пространства и времени ^[4] и на четко определенном формальном языке ^[5] для вычисления функции . ^[6] Начиная с начального состояния и начального ввода (возможно, пустого ), ^[7] инструкции описывают вычисление, которое при выполнении проходит через конечное ^[8] число четко определенных последовательных состояний, в конечном итоге производя «выход» ^{[ 9]} и завершается в конечном конечном состоянии. Переход от одного состояния к другому не обязательно является детерминированным ; некоторые алгоритмы, известные как рандомизированные алгоритмы , включают случайный ввод. ^[10]

Этимология

Около 825 года нашей эры персидский ученый и эрудит Мухаммад ибн Муса аль-Хорезми написал «Китаб аль-Хисаб аль-хинди» («Книга индийских вычислений») и « Китаб аль-джам' ва'ль-тафрик аль-Хисаб аль-хинди» («Дополнение»). и вычитание в индийской арифметике»). ^[1] В начале XII века появились латинские переводы упомянутых текстов аль-Хорезми, включающие индуистско-арабскую систему счисления и арифметику , например, Liber Alghoarismi de practica arismetrice , приписываемую Иоанну Севильскому , и Liber Algorismi de numero Indorum , приписываемую Аделарду Батскому . ^[2] Таким образом, alghoarismi или algorismi — это латинизация имени Аль-Хорезми; текст начинается с фразы Dixit Algorismi , или «Так говорил Аль-Хорезми». ^[3] Около 1230 года было засвидетельствовано использование английского слова «алгоризм» , а затем Чосером в 1391 году английский язык принял французский термин. ^{[4] [5] [ нужны разъяснения ]} В 15 веке под влиянием греческого слова ἀριθμός ( арифмос , «число»; ср. «арифметика») латинское слово было изменено на алгоритмус . ^{[ нужна цитата ]}

Определение

Одним из неофициальных определений является «набор правил, который точно определяет последовательность операций», ^{[11] [ для проверки требуется цитата ]} , который включает в себя все компьютерные программы (включая программы, которые не выполняют числовые вычисления) и (например) любые предписанная бюрократическая процедура ^[12] или рецепт из кулинарной книги . ^[13] В общем, программа является алгоритмом только в том случае, если она в конце концов останавливается ^[14] — даже несмотря на то, что бесконечные циклы иногда могут оказаться желательными. Булос, Джеффри и 1974, 1999 определяют алгоритм как набор инструкций для определения результата, заданных явно в форме, которой может следовать либо вычислительная машина, либо человек, который может выполнять только определенные элементарные операции с символами . ^[15]

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

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

История

Древние алгоритмы

С древности были засвидетельствованы пошаговые процедуры решения математических задач. Сюда входят вавилонская математика (около 2500 г. до н. э.), ^[16] египетская математика (около 1550 г. до н. э.), ^[16] индийская математика (около 800 г. до н. э. и позже), ^{[17] [18]} Оракул Ифа (около 500 г. до н. э.), Греческая математика (около 240 г. до н.э.) ^[19] и арабская математика (около 800 г. н.э.). ^[20]

Самые ранние свидетельства существования алгоритмов можно найти в вавилонской математике древней Месопотамии (современный Ирак). Шумерская глиняная табличка, найденная в Шуруппаке недалеко от Багдада и датированная ок.  В 2500 году до нашей эры был описан самый ранний алгоритм деления . ^[16] Во времена династии Хаммурапи ок.  1800  – ок.  1600 г. до н.э. на вавилонских глиняных табличках описаны алгоритмы вычисления формул. ^[21] Алгоритмы также использовались в вавилонской астрономии . Вавилонские глиняные таблички описывают и используют алгоритмические процедуры для расчета времени и места важных астрономических событий. ^[22]

Алгоритмы арифметики также встречаются в древнеегипетской математике , начиная с Математического папируса Ринда ок.  1550 г. до н.э. ^[16] Позднее алгоритмы использовались в древней эллинистической математике . Двумя примерами являются «Решето Эратосфена» , которое было описано во «Введении в арифметику» Никомаха , ^{[23] [19] : гл. 9.2} , и алгоритм Евклида , который был впервые описан в «Началах» Евклида ( ок.  300 г. до н. э. ). ^{[19] : Глава 9.1.} Примеры древнеиндийской математики включают « Шулба-сутры» , школу Кералы и «Брахмаспхутасиддханту» . ^[17]

Первый криптографический алгоритм для расшифровки зашифрованного кода был разработан Аль-Кинди , арабским математиком 9-го века, в «Рукописи о расшифровке криптографических сообщений» . Он дал первое описание криптоанализа с помощью частотного анализа , самого раннего алгоритма взлома кода. ^[20]

Компьютеры

Весовые часы

Болтер считает изобретение часов с весовым приводом «ключевым изобретением [Европы в Средневековье]». В частности, он отдает должное механизму спускового механизма ^[24] , который обеспечивает нам тиканье и такт механических часов. «Точная автоматическая машина» ^[25] сразу привела к «механическим автоматам », начиная с XIII века, и, наконец, к «вычислительным машинам» — разностной машине и аналитическим машинам Чарльза Бэббиджа и графини Ады Лавлейс , середина XIX века. ^[26] Лавлейсу приписывают первое создание алгоритма, предназначенного для обработки на компьютере — аналитической машины Бэббиджа, первого устройства, считавшегося настоящим Тьюринг-полным компьютером, а не просто калькулятором — и иногда его называют «первым программистом в истории», как В результате, хотя полная реализация второго устройства Бэббиджа будет реализована только спустя десятилетия после ее жизни.

Электромеханическое реле

Белл и Ньюэлл (1971) указывают, что жаккардовый ткацкий станок (1801 г.), предшественник карт Холлерита (перфокарты, 1887 г.), и «технологии телефонной коммутации» были корнями дерева, приведшего к разработке первых компьютеров. ^[27] К середине 19-го века телеграф , предшественник телефона, использовался во всем мире, его дискретное и различимое кодирование букв в виде «точек и тире» было обычным звуком. К концу 19 века стала использоваться бегущая лента ( около  1870-х годов ), а также карты Холлерита при переписи населения США 1890 года. Затем появился телетайп ( ок.  1910 г. ) с перфолентой, в которой код Бодо был записан на ленте.

Телефонно-коммутационные сети электромеханических реле (изобретены в 1835 г.) легли в основу работ Джорджа Стибитца (1937 г.), изобретателя цифрового суммирующего устройства. Работая в Bell Laboratories, он наблюдал «обременительное» использование механических калькуляторов с шестернями. «Однажды вечером в 1937 году он пошел домой, намереваясь проверить свою идею... Когда работа была окончена, Стибиц сконструировал устройство двоичного сложения». ^[28] Математик Мартин Дэвис поддержал особую важность электромеханического реле ^{[29] .}

Формализация

Диаграмма Ады Лавлейс из « Note G », первого опубликованного компьютерного алгоритма.

В 1928 году началась частичная формализация современной концепции алгоритмов с попыток решить Entscheidungsproblem ( проблему принятия решений), поставленную Дэвидом Гильбертом . Более поздние формализации были оформлены как попытки определить « эффективную вычислимость » ^[30] или «эффективный метод». ^[31] Эти формализации включали рекурсивные функции Гёделя – Эрбрана – Клини 1930, 1934 и 1935 годов, лямбда-исчисление Алонзо Черча 1936 года, формулу 1 Эмиля Поста 1936 года и машины Тьюринга Алана Тьюринга 1936–37 годов. и 1939 год.

Представительства

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

Машины Тьюринга

Существует большое разнообразие возможных представлений, и можно выразить данную программу машины Тьюринга как последовательность машинных таблиц (подробнее см. Конечный автомат , таблица переходов состояний и таблица управления ), как блок-схемы и драконовые диаграммы (см. диаграмму состояний для получения дополнительной информации) или как форму элементарного машинного кода или ассемблерного кода , называемого «наборами четверок» ( более подробную информацию см. в разделе «Машина Тьюринга» ). Представления алгоритмов также можно разделить на три общепринятых уровня описания машины Тьюринга: описание высокого уровня, описание реализации и формальное описание. ^[32] Высокоуровневое описание описывает качества самого алгоритма, игнорируя то, как он реализован на машине Тьюринга. ^[32] Описание реализации описывает общий способ, которым машина перемещает голову и сохраняет данные для выполнения алгоритма, но не дает точных состояний. ^[32] В наиболее подробном формальном описании дается точная таблица состояний и список переходов машины Тьюринга. ^[32]

Представление блок-схемы

Графическое средство, называемое блок-схемой, предлагает способ описания и документирования алгоритма (и соответствующей ему компьютерной программы). Подобно потоку программы на машине Мински, блок-схема всегда начинается вверху страницы и продолжается вниз. Его основных символов всего четыре: направленная стрелка, показывающая ход выполнения программы, прямоугольник (SEQUENCE, GOTO), ромб (IF-THEN-ELSE) и точка (ИЛИ-связь). Канонические структуры Бема – Якопини состоят из этих примитивных форм. Подструктуры могут «вкладываться» в прямоугольники, но только в том случае, если из надстройки происходит единственный выход. Символы и их использование для построения канонических структур показаны на схеме. ^[33]

Алгоритмический анализ

Часто важно знать, сколько определенного ресурса (например, времени или памяти) теоретически требуется для данного алгоритма. Разработаны методы анализа алгоритмов получения таких количественных ответов (оценок); например, алгоритм, который складывает элементы списка из n чисел, потребует времени ⁠ ⁠ ${\displaystyle O(n)}$ с использованием обозначения big O. Алгоритму всегда нужно помнить только два значения: сумму всех элементов на данный момент и его текущую позицию во входном списке. Поэтому говорят, что требуется пространство ⁠ ⁠ ${\displaystyle O(1)}$ , если пространство, необходимое для хранения входных чисел, не учитывается, или ⁠ ⁠, ${\displaystyle O(n)}$ если оно учитывается.

Разные алгоритмы могут выполнять одну и ту же задачу с разным набором инструкций за меньшее или большее время, пространство или « усилия », чем другие. Например, алгоритм двоичного поиска (со стоимостью ⁠ ⁠ ${\displaystyle O(\log n)}$ ) превосходит последовательный поиск (стоимость ⁠ ⁠ ${\displaystyle O(n)}$ ) при использовании для поиска в таблицах в отсортированных списках или массивах.

Формальный против эмпирического

Анализ и изучение алгоритмов — это дисциплина информатики , которая часто практикуется абстрактно, без использования конкретного языка программирования или реализации. В этом смысле анализ алгоритмов похож на другие математические дисциплины, поскольку он фокусируется на основных свойствах алгоритма, а не на особенностях какой-либо конкретной реализации. Обычно для анализа используется псевдокод , поскольку это самое простое и общее представление. Однако в конечном итоге большинство алгоритмов обычно реализуются на определенных аппаратных/программных платформах, и их алгоритмическая эффективность в конечном итоге проверяется с использованием реального кода. Для решения «разовой» проблемы эффективность конкретного алгоритма может не иметь существенных последствий (если только n не чрезвычайно велико), но для алгоритмов, предназначенных для быстрого интерактивного, коммерческого или длительного научного использования, это может иметь решающее значение. Масштабирование от маленького n до большого n часто приводит к появлению неэффективных алгоритмов, которые в остальном безвредны.

Эмпирическое тестирование полезно, поскольку оно может выявить неожиданные взаимодействия, влияющие на производительность. Тесты можно использовать для сравнения возможных улучшений алгоритма до/после после оптимизации программы. Однако эмпирические тесты не могут заменить формальный анализ, и их не так просто выполнить честно. ^[34]

Эффективность исполнения

Чтобы проиллюстрировать потенциальные улучшения, возможные даже в хорошо зарекомендовавших себя алгоритмах, недавнее важное нововведение, касающееся алгоритмов БПФ (широко используемых в области обработки изображений), может сократить время обработки до 1000 раз для таких приложений, как медицинская визуализация. ^[35] В общем, улучшение скорости зависит от особых свойств задачи, которые очень распространены в практических приложениях. ^[36] Ускорение такого масштаба позволяет вычислительным устройствам, широко использующим обработку изображений (например, цифровым камерам и медицинскому оборудованию), потреблять меньше энергии.

Дизайн

Разработка алгоритма относится к методу или математическому процессу решения проблем и разработки алгоритмов. Разработка алгоритмов является частью многих теорий решения, таких как « разделяй и властвуй» или динамическое программирование в рамках исследования операций . Методы проектирования и реализации алгоритмов также называются шаблонами проектирования алгоритмов ^[37] с примерами, включая шаблон метода шаблона и шаблон декоратора. Одним из наиболее важных аспектов разработки алгоритмов является эффективность использования ресурсов (время выполнения, использование памяти); Обозначение «большое О» используется, например, для описания роста алгоритма во время выполнения по мере увеличения размера входных данных. ^[38]

Структурированное программирование

Согласно тезису Чёрча-Тьюринга , любой алгоритм может быть вычислен с помощью модели, известной как полная по Тьюрингу . Фактически было продемонстрировано, что для полноты по Тьюрингу требуется только четыре типа инструкций — условный GOTO, безусловный GOTO, присваивание и HALT. Однако Кемени и Курц отмечают, что, хотя «недисциплинированное» использование безусловных GOTO и условных IF-THEN GOTO может привести к « спагетти-коду », программист может писать структурированные программы, используя только эти инструкции; с другой стороны, «также возможно и не слишком сложно писать плохо структурированные программы на структурированном языке». ^[39] Таусворт дополняет три канонические структуры Бема-Якопини : ^[40] ПОСЛЕДОВАТЕЛЬНОСТЬ, ЕСЛИ-ТО-ЛИБО и ПОКА-ДЕЛАТЬ, еще двумя: ДЕЛАТЬ-ПОКА и СЛУЧАЙ. ^[41] Дополнительным преимуществом структурированной программы является то, что ее корректность можно доказать с помощью математической индукции . ^[42]

Легальное положение

Алгоритмы сами по себе обычно не патентоспособны. В Соединенных Штатах заявка, состоящая исключительно из простых манипуляций с абстрактными понятиями, числами или сигналами, не представляет собой «процессы» (USPTO 2006), поэтому алгоритмы не подлежат патентованию (как в деле Готшалк против Бенсона ). Однако практическое применение алгоритмов иногда патентоспособно. Например, в деле Даймонд против Дира применение простого алгоритма обратной связи для отверждения синтетического каучука было признано патентоспособным. Патентование программного обеспечения является спорным ^[43] , и существуют критикуемые патенты, связанные с алгоритмами, особенно алгоритмами сжатия данных , такие как патент LZW компании Unisys . Кроме того, некоторые криптографические алгоритмы имеют ограничения на экспорт (см. экспорт криптографии ).

Классификация

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

По реализации

Один из способов классификации алгоритмов — по средствам реализации.

Рекурсия

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

Последовательный, параллельный или распределенный

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

Детерминированный или недетерминированный

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

Точный или приблизительный

Хотя многие алгоритмы достигают точного решения, алгоритмы аппроксимации ищут приближение, которое ближе к истинному решению. Аппроксимация может быть достигнута с использованием детерминированной или случайной стратегии. Такие алгоритмы имеют практическую ценность для решения многих сложных задач. Одним из примеров приближенного алгоритма является задача о рюкзаке , где имеется набор заданных предметов. Его цель – упаковать рюкзак так, чтобы получить максимальную общую ценность. Каждый предмет имеет некоторый вес и некоторую ценность. Общий вес, который можно перевезти, не превышает некоторого фиксированного числа X. Таким образом, решение должно учитывать вес предметов, а также их стоимость. ^[44]

Квантовый алгоритм

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

По дизайнерской парадигме

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

Грубая сила или полный перебор

Грубая сила — это метод решения проблем, который предполагает систематическое перебор всех возможных вариантов, пока не будет найдено оптимальное решение. Этот подход может занять очень много времени, поскольку требует анализа всех возможных комбинаций переменных. Однако его часто используют, когда другие методы недоступны или слишком сложны. Грубую силу можно использовать для решения множества задач, включая поиск кратчайшего пути между двумя точками и взлом паролей.

Разделяй и властвуй

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

Поиск и перечисление

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

Рандомизированный алгоритм

Такие алгоритмы делают некоторые выборы случайным (или псевдослучайным) образом. Они могут быть очень полезны при поиске приближенных решений задач, для которых поиск точных решений может быть непрактичным (см. эвристический метод ниже). Известно, что для некоторых из этих задач самые быстрые приближения должны включать в себя некоторую случайность . ^[45] Могут ли рандомизированные алгоритмы с полиномиальной временной сложностью быть самым быстрым алгоритмом для некоторых задач — открытый вопрос, известный как проблема P и NP . Существует два больших класса таких алгоритмов:

1. Алгоритмы Монте-Карло возвращают правильный ответ с высокой вероятностью. Например, RP является их подклассом, который работает за полиномиальное время .
2. Алгоритмы Лас-Вегаса всегда возвращают правильный ответ, но время их работы ограничено только вероятностно, например ZPP .

Уменьшение сложности

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

обратное отслеживание

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

Проблемы оптимизации

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

Линейное программирование

При поиске оптимальных решений линейной функции, связанной с ограничениями линейного равенства и неравенства, ограничения задачи могут быть использованы непосредственно для получения оптимальных решений. Существуют алгоритмы, способные решить любую задачу этой категории, например популярный симплекс-алгоритм . ^[46] Проблемы, которые можно решить с помощью линейного программирования, включают задачу максимального потока для ориентированных графов. Если задача дополнительно требует, чтобы одно или несколько неизвестных были целыми числами, тогда это классифицируется как целочисленное программирование . Алгоритм линейного программирования может решить такую ​​задачу, если можно доказать, что все ограничения на целочисленные значения поверхностны, т. е. решения в любом случае удовлетворяют этим ограничениям. В общем случае используется специализированный алгоритм или алгоритм, находящий приближенные решения, в зависимости от сложности задачи.

Динамическое программирование

Когда проблема имеет оптимальные подструктуры (это означает, что оптимальное решение проблемы может быть построено из оптимальных решений подзадач) и перекрывающиеся подзадачи (то есть одни и те же подзадачи используются для решения многих разных экземпляров проблемы), более быстрый подход, называемый динамическим программированием, позволяет избежать повторного вычисления решений, которые уже вычислены. Например, алгоритм Флойда-Уоршалла , кратчайший путь к цели из вершины во взвешенном графе можно найти, используя кратчайший путь к цели из всех соседних вершин. Динамическое программирование и мемоизация идут рука об руку. Основное различие между динамическим программированием и «разделяй и властвуй» заключается в том, что подзадачи в «разделяй и властвуй» более или менее независимы, тогда как в динамическом программировании подзадачи перекрываются. Разница между динамическим программированием и простой рекурсией заключается в кэшировании или запоминании рекурсивных вызовов. Когда подзадачи независимы и нет повторения, запоминание не помогает; следовательно, динамическое программирование не является решением всех сложных проблем. Используя мемоизацию или ведение таблицы уже решенных подзадач, динамическое программирование сводит экспоненциальный характер многих задач к полиномиальной сложности.

Жадный метод

Жадный алгоритм похож на алгоритм динамического программирования тем, что он работает, исследуя подструктуры, в данном случае не проблемы, а заданного решения. Такие алгоритмы начинаются с некоторого решения, которое может быть задано или было построено каким-либо образом, и улучшают его путем внесения небольших модификаций. Для некоторых задач они могут найти оптимальное решение, тогда как для других они останавливаются на локальных оптимумах , то есть на решениях, которые не могут быть улучшены алгоритмом, но не являются оптимальными. Наиболее популярное использование жадных алгоритмов — поиск минимального остовного дерева, где с помощью этого метода возможно найти оптимальное решение. Huffman Tree , Kruskal , Prim , Sollin — жадные алгоритмы, способные решить эту задачу оптимизации.

Эвристический метод

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

Примеры

Один из простейших алгоритмов — найти наибольшее число в списке чисел случайного порядка. Чтобы найти решение, необходимо просмотреть каждое число в списке. Отсюда следует простой алгоритм, который можно сформулировать в высокоуровневом описании в английской прозе следующим образом:

Описание высокого уровня:

1. Если в наборе нет чисел, то нет и старшего числа.
2. Предположим, что первое число в наборе является самым большим числом в наборе.
3. Для каждого оставшегося числа в наборе: если это число больше текущего самого большого числа, считайте это число самым большим числом в наборе.
4. Если в наборе не осталось чисел для перебора, считайте, что текущее наибольшее число является самым большим числом в наборе.

(Квази-)формальное описание: Написанное прозой, но гораздо ближе к языку высокого уровня компьютерной программы, ниже приводится более формальное кодирование алгоритма в псевдокоде или пиджин-коде :

Алгоритм наибольшего числаВходные данные: список чисел L .Выходные данные: Самое большое число в списке L .

если  L.size = 0 вернуть нулевой наибольший ← L [0] для каждого  элемента  в  L , сделать  , если  элемент > самый большой , то  самый большой ← элемент вернуть  самый большой

• « ←» означает присвоение . Например, « самый большой элемент ← » означает, что значение самого большого изменяется на значение элемента .
• « return » завершает алгоритм и выводит следующее значение.

Смотрите также

• Математический портал
• Портал компьютерного программирования

• Абстрактная машина
• АЛГОЛ
• Отвращение к алгоритму
• Алгоритмическая инженерия
• Характеристики алгоритма
• Алгоритмическое смещение
• Алгоритмическая композиция
• Алгоритмические сущности
• Алгоритмический синтез
• Алгоритмическая методика
• Алгоритмическая топология
• Мусор на входе, мусор на выходе
• Введение в алгоритмы (учебник)
• Правительство по алгоритму
• Список алгоритмов
• Список общих тем алгоритмов
• Регулирование алгоритмов
• Теория вычислений
  • Теория вычислимости
  • Теория сложности вычислений
• Вычислительная математика

Примечания

1. «Определение АЛГОРИТМА». Интернет-словарь Мерриам-Вебстера . Архивировано из оригинала 14 февраля 2020 года . Проверено 14 ноября 2019 г.
2. Блэр, Энн, Дугид, Пол, Гоинг, Аня-Сильвия и Графтон, Энтони. Информация: Исторический спутник, Принстон: Princeton University Press, 2021. с. 247
3. Дэвид А. Гроссман, Офир Фридер, Информационный поиск: алгоритмы и эвристика , 2-е издание, 2004 г., ISBN 1402030045 
4. «Например, любой классический математический алгоритм можно описать конечным числом английских слов» (Роджерс 1987:2).
5. Четко определено в отношении агента, выполняющего алгоритм: «Существует вычислительный агент, обычно человек, который может реагировать на инструкции и выполнять вычисления» (Rogers 1987:2).
6. «Алгоритм - это процедура вычисления функции (относительно некоторых выбранных обозначений целых чисел) ... это ограничение (числовых функций) не приводит к потере общности» (Rogers 1987: 1).
7. «Алгоритм имеет ноль или более входных данных, то есть величин , которые ему задаются изначально до начала работы алгоритма» (Кнут 1973:5).
8. «Процедура, которая обладает всеми характеристиками алгоритма, за исключением того, что ей, возможно, не хватает конечности, может быть названа« вычислительным методом » » (Кнут 1973:5).
9. «Алгоритм имеет один или несколько выходных данных, то есть величины, которые имеют определенное отношение к входным данным» (Кнут 1973:5).
10. Является ли процесс со случайными внутренними процессами (не включая входные) алгоритмом, является дискуссионным. Роджерс полагает, что: «вычисления выполняются дискретно, поэтапно, без использования непрерывных методов или аналоговых устройств... проводятся детерминированно, без обращения к случайным методам или устройствам, например игральным костям» (Rogers 1987:2) .
11. Стоун 1973: 4
12. Симановский, Роберто (2018). Алгоритм смерти и другие цифровые дилеммы. Несвоевременные размышления. Том. 14. Перевод Чейза, Джефферсона. Кембридж, Массачусетс: MIT Press. п. 147. ИСБН 9780262536370. Архивировано из оригинала 22 декабря 2019 года . Проверено 27 мая 2019 г. [...] следующий уровень абстракции центральной бюрократии: глобально действующие алгоритмы.
13. Дитрих, Эрик (1999). "Алгоритм". В Уилсоне, Роберт Эндрю; Кейл, Фрэнк С. (ред.). Энциклопедия когнитивных наук Массачусетского технологического института. Библиотека MIT Cognet. Кембридж, Массачусетс: MIT Press (опубликовано в 2001 г.). п. 11. ISBN 9780262731447. Проверено 22 июля 2020 г. Алгоритм — это рецепт, метод или техника выполнения чего-либо.
14. Стоун требует, чтобы «он заканчивался за конечное число шагов» (Stone 1973:7–8).
15. Булос и Джеффри 1974,1999:19
16. Шабер, Жан-Люк (2012). История алгоритмов: от камешка до микрочипа . Springer Science & Business Media. стр. 7–8. ISBN 9783642181924.
17. Шрирам, MS (2005). «Алгоритмы в индийской математике». В Эмче, Джерард Г.; Шридхаран, Р.; Шринивас, доктор медицины (ред.). Вклад в историю индийской математики . Спрингер. п. 153. ИСБН 978-93-86279-25-5.
18. Хаяши, Т. (1 января 2023 г.). Брахмагупта. Британская энциклопедия.
19. Cooke, Роджер Л. (2005). История математики: Краткий курс . Джон Уайли и сыновья. ISBN 978-1-118-46029-0.
20. Дули, Джон Ф. (2013). Краткая история криптологии и криптографических алгоритмов . Springer Science & Business Media. стр. 12–3. ISBN 9783319016283.
21. Кнут, Дональд Э. (1972). «Древние вавилонские алгоритмы» (PDF) . Коммун. АКМ . 15 (7): 671–677. дои : 10.1145/361454.361514. ISSN  0001-0782. S2CID  7829945. Архивировано из оригинала (PDF) 24 декабря 2012 г.
22. Аабо, Асгер (2001). Эпизоды из ранней истории астрономии . Нью-Йорк: Спрингер. стр. 40–62. ISBN 978-0-387-95136-2.
23. Аст, Кортни. «Эратосфен». Государственный университет Уичито: факультет математики и статистики. Архивировано из оригинала 27 февраля 2015 года . Проверено 27 февраля 2015 г.
24. Болтер 1984:24
25. Болтер 1984:26
26. Болтер 1984: 33–34, 204–206.
27. Диаграмма Белла и Ньюэлла 1971:39, ср. Дэвис 2000
28. Мелина Хилл, корреспондент Valley News, Тинкерер получает место в истории , Valley News Западный Ливан, штат Нью-Хэмпшир, четверг, 31 марта 1983 г., стр. 13.
29. Дэвис 2000:14
30. Клини 1943 в Дэвисе 1965: 274
31. Россер 1939 в Дэвисе 1965: 225
32. Sipser 2006: 157
33. см. Таусворт, 1977 г.
34. Кригель, Ганс-Петер ; Шуберт, Эрих; Зимек, Артур (2016). «(Черное) искусство оценки во время выполнения: сравниваем ли мы алгоритмы или реализации?». Знания и информационные системы . 52 (2): 341–378. дои : 10.1007/s10115-016-1004-2. ISSN  0219-1377. S2CID  40772241.
35. Джиллиан Конахан (январь 2013 г.). «Лучшая математика делает сети передачи данных быстрее». Discovermagazine.com. Архивировано из оригинала 13 мая 2014 года . Проверено 13 мая 2014 г.
36. Хайтам Хассание, Петр Индик , Дина Катаби и Эрик Прайс, «Симпозиум ACM-SIAM по дискретным алгоритмам (SODA). Архивировано 4 июля 2013 г., в Wayback Machine , Киото, январь 2012 г. См. Также веб-страницу sFFT, архивированную 21 февраля. , 2012 год, в Wayback Machine .
37. Гудрич, Майкл Т .; Тамассия, Роберто (2002). Разработка алгоритмов: основы, анализ и примеры из Интернета. Джон Уайли и сыновья, Inc. ISBN 978-0-471-38365-9. Архивировано из оригинала 28 апреля 2015 года . Проверено 14 июня 2018 г.
38. «Обозначение Big-O (статья) | Алгоритмы» . Ханская академия . Проверено 3 июня 2024 г.
39. Джон Г. Кемени и Томас Э. Курц, 1985 г. «Возвращение к основам: история, коррупция и будущее языка» , Addison-Wesley Publishing Company, Inc. Ридинг, Массачусетс, ISBN 0-201-13433-0 . 
40. Таусворт 1977: 101
41. Таусворт 1977: 142
42. Кнут 1973, раздел 1.2.1, расширенный Таусвортом 1977 на стр. 100 и далее и в главе 9.1.
43. «Эксперты: поощряет ли патентная система инновации?» Журнал "Уолл Стрит . 16 мая 2013 г. ISSN  0099-9660 . Проверено 29 марта 2017 г.
44. Келлерер, Ганс; Пферши, Ульрих; Пизингер, Дэвид (2004). Проблемы с рюкзаком | Ганс Келлерер | Спрингер. Спрингер. дои : 10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. S2CID  28836720. Архивировано из оригинала 18 октября 2017 года . Проверено 19 сентября 2017 г.
45. Например, объем выпуклого многогранника (описанного с помощью оракула членства) может быть аппроксимирован с высокой точностью с помощью алгоритма рандомизированного полиномиального времени, но не детерминированного: см. Дайер, Мартин; Фриз, Алан; Каннан, Рави (январь 1991 г.). «Случайный полиномиальный алгоритм аппроксимации объема выпуклых тел». Дж. АКМ . 38 (1): 1–17. CiteSeerX 10.1.1.145.4600 . дои : 10.1145/102782.102783. S2CID  13268711. 
46. Джордж Б. Данциг и Мукунд Н. Тапа. 2003. Линейное программирование 2: теория и расширения . Спрингер-Верлаг.

Библиография

• Акст, П (1959). «О субрекурсивной иерархии и примитивно-рекурсивных степенях». Труды Американского математического общества . 92 (1): 85–105. дои : 10.2307/1993169 . JSTOR  1993169.
• Белл, К. Гордон и Ньюэлл, Аллен (1971), Компьютерные структуры: материалы для чтения и примеры , McGraw – Hill Book Company, Нью-Йорк. ISBN 0-07-004357-4 . 
• Бласс, Андреас ; Гуревич, Юрий (2003). «Алгоритмы: поиск абсолютных определений» (PDF) . Бюллетень Европейской ассоциации теоретической информатики . 81 . Архивировано (PDF) оригинала 9 октября 2022 г.Включает библиографию из 56 ссылок.
• Болтер, Дэвид Дж. (1984). Человек Тьюринга: западная культура в компьютерный век (изд. 1984 г.). Чапел-Хилл, Северная Каролина: Издательство Университета Северной Каролины. ISBN 978-0-8078-1564-9., ISBN 0-8078-4108-0 
• Булос, Джордж ; Джеффри, Ричард (1999) [1974]. Вычислимость и логика (4-е изд.). Издательство Кембриджского университета, Лондон. ISBN 978-0-521-20402-6.: см. Глава 3 «Машины Тьюринга» , где обсуждаются «некоторые перечислимые множества, которые не являются эффективно (механически) перечислимыми».
• Бургин, Марк (2004). Суперрекурсивные алгоритмы . Спрингер. ISBN 978-0-387-95569-8.
• Кампаньоло, М.Л., Мур, К. и Коста, Дж.Ф. (2000) Аналоговая характеристика субрекурсивных функций. В Proc. 4-й конференции по действительным числам и компьютерам , Университет Оденсе, стр. 91–109.
• Черч, Алонсо (1936). «Неразрешимая проблема элементарной теории чисел». Американский журнал математики . 58 (2): 345–363. дои : 10.2307/2371045. JSTOR  2371045.Перепечатано в «Неразрешимом» , с. 89 и след. Первое выражение «Тезиса Церкви». См., в частности, страницу 100 ( «Неразрешимое» ), где он определяет понятие «эффективной вычислимости» в терминах «алгоритма» и использует слово «завершает» и т. д.
• Черч, Алонсо (1936). «Заметка о проблеме Entscheidungs». Журнал символической логики . 1 (1): 40–41. дои : 10.2307/2269326. JSTOR  2269326. S2CID  42323521. Черч, Алонсо (1936). «Исправление к примечанию к проблеме Entscheidungs». Журнал символической логики . 1 (3): 101–102. дои : 10.2307/2269030. JSTOR  2269030. S2CID  5557237.Перепечатано в «Неразрешимом» , с. 110ff. Чёрч показывает, что проблема Entscheidungs ​​неразрешима примерно на 3 страницах текста и 3 страницах сносок.
• Даффа, Али Абдулла аль- (1977). Вклад мусульман в математику . Лондон: Крум Хелм. ISBN 978-0-85664-464-1.
• Дэвис, Мартин (1965). Неразрешимое: основные статьи о неразрешимых предложениях, неразрешимых проблемах и вычислимых функциях . Нью-Йорк: Рэйвен Пресс. ISBN 978-0-486-43228-1.Дэвис дает комментарий перед каждой статьей. Включены статьи Гёделя , Алонзо Чёрча , Тьюринга , Россера , Клини и Эмиля Поста ; те, которые цитируются в статье, перечислены здесь по имени автора.
• Дэвис, Мартин (2000). Логические машины: математики и происхождение компьютера . Нью-Йорк: WW Nortion. ISBN 978-0-393-32229-3.Дэвис предлагает краткие биографии Лейбница , Буля , Фреге , Кантора , Гильберта , Гёделя и Тьюринга с фон Нейманом в роли злодея, похищающего шоу. Очень краткие биографии Жозефа-Мари Жаккарда , Бэббиджа , Ады Лавлейс , Клода Шеннона , Говарда Эйкена и др.
•  Эта статья включает общедоступные материалы Пола Э. Блэка. "алгоритм". Словарь алгоритмов и структур данных . НИСТ .
• Дин, Тим (2012). «Эволюция и моральное разнообразие». Балтийский международный ежегодник познания, логики и коммуникации . 7 . дои : 10.4148/biyclc.v7i0.1775 .
• Деннетт, Дэниел (1995). Опасная идея Дарвина . Нью-Йорк: Touchstone/Simon & Schuster. стр. 32–36. ISBN 978-0-684-80290-9.
• Дилсон, Джесси (2007). Счеты ((1968, 1994) изд.). Пресса Святого Мартина, Нью-Йорк. ISBN 978-0-312-10409-2., ISBN 0-312-10409-X 
• Юрий Гуревич , Последовательные абстрактные конечные автоматы захватывают последовательные алгоритмы, Транзакции ACM в вычислительной логике, Том 1, № 1 (июль 2000 г.), стр. 77–111. Включает библиографию из 33 источников.
• ван Хейеноорт, Жан (2001). От Фреге до Гёделя, Справочник по математической логике, 1879–1931 ((1967) изд.). Издательство Гарвардского университета, Кембридж. ISBN 978-0-674-32449-7., 3-е издание 1976 г. [?], ISBN 0-674-32449-8 (pbk.) 
• Ходжес, Эндрю (1983). Алан Тьюринг: Загадка . Нью-Йорк: Саймон и Шустер . ISBN 978-0-671-49207-6., ISBN 0-671-49207-1 . См. Глава «Дух истины» содержит историю, ведущую к его доказательству, и обсуждение его. 
• Клини, Стивен К. (1936). «Общерекурсивные функции натуральных чисел». Математические Аннален . 112 (5): 727–742. дои : 10.1007/BF01565439. S2CID  120517999. Архивировано из оригинала 3 сентября 2014 года . Проверено 30 сентября 2013 г.Представлено Американскому математическому обществу в сентябре 1935 года. Перепечатано в The Undecidable , с. 237 и далее. Определение «общей рекурсии» Клини (известное теперь как мю-рекурсия) было использовано Чёрчем в его статье 1935 года «Неразрешимая проблема элементарной теории чисел» , в которой было доказано, что «проблема принятия решения» «неразрешима» (т. е. имеет отрицательный результат).
• Клини, Стивен К. (1943). «Рекурсивные предикаты и квантификаторы». Труды Американского математического общества . 53 (1): 41–73. дои : 10.2307/1990131 . JSTOR  1990131.Перепечатано в «Неразрешимом» , с. 255 и далее. Клини уточнил свое определение «общей рекурсии» и в главе «12. Алгоритмические теории» перешел к постулированию «Тезиса I» (стр. 274); позже он повторит этот тезис (Клин 1952:300) и назовет его «Тезис Чёрча» (Клин 1952:317) (т.е. тезис Чёрча ).
• Клини, Стивен К. (1991) [1952]. Введение в метаматематику (Десятое изд.). Издательство Северной Голландии. ISBN 978-0-7204-2103-3.
• Кнут, Дональд (1997). Фундаментальные алгоритмы, третье издание . Ридинг, Массачусетс: Аддисон-Уэсли. ISBN 978-0-201-89683-1.
• Кнут, Дональд (1969). Том 2/Получисловые алгоритмы, Искусство компьютерного программирования, первое издание . Ридинг, Массачусетс: Аддисон-Уэсли.
• Косовский, Н. К. Элементы математической логики и ее применение к теории субрекурсивных алгоритмов , Изд-во ЛГУ, Ленинград, 1981
• Ковальски, Роберт (1979). «Алгоритм=Логика+Управление». Коммуникации АКМ . 22 (7): 424–436. дои : 10.1145/359131.359136 . S2CID  2509896.
• А. А. Марков (1954) Теория алгоритмов . [Перевод Жака Шорра-Кона и сотрудников PST] Выходные данные Москва, Академия наук СССР, 1954 г. [т. е. Иерусалим, Израильская программа научных переводов, 1961 г.; можно получить в Управлении технических служб Министерства торговли США, Вашингтон] Описание 444 стр. 28 см. Добавлено тп в Русский перевод трудов Математического института АН СССР, т. 42. Оригинальное название: Теория алгерифмов. [QA248.M2943 Библиотека Дартмутского колледжа. Министерство торговли США, Управление технических служб, номер OTS 60-51085.]
• Мински, Марвин (1967). Вычисления: конечные и бесконечные машины (первое изд.). Прентис-Холл, Энглвуд Клиффс, Нью-Джерси. ISBN 978-0-13-165449-5.Мински расширяет свою «...идею алгоритма - эффективной процедуры...» в главе 5.1 « Вычислимость, эффективные процедуры и алгоритмы». Бесконечные машины.
• Пост, Эмиль (1936). «Конечные комбинаторные процессы, формулировка I». Журнал символической логики . 1 (3): 103–105. дои : 10.2307/2269031. JSTOR  2269031. S2CID  40284503.Перепечатано в «Неразрешимом» , стр. 289 и далее. Пост определяет простой алгоритмический процесс, в котором человек пишет или стирает отметки, переходит от ящика к ящику и в конечном итоге останавливается, следуя списку простых инструкций. Клини цитирует это как один из источников своего «Тезиса I», так называемого тезиса Чёрча-Тьюринга .
• Роджерс, Хартли младший (1987). Теория рекурсивных функций и эффективная вычислимость . Массачусетский технологический институт Пресс. ISBN 978-0-262-68052-3.
• Россер, Дж. Б. (1939). «Неофициальное изложение доказательств теоремы Гёделя и теоремы Чёрча». Журнал символической логики . 4 (2): 53–60. дои : 10.2307/2269059. JSTOR  2269059. S2CID  39499392.Перепечатано в «Неразрешимом» , с. 223 и далее. Вот знаменитое определение «эффективного метода», данное Россером: «…метод, каждый шаг которого точно определен и который наверняка даст ответ за конечное число шагов… машина, которая затем решит любую задачу набор без вмешательства человека, кроме вставки вопроса и (позже) чтения ответа» (стр. 225–226, Неразрешимое )
• Сантос-Ланг, Кристофер (2015). «Подходы моральной экологии к машинной этике» (PDF) . Ин ван Рызевик, Саймон; Понтье, Маттейс (ред.). Машинная медицинская этика . Интеллектуальные системы, управление и автоматизация: наука и техника. Том. 74. Швейцария: Шпрингер. стр. 111–127. дои : 10.1007/978-3-319-08108-3_8. ISBN 978-3-319-08107-6. Архивировано (PDF) оригинала 9 октября 2022 г.
• Скотт, Майкл Л. (2009). Прагматика языков программирования (3-е изд.). Издательство Морган Кауфманн/Эльзевир. ISBN 978-0-12-374514-9.
• Сипсер, Майкл (2006). Введение в теорию вычислений. Издательская компания ПВС. ISBN 978-0-534-94728-6.
• Трезвый, Эллиотт; Уилсон, Дэвид Слоан (1998). Другим: эволюция и психология бескорыстного поведения . Кембридж: Издательство Гарвардского университета. ISBN 9780674930469.
• Стоун, Гарольд С. (1972). Введение в компьютерную организацию и структуры данных (изд. 1972 г.). МакГроу-Хилл, Нью-Йорк. ISBN 978-0-07-061726-1.См. в частности, первая глава под названием « Алгоритмы, машины Тьюринга и программы» . Его краткое неформальное определение: «...любая последовательность инструкций, которой может подчиняться робот, называется алгоритмом » (стр. 4).
• Таусворт, Роберт С. (1977). Стандартизированная разработка компьютерного программного обеспечения. Часть 1. Методы . Энглвуд Клиффс, штат Нью-Джерси: ISBN Prentice – Hall, Inc. 978-0-13-842195-3.
• Тьюринг, Алан М. (1936–37). «О вычислимых числах с применением к проблеме Entscheidungs». Труды Лондонского математического общества . Серия 2. 42 : 230–265. дои : 10.1112/plms/s2-42.1.230. S2CID  73712.. Исправления, там же, т. 1, с. 43 (1937), стр. 544–546. Перепечатано в «Неразрешимом» , с. 116 и далее. Знаменитая работа Тьюринга была завершена в качестве магистерской диссертации в Королевском колледже Кембриджа, Великобритания.
• Тьюринг, Алан М. (1939). «Системы логики, основанные на ординалах». Труды Лондонского математического общества . 45 : 161–228. дои : 10.1112/plms/s2-45.1.161. hdl : 21.11116/0000-0001-91CE-3 .Перепечатано в «Неразрешимом» , стр. 155 и далее. Статья Тьюринга, дающая определение понятию «оракул», была его докторской диссертацией в Принстоне.
• Ведомство США по патентам и товарным знакам (2006), 2106.02 **>Математические алгоритмы: 2100 Патентоспособность, Руководство по процедуре патентной экспертизы (MPEP). Последняя редакция: август 2006 г.

• Заславский, К. (1970). Математика народа йоруба и их соседей в Южной Нигерии. Двухлетний математический журнал колледжа, 1 (2), 76–99. https://doi.org/10.2307/3027363

дальнейшее чтение

• Белла, Роберт Нилли (1985). Привычки сердца: индивидуализм и приверженность в американской жизни. Беркли: Издательство Калифорнийского университета. ISBN 978-0-520-25419-0.
• Берлински, Дэвид (2001). Появление алгоритма: 300-летний путь от идеи к компьютеру. Книги урожая. ISBN 978-0-15-601391-8.
• Шабер, Жан-Люк (1999). История алгоритмов: от камешка до микрочипа . Спрингер Верлаг. ISBN 978-3-540-63369-3.
• Томас Х. Кормен; Чарльз Э. Лейзерсон; Рональд Л. Ривест; Клиффорд Стейн (2009). Введение в алгоритмы (3-е изд.). МТИ Пресс. ISBN 978-0-262-03384-8.
• Харель, Дэвид; Фельдман, Ишай (2004). Алгоритмика: дух вычислений . Аддисон-Уэсли. ISBN 978-0-321-11784-7.
• Герцке, Аллен Д.; МакРори, Крис (1998). «Концепция моральной экологии». В Лоулере, Питер Августин; МакКонки, Дейл (ред.). Сообщество и политическая мысль сегодня . Вестпорт, Коннектикут: Прегер .
• Кнут, Дональд Э. (2000). Избранные статьи по анализу алгоритмов. Архивировано 1 июля 2017 года в Wayback Machine . Стэнфорд, Калифорния: Центр изучения языка и информации.
• Кнут, Дональд Э. (2010). Избранные статьи по разработке алгоритмов. Архивировано 16 июля 2017 года в Wayback Machine . Стэнфорд, Калифорния: Центр изучения языка и информации.
• Уоллах, Венделл; Аллен, Колин (ноябрь 2008 г.). Моральные машины: обучение роботов правильному и неправильному . США: Издательство Оксфордского университета. ISBN 978-0-19-537404-9.
• Бликли, Крис (2020). Стихи, решающие головоломки: история и наука алгоритмов. Издательство Оксфордского университета. ISBN 978-0-19-885373-2.

Внешние ссылки

• "Алгоритм". Энциклопедия математики . ЭМС Пресс . 2001 [1994].
• Алгоритмы в Curlie
• Вайсштейн, Эрик В. «Алгоритм». Математический мир .
• Словарь алгоритмов и структур данных - Национальный институт стандартов и технологий

Хранилища алгоритмов

• Репозиторий алгоритмов Стоуни-Брук – Государственный университет Нью-Йорка в Стоуни-Брук
• Сборник алгоритмов ACM – Ассоциации вычислительной техники
• Stanford GraphBase. Архивировано 6 декабря 2015 г. в Wayback Machine - Стэнфордский университет .