Алгоритм

Блок -схема алгоритма ( алгоритм Евклида ) для вычисления наибольшего общего делителя (gcd) двух чисел a и b в местах с именами A и B. Алгоритм работает путем последовательных вычитаний в двух циклах: ЕСЛИ тест B ≥ A дает «да» или «верно» (точнее, число b в ячейке B больше или равно числу a в ячейке A) ТОГДА алгоритм указывает B ← B − A (это означает, что число b − a заменяет старое b). Аналогично, ЕСЛИ A > B, ТО A ← A − B. Процесс завершается, когда (содержимое) B равно 0, что дает НОД в A. (Алгоритм взят из Scott 2009:13; символы и стиль рисования из Tausworthe 1977) .

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

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

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

История

Понятие алгоритма существует с древних времен. Арифметические алгоритмы, такие как алгоритм деления , использовались древними вавилонскими математиками c. 2500 г. до н.э. и египетские математики ок. 1550 г. до н.э. ^[10] Позднее греческие математики в 240 г. до н.э. использовали алгоритмы решета Эратосфена для нахождения простых чисел и алгоритм Евклида для нахождения наибольшего общего делителя двух чисел. ^[11] Арабские математики , такие как аль-Кинди , в 9 веке использовали криптографические алгоритмы для взлома кода ., основанный на частотном анализе . ^[12]

Слово « алгоритм » происходит от имени персидского математика 9-го века Мухаммада ибн Муса аль-Хорезми , чья нисба (отождествляющая его с Хорезмом ) была латинизирована как Алгоритми ( арабизированный персидский الخوارزمی c. 780–850). ^{[13] [14]}

Мухаммад ибн Муса аль-Хорезми был математиком, астрономом , географом и ученым из Дома Мудрости в Багдаде , чье имя означает «уроженец Хорезма », региона, который был частью Большого Ирана , а ныне находится в Узбекистане . ^{[15] [16]} Около 825 года аль-Хорезми написал трактат на арабском языке об индийско-арабской системе счисления , который был переведен на латынь в XII веке. Рукопись начинается с фразы Dixit Algorizmi.(«Так говорил Аль-Хорезми»), где «Алгоризми» было латинизацией переводчиком имени Аль-Хорезми. ^[17] Аль-Хорезми был самым читаемым математиком в Европе в позднем Средневековье, прежде всего благодаря другой своей книге, « Алгебре » . ^[18] В позднесредневековой латыни algorismus , английское « алгоризм », искаженное его имя, просто означало «десятичную систему счисления». ^[19] В 15 веке под влиянием греческого слова ἀριθμός ( арифмос ), «число» ( ср . «арифметика») латинское слово было изменено на алгоритмус, а соответствующий английский термин «алгоритм» впервые засвидетельствован в 17 веке; современный смысл был введен в 19 веке. ^[20]

В английском языке он впервые был использован примерно в 1230 году, а затем Чосером в 1391 году. Английский принял французский термин, но только в конце 19 века «алгоритм» приобрел то значение, которое он имеет в современном английском языке. ^[21]

Еще одно раннее использование этого слова относится к 1240 году в руководстве под названием « Кармен де Альгорисмо », составленном Александром де Виледье . Он начинается с:

Haec algorismus ars praesens dicitur, in qua/Talibus Indorum fruimur bis quinque figuris.

что переводится как:

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

Поэма состоит из нескольких сотен строк и обобщает искусство счета с помощью индийских игральных костей нового стиля ( Tali Indorum ) или индуистских цифр. ^[22]

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

Неформальное определение

Неофициальным определением может быть «набор правил, который точно определяет последовательность операций», ^{[25] [ нужна цитата для проверки ]} , который будет включать все компьютерные программы (включая программы, которые не выполняют числовых вычислений) и (например) любая предписанная бюрократическая процедура ^[26] или рецепт из кулинарной книги . ^[27]

В общем, программа является алгоритмом только в том случае, если она в конце концов останавливается ^{[28] —} даже несмотря на то, что бесконечные циклы иногда могут оказаться желательными.

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

Boolos, Jeffrey & 1974, 1999 предлагают неофициальное значение слова «алгоритм» в следующей цитате:

Ни один человек не может писать достаточно быстро, или достаточно долго, или достаточно мелко† († «все меньше и меньше без ограничений… вы попытаетесь писать на молекулах, на атомах, на электронах»), чтобы перечислить все члены бесконечно бесконечного установить, выписав их имена, одно за другим, в некоторых обозначениях. Но люди могут сделать что-то столь же полезное в случае некоторых счетно бесконечных множеств: они могут дать явные инструкции для определения n -го члена множества для произвольного конечного n . Такие инструкции должны быть даны совершенно явно, в форме, в которой им могла бы следовать вычислительная машина или человек, способный выполнять только самые элементарные операции с символами. ^[29]

« Исчислимо бесконечное множество» — это множество, элементы которого можно поставить во взаимно однозначное соответствие целым числам. Таким образом, Булос и Джеффри говорят, что алгоритм подразумевает инструкции для процесса, который «создает» выходные целые числа из произвольного «входного» целого числа или целых чисел, которые теоретически могут быть сколь угодно большими. Например, алгоритм может быть алгебраическим уравнением, таким как y = m + n (т. е. две произвольные «входные переменные» m и n , которые дают результат y ), но попытки различных авторов определить это понятие указывают на то, что это слово подразумевает гораздо больше, чем это, что-то порядка (для примера сложения):

Точные инструкции (на языке, понятном «компьютеру») ^[30] для быстрого, эффективного, «хорошего» ^[31] процесса, определяющего «ходы» «компьютера» (машины или человека, оснащенного необходимыми внутренними средствами). содержит информацию и возможности) ^[32] находить, декодировать и затем обрабатывать произвольные входные целые числа/символы m и n , символы + и = … и «эффективно» ^[33] производить за «разумное» время ^[34] вывод -integer y в указанном месте и в указанном формате.

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

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

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

Алгоритмы необходимы для того, как компьютеры обрабатывают данные. Многие компьютерные программы содержат алгоритмы, подробно описывающие конкретные инструкции, которые компьютер должен выполнять — в определенном порядке — для выполнения определенной задачи, такой как расчет заработной платы сотрудников или печать табелей успеваемости учащихся. Таким образом, алгоритмом можно считать любую последовательность операций, которая может быть смоделирована полной по Тьюрингу системой. Среди авторов, отстаивающих этот тезис, Минский (1967), Сэвидж (1987) и Гуревич (2000):

Минский: «Но мы также будем утверждать вместе с Тьюрингом… что любая процедура, которую можно было бы «естественно» назвать эффективной, на самом деле может быть реализована (простой) машиной. Хотя это может показаться крайним, аргументы… в ее пользу трудно опровергнуть». ^[35] Гуревич: «… Неформальный аргумент Тьюринга в пользу его тезиса оправдывает более сильный тезис: каждый алгоритм может быть смоделирован машиной Тьюринга… согласно Сэвиджу [1987], алгоритм — это вычислительный процесс, определяемый машиной Тьюринга». ^[36]

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

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

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

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

До сих пор обсуждение формализации алгоритма исходило из предпосылок императивного программирования . Это наиболее распространенная концепция, которая пытается описать задачу дискретными, «механическими» средствами. Уникальной для этой концепции формализованных алгоритмов является операция присваивания , которая устанавливает значение переменной. Оно вытекает из интуиции « памяти » как блокнота. Пример такого задания можно найти ниже.

Для некоторых альтернативных концепций того, что представляет собой алгоритм, смотрите функциональное программирование и логическое программирование .

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

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

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

Представления алгоритмов можно разделить на три общепринятых уровня описания машины Тьюринга следующим образом: ^[37]

1 Высокоуровневое описание

«… прозой, чтобы описать алгоритм, игнорируя детали реализации. На этом уровне нам не нужно упоминать, как машина управляет своей лентой или головкой».

2 Описание реализации

«…проза использовалась для определения того, как машина Тьюринга использует свою голову и как она хранит данные на своей ленте. На этом уровне мы не даем подробностей о состояниях или функции перехода».

3 Формальное описание

Наиболее подробный, «самый низкий уровень», дает «таблицу состояний» машины Тьюринга.

Пример простого алгоритма «Добавить m+n», описанного на всех трех уровнях, см . в разделе Алгоритм#Примеры .

Дизайн

Было предложено разделить эту статью на новую статью под названием Algorithm design . ( Обсудить ) ( март 2020 )

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

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

Типичные этапы разработки алгоритмов:

1. Определение проблемы
2. Разработка модели
3. Спецификация алгоритма
4. Разработка алгоритма
5. Проверка правильности алгоритма
6. Анализ алгоритма
7. Реализация алгоритма
8. Тестирование программы
9. Подготовка документации ^{[ требуется уточнение ]}

Компьютерные алгоритмы

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

«Элегантные» (компактные) программы, «хорошие» (быстрые) программы . Понятие «простота и элегантность» неформально появляется у Кнута и именно у Чайтина :

Кнут: «… нам нужны хорошие алгоритмы в каком-то нечетко определенном эстетическом смысле. Один критерий… это время, необходимое для выполнения алгоритма…. Другими критериями являются адаптируемость алгоритма к компьютерам, его простота и элегантность и т. д.» ^[39]

Чайтин: «...программа 'изящна', под которой я подразумеваю, что это наименьшая возможная программа для получения того результата, который она делает» ^{[40] .}

Чайтин предваряет свое определение словами: «Я покажу, что вы не можете доказать, что программа «изящна » » — такое доказательство решило бы проблему остановки (там же).

Алгоритм против функции, вычисляемой алгоритмом : для данной функции может существовать несколько алгоритмов. Это верно даже без расширения доступного программисту набора инструкций. Роджерс замечает, что «... важно различать понятие алгоритма , т. е. процедуры, и понятие функции, вычисляемой с помощью алгоритма , т. е. отображения, полученного с помощью процедуры. Одна и та же функция может иметь несколько разных алгоритмов». ^[41]

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

Компьютеры (и компьютеры), модели вычислений : Компьютер (или человеческий «компьютер» ^[42] ) — это машина ограниченного типа, «дискретное детерминированное механическое устройство» ^[43] , которое слепо следует своим инструкциям. ^[44] Примитивные модели Мелзака и Ламбека ^[45] свели это понятие к четырем элементам: (i) дискретные, различимые местоположения , (ii) дискретные, неразличимые счетчики ^[46] (iii) агент и (iv) список инструкций которые эффективны относительно возможностей агента. ^[47]

Мински описывает более подходящую вариацию модели «счетов» Ламбека в его «Очень простых основах вычислимости ». ^[48] Машина Мински последовательно выполняет свои пять (или шесть, в зависимости от того, как считать) инструкций, если только условный IF-THEN GOTO или безусловный GOTO не изменяет ход выполнения программы вне последовательности. Помимо HALT, машина Мински включает три операции присваивания (замены, подстановки) ^[49] : НУЛЬ (например, содержимое ячейки заменено на 0: L ← 0), ПОСЛЕДОВАТЕЛЬ (например, L ← L+1) и УМЕНЬШЕНИЕ (например, L ← л - 1). ^[50] Программисту редко приходится писать «код» с таким ограниченным набором инструкций.Но Минский показывает (как и Мелзак и Ламбек), что его машинаВ комплекте Тьюринга всего четыре основных типа инструкций: условный GOTO, безусловный GOTO, присваивание/замена/подстановка и HALT. Однако для полноты по Тьюрингу также требуется несколько различных инструкций присваивания (например, DECREMENT, INCREMENT и ZERO/CLEAR/EMPTY для машины Мински); их точная спецификация зависит от дизайнера. Безусловный GOTO удобен; он может быть построен путем инициализации выделенной ячейки нулями, например, командой «Z ← 0»; после этого инструкция IF Z=0 THEN GOTO xxx является безусловной.

Моделирование алгоритма: компьютерный (компьютерный) язык : Кнут советует читателю, что «лучший способ изучить алгоритм — это попробовать его... немедленно взять ручку и бумагу и проработать пример». ^[51] А как насчет симуляции или исполнения реальной вещи? Программист должен перевести алгоритм на язык, который симулятор/компьютер/компьютер может эффективно выполнять. Стоун приводит пример этого: при вычислении корней квадратного уравнения вычислитель должен знать, как извлечь квадратный корень. Если они этого не делают, то алгоритм, чтобы быть эффективным, должен обеспечивать набор правил для извлечения квадратного корня. ^[52]

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

Но какую модель следует использовать для моделирования? Ван Эмде Боас отмечает, что «даже если мы основываем теорию сложности на абстрактных, а не на конкретных машинах, остается произвол в выборе модели. Именно в этот момент появляется понятие симуляции ». ^[53] При измерении скорости набор инструкций имеет значение. Например, подпрограмма в алгоритме Евклида для вычисления остатка выполнялась бы намного быстрее, если бы у программиста была доступна инструкция « модуля », а не просто вычитание (или, что еще хуже, просто «декремент» Минского).

Структурированное программирование, канонические структуры : согласно тезису Черча-Тьюринга , любой алгоритм может быть рассчитан с помощью модели, известной как полная по Тьюрингу , и, согласно демонстрации Мински, для полноты по Тьюрингу требуется только четыре типа инструкций: условный GOTO, безусловный GOTO, присваивание, HALT. Кемени и Курц отмечают, что, хотя «недисциплинированное» использование безусловных GOTO и условных IF-THEN GOTO может привести к « спагетти-коду », программист может писать структурированные программы, используя только эти инструкции; с другой стороны, «также возможно и не слишком сложно писать плохо структурированные программы на структурированном языке».^[54] Таусворт дополняет три канонические структуры Бема-Якопини :^[55] SEQUENCE, IF-THEN-ELSE и WHILE-DO, а также еще два: DO-WHILE и CASE. ^[56] Дополнительным преимуществом структурированной программы является то, что она поддается доказательству правильности с использованием математической индукции . ^[57]

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

Примеры

Пример алгоритма

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

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

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

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

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

 если  L.size = 0 вернуть значение null по величине ← L [0] для каждого  элемента  в  L , сделать ,  если  элемент > по величине , то  по величине ← элемент  вернуть  по величине

Алгоритм Евклида

В математике алгоритм Евклида или алгоритм Евклида является эффективным методом вычисления наибольшего общего делителя (НОД) двух целых чисел (чисел), наибольшего числа, на которое они оба делятся без остатка . Он назван в честь древнегреческого математика Евклида , впервые описавшего его в своих « Началах » (ок. 300 г. до н. э.). ^[59] Это один из старейших широко используемых алгоритмов. Его можно использовать для приведения дробей к их простейшей форме , и он является частью многих других теоретико-числовых и криптографических вычислений.

Евклид ставит задачу так: «Для двух чисел, не простых друг другу, найти их наибольшую общую меру». Он определяет «число [быть] множеством, состоящим из единиц»: счетное число, положительное целое число, не включающее ноль. «Измерить» — значит поместить более короткую измерительную длину s последовательно ( q раз) вдоль большей длины l до тех пор, пока оставшаяся часть r не станет меньше, чем более короткая длина s . ^[60] Говоря современным языком, остаток r = l − q × s , q — частное, или остаток r- "модуль", целочисленная дробная часть, оставшаяся после деления. ^[61]

Чтобы метод Евклида был успешным, начальные длины должны удовлетворять двум требованиям: (i) длины не должны быть равны нулю, И (ii) вычитание должно быть «правильным»; т. е. тест должен гарантировать, что меньшее из двух чисел вычитается из большего (или два могут быть равны, так что их вычитание дает ноль).

Первоначальное доказательство Евклида добавляет третье требование: две длины не должны быть простыми друг к другу. Евклид оговорил это, чтобы он мог построить доведение до абсурда доказательство того, что общая мера двух чисел на самом деле является наибольшей . ^[62] Хотя алгоритм Никомаха такой же, как у Евклида, когда числа являются простыми друг к другу, он дает число «1» для их общей меры. Так что, если быть точным, следующий алгоритм действительно принадлежит Никомаху.

1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 13 39 = 13×3 + 0

Компьютерный язык для алгоритма Евклида

Для выполнения алгоритма Евклида требуется всего несколько типов инструкций — некоторые логические проверки (условный переход), безусловный переход, присваивание (замена) и вычитание.

• Местоположение обозначается заглавными буквами, например, S, A и т. д .
• Различное количество (число) в локации записывается строчными буквами и (обычно) связано с названием локации. Например, ячейка L в начале может содержать число l = 3009.

Неэлегантная программа для алгоритма Евклида

Следующий алгоритм оформлен как четырехшаговая версия алгоритма Евклида и Никомаха Кнута, но вместо использования деления для нахождения остатка он использует последовательное вычитание меньшей длины s из оставшейся длины r до тех пор, пока r не станет меньше s . Высокоуровневое описание, выделенное жирным шрифтом, взято из Knuth 1973:2–4:

ВВОД :

1 [В двух местах L и S поместите числа l и s , которые обозначают две длины]: ВХОД Л, С2 [Инициализировать R: сделать оставшуюся длину r равной начальной/начальной/входной длине l ]: Р ← Л

E0: [Убедитесь, что r ≥ s .]

3 [Убедитесь, что меньшее из двух чисел находится в S, а большее в R]: ЕСЛИ R > S, ТО содержимое L — это большее число, поэтому пропустите шаги обмена 4 , 5 и 6 : ПЕРЕЙТИ к шагу 7 ЕЩЕ поменять местами содержимое R и S.4 L ← R (этот первый шаг избыточен, но полезен для дальнейшего обсуждения).5 Р ← С6 С ← Л

E1: [Найти остаток] : до тех пор, пока оставшаяся длина r в R не станет меньше, чем более короткая длина s в S, несколько раз вычтите измеренное число s в S из оставшейся длины r в R.

7 ЕСЛИ S > R ТО сделал измерения так ПЕРЕЙТИ К 10 ЕЩЕ еще раз измерить,8 Р ← Р - С9 [Остаток цикла]: ПЕРЕЙТИ К 7 .

E2: [Остаток равен нулю?] : ЛИБО (i) последняя мера была точной, остаток в R равен нулю, и программа может остановиться, ИЛИ (ii) алгоритм должен продолжаться: последняя мера оставила остаток в R меньше, чем число измерения в S.

10 ЕСЛИ R = 0 ТО сделано так ПЕРЕЙТИ к шагу 15 ЕЩЕ ПЕРЕЙДИТЕ К шагу 11 ,

E3: [Поменять местами s и r ] : орех алгоритма Евклида. Используйте остаток r , чтобы измерить то, что раньше было меньшим числом s ; L служит временным местом.

11 Л ← П12 Р ← С13 С ← Л14 [Повторите процесс измерения]: ПЕРЕЙТИ К 7

ВЫВОД :

15 [Готово. S содержит наибольший общий делитель ]: ПЕЧАТЬ С

СДЕЛАНО :

16 ОСТАНОВКА, КОНЕЦ, СТОП.

Элегантная программа для алгоритма Евклида

В следующей версии алгоритма Евклида требуется всего шесть основных инструкций, чтобы сделать то, что тринадцать требуется для «Неэлегантного»; хуже того, "Неэлегантный" требует больше типов инструкций. ^{[ уточнить ]} Блок-схему «Элегант» можно найти вверху этой статьи. В (неструктурированном) языке Basic шаги пронумерованы, а инструкция — это инструкция присваивания, обозначенная знаком ←.LET [] = []

 5  REM Алгоритм Евклида для нахождения наибольшего общего делителя  6  PRINT  "Введите два целых числа больше 0"  10  ВВОД  A , B  20  ЕСЛИ  B = 0 ,  ТОГДА  ПЕРЕЙТИ К  80  30  ЕСЛИ  A  >  B ,  ТОГДА  ПЕРЕЙТИ К  60  40  ПУСТЬ  B = B - A  50  ПЕРЕЙТИ К  20  60  ПУСТЬ  A = A - B  70  ПЕРЕЙТИ  20  80  ПЕЧАТЬ  A  90  КОНЕЦ

Как работает «Elegant» : вместо внешней «петли Евклида» «Elegant» перемещается туда и обратно между двумя «совместными циклами», циклом A > B, который вычисляет A ← A − B, и циклом B ≤ A. который вычисляет B ← B − A. Это работает, потому что, когда, наконец, уменьшаемое M меньше или равно вычитаемому S (Разность = уменьшаемое − вычитаемое), уменьшаемое может стать s (новая длина измерения), а вычитаемое может стать новым r (длина, которую нужно измерить); другими словами, «смысл» вычитания меняется на противоположный.

Следующая версия может использоваться с языками программирования из семейства C :

// Алгоритм Евклида для наибольшего общего делителя int  euclidAlgorithm  ( int  A ,  int  B ){  A = abs ( A );  B = абс ( B );  в то время как  ( B != 0 ) {  в то время как  ( A > B )  A знак равно A - B ;  В = В - А ;  }  вернуть  А ; }

Тестирование алгоритмов Евклида

Делает ли алгоритм то, что хочет его автор? Несколько тестов обычно дают некоторую уверенность в основных функциях. Но тестов недостаточно. Для тестов один источник ^[63] использует 3009 и 884. Кнут предложил 40902, 24140. Другой интересный случай — два относительно простых числа 14157 и 5950.

Но «исключительные случаи» ^[64] должны быть выявлены и проверены. Будет ли «Неэлегантно» работать правильно, когда R > S, S > R, R = S? То же самое для «Элегантного»: B > A, A > B, A = B? (Да для всех). Что происходит, когда одно число равно нулю, оба числа равны нулю? («Неэлегантный» вычисляет навсегда во всех случаях; «Элегантный» вычисляет навсегда, когда A = 0.) Что произойдет, если будут введены отрицательные числа? Дробные числа? Если входные числа, т. е. область определения функции , вычисляемой алгоритмом/программой, должны включать только положительные целые числа, включая ноль,тогда сбои в нуле указывают на то, что алгоритм (и программа, которая реализует его) является частичной функцией , а не общей функцией .. Заметной неудачей из-за исключений является отказ ракеты Ariane 5 Flight 501 (4 июня 1996 г.).

Доказательство правильности программы с использованием математической индукции : Кнут демонстрирует применение математической индукции к «расширенной» версии алгоритма Евклида и предлагает «общий метод, применимый для доказательства правильности любого алгоритма». ^[65] Tausworthe предлагает, чтобы мерой сложности программы была длина доказательства ее корректности. ^[66]

Измерение и улучшение алгоритмов Евклида

Элегантность (компактность) и качество (скорость) : всего с шестью основными инструкциями «Элегантный» является явным победителем по сравнению с «Неэлегантным» с тринадцатью инструкциями. Однако «Неэлегантный» быстрее (он достигает HALT за меньшее количество шагов). Анализ алгоритма ^[67] показывает, почему это так: «Элегантный» выполняет две условные проверки в каждом цикле вычитания, тогда как «Неэлегантный» — только один. Поскольку алгоритм (обычно) требует много циклов, в среднем много времени тратится впустую на выполнение "B = 0?" тест, который необходим только после вычисления остатка.

Можно ли улучшить алгоритмы? : Как только программист оценивает программу как «подходящую» и «эффективную», то есть она вычисляет функцию, задуманную ее автором, возникает вопрос, можно ли ее улучшить?

Компактность «Неэлегантного» можно повысить, убрав пять ступеней. Но Чайтин доказал, что сжатие алгоритма нельзя автоматизировать с помощью обобщенного алгоритма; ^[68] скорее, это можно сделать только эвристически ; то есть путем исчерпывающего поиска (примеры можно найти на Busy beaver ), проб и ошибок, сообразительности, проницательности, применения индуктивных рассуждений и т. д . Обратите внимание, что шаги 4, 5 и 6 повторяются в шагах 11, 12 и 13. Сравнение с «Элегантный» намекает на то, что эти шаги вместе с шагами 2 и 3 можно исключить. Это уменьшает количество основных инструкций с тринадцати до восьми, что делает его «более элегантным», чем «Elegant», с девятью шагами.

Скорость «Элеганта» можно улучшить, переместив «B=0?» тест вне двух петель вычитания. Это изменение требует добавления трех инструкций (B = 0?, A = 0?, GOTO). Теперь "Elegant" быстрее вычисляет номера примеров; всегда ли это имеет место для любых данных A, B и R, S, потребовал бы подробного анализа.

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

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

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

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

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

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

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

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

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

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

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

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

int gcd ( int A , int B ) {      если ( В == 0 )    вернуть А ;  иначе , если ( А > В )     вернуть НОД ( A - B , B );  еще вернуть gcd ( A , B - A ); }

Рекурсия

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

Логический

Алгоритм можно рассматривать как управляемый логический вывод . Это понятие можно выразить так: Алгоритм = логика + управление . ^[72] Логический компонент выражает аксиомы, которые могут использоваться в вычислениях, а управляющий компонент определяет способ применения вывода к аксиомам. Это основа парадигмы логического программирования . В языках программирования с чистой логикой компонент управления фиксирован, а алгоритмы задаются только логическим компонентом. Привлекательность этого подхода заключается в элегантной семантике : изменение аксиом приводит к четко определенным изменениям в алгоритме.

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

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

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

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

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

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

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

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

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

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

Полный перебор или полный перебор

Это наивный метод пробовать все возможные решения, чтобы найти лучшее. ^[74]

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

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

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

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

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

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

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

Снижение сложности

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

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

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

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

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

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

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

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

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

Жадный метод

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

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

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

По области обучения

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

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

По сложности

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

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

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

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

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

• Алгоритм, работающий с данными, представляющими непрерывные величины, даже если эти данные представлены дискретными приближениями, — такие алгоритмы изучаются в численном анализе ; или
• Алгоритм в виде дифференциального уравнения , непрерывно работающий с данными, работающий на аналоговом компьютере . ^[77]

Юридические проблемы

Алгоритмы сами по себе обычно не подлежат патентованию. В Соединенных Штатах заявление, состоящее исключительно из простых манипуляций с абстрактными понятиями, числами или сигналами, не является «процессом» (USPTO 2006), и, следовательно, алгоритмы не подлежат патентованию (как в деле Gottschalk v. Benson ). Однако практическое применение алгоритмов иногда патентоспособно. Например, в деле Даймонд против Диера применение простого алгоритма обратной связи для облегчения отверждения синтетического каучука было признано патентоспособным. Патентование программного обеспечения вызывает большие споры, и есть сильно критикуемые патенты, связанные с алгоритмами, особенно алгоритмами сжатия данных , такими как Unisys.« Патент LZW .

Кроме того, некоторые криптографические алгоритмы имеют ограничения на экспорт (см. экспорт криптографии ).

История: Развитие понятия «алгоритм».

Древний Ближний Восток

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

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

Дискретные и различимые символы

Метки: Чтобы вести учет своих стад, мешков с зерном и денег, древние использовали подсчет: собирая камни или отметки, нацарапанные на палках, или делая дискретные символы на глине. Благодаря использованию знаков и символов вавилонянами и египтянами в конечном итоге появились римские цифры и счеты (Дилсон, стр. 16–41). Метки подсчета занимают видное место в арифметике унарной системы счисления, используемой в вычислениях на машине Тьюринга и машине Пост-Тьюринга .

Манипуляции с символами как «заполнителями» для чисел: алгебра

Мухаммад ибн Муса аль-Хорезми , персидский математик , написал Аль-Джабр в 9 веке. Термины « алгоритм » и «алгоритм» происходят от имени аль-Хорезми, а термин « алгебра » происходит от книги Аль-джабр . В Европе слово «алгоритм» первоначально использовалось для обозначения набора правил и методов, используемых Аль-Хорезми для решения алгебраических уравнений, а затем было обобщено для обозначения любого набора правил или методов. ^[81] Это в конечном итоге привело к понятию Лейбница о логическом исчислении (ок. 1680 г.):

На добрых полтора века раньше своего времени Лейбниц предложил алгебру логики, алгебру, которая определяла бы правила манипулирования логическими понятиями так же, как обычная алгебра определяет правила манипулирования числами. ^[82]

Криптографические алгоритмы

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

Механические устройства с дискретными состояниями

Часы : Болтер считает изобретение весовых часов «ключевым изобретением [Европы в Средние века]», в частности, спусковой механизм грани ^[83] , который дает нам тиканье механических часов. «Точная автоматическая машина» ^[84] немедленно привела к «механическим автоматам », начиная с 13 века, и, наконец, к «вычислительным машинам» — разностной машине и аналитическим машинам Чарльза Бэббиджа и графини Ады Лавлейс , середина 19 века. ^[85]Лавлейсу приписывают первое создание алгоритма, предназначенного для обработки на компьютере - аналитическая машина Бэббиджа, первое устройство, которое считается настоящим полным по Тьюрингу компьютером, а не просто калькулятором , - и в результате его иногда называют «первым программистом в истории». хотя полная реализация второго устройства Бэббидж будет реализована только спустя десятилетия после ее жизни.

Логические машины 1870 г. - «логические счеты» и «логическая машина» Стэнли Джевонса : техническая проблема заключалась в сокращении булевых уравнений, когда они представлены в форме, аналогичной тому, что сейчас известно как карты Карно . Джевонс (1880) сначала описывает простые «счеты» из «деревянных планок, снабженных булавками, устроенные так, что любая часть или класс [логических] комбинаций может быть выбрана механически… систему в полностью механическую форму и, таким образом, воплотили весь непрямой процесс вывода в том, что можно назвать логической машиной .«Его машина была оснащена «некоторыми подвижными деревянными стержнями» и «у основания была 21 клавиша, как у пианино [и т. Д.] ...». С помощью этой машины он мог анализировать « силлогизм или любой другой простой логический аргумент». ^[86]

Эту машину он продемонстрировал в 1870 году перед членами Королевского общества. ^[87] Однако другой логик Джон Венн в своей « Символической логике » 1881 года предвзято отнесся к этому усилию: «Я не слишком высоко оцениваю интерес или важность того, что иногда называют логическими машинами… мне кажется, что любые устройства, известные в настоящее время или которые могут быть обнаружены, действительно заслуживают названия логических машин»; подробнее см. в разделе Характеристики алгоритмов . Но чтобы не отставать, он также представил «схему, несколько аналогичную, как я понимаю, счетам профессора Джевона».... [И] [а] усиление, соответствующее логической машине профессора Джевонса, может быть описано следующее устройство. Я предпочитаю называть ее просто машиной логических диаграмм... но я полагаю, что она вполне может делать все, что можно разумно ожидать от любой логической машины» ^{[88] .}

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

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

Дэвис (2000) отмечает особую важность электромеханического реле (с его двумя «бинарными состояниями» — открытым и закрытым ):

Только с развитием, начиная с 1930-х годов, электромеханических калькуляторов, использующих электрические реле, были построены машины, обладающие возможностями, которые предвидел Бэббидж» ^{[91] .}

Математика в 19 веке до середины 20 века

Символы и правила . В быстрой последовательности математика Джорджа Буля (1847, 1854), Готлоба Фреге (1879) и Джузеппе Пеано (1888–1889) сводила арифметику к последовательности символов, управляемых правилами. Принципы арифметики Пеано , изложенные новым методом (1888 г.), были «первой попыткой аксиоматизации математики на символическом языке ». ^[92]

Но Хейеноорт отдает Фреге (1879) такую ​​похвалу: «Возможно, это самая важная работа Фреге, когда-либо написанная по логике... в которой мы видим «язык формул», то есть lingua characterica , язык, написанный с помощью специальных символов . , «для чистой мысли», то есть свободной от риторических украшений ... построенных из определенных символов, которыми манипулируют в соответствии ^с определенными правилами » . их Principia Mathematica (1910–1913).

Парадоксы : В то же время в литературе появился ряд тревожных парадоксов, в частности, парадокс Бурали-Форти (1897 г.), парадокс Рассела (1902–03 гг.) и парадокс Ричарда . ^[94] Результирующие соображения привели к статье Курта Гёделя (1931) — он специально цитирует парадокс лжеца — которая полностью сводит правила рекурсии к числам.

Эффективная вычислимость : в попытке решить Entscheidungsproblem , точно сформулированную Гильбертом в 1928 году, математики сначала приступили к определению того, что подразумевается под «эффективным методом», или «эффективным вычислением», или «эффективной вычислимостью» (т. ). В быстрой последовательности появилось следующее: λ-исчисление Алонзо Черча , Стивена Клини и Дж. Б. Россера [ ^95] — точно отточенное определение «общей рекурсии» из работы Гёделя, действующее по предложениям Жака Эрбранда (ср. 1934) и последующие упрощения Клини. ^[96] Церковь'доказательство ^[97]что проблема Entscheidungsproblem неразрешима, определение Эмиля Поста эффективной расчетливости как рабочего, бездумно выполняющего список инструкций, чтобы двигаться влево или вправо через последовательность комнат и, находясь там, либо помечать, либо стирать бумагу, либо наблюдать за бумагой и делать да - нет решения о следующей инструкции. ^[98] Доказательство Аланом Тьюрингом того, что проблема Entscheidungsproblem неразрешима с помощью его «[автоматической] машины» ^[99] — по сути, почти идентично «формулировке» Поста, определению «эффективного метода » Дж. Баркли Россера . "в терминах "машина". ^[100] Предложение Клини предшественника « тезиса Чёрча », который он назвал «Тезис I», ^[101]а несколько лет спустя Клини переименовал свой тезис в «Тезис Черча» ^[102] и предложил «Тезис Тьюринга». ^[103]

Эмиль Пост (1936) и Алан Тьюринг (1936–37, 1939)

Эмиль Пост (1936) описал действия «компьютера» (человека) следующим образом:

«... задействованы два понятия: пространство символов , в котором должна выполняться работа, ведущая от проблемы к ответу, и фиксированный неизменный набор направлений .

Его пространство символов будет

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

«Одна клетка должна быть выделена и названа отправной точкой... конкретная задача должна быть задана в символической форме с помощью конечного числа ячеек [т. е. ВХОД], отмеченных штрихом. , ВЫВОД] должен быть задан в символической форме такой конфигурацией отмеченных прямоугольников...

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

Работа Алана Тьюринга ^[105] предшествовала работе Стибица (1937); неизвестно, знал ли Штибиц о работе Тьюринга. Биограф Тьюринга полагал, что использование Тьюрингом модели, похожей на пишущую машинку, проистекает из юношеского интереса: «Алан мечтал изобрести пишущие машинки в детстве; у миссис Тьюринг была пишущая машинка, и он вполне мог начать с вопроса, что имелось в виду, когда он называл пишущая машинка «механическая». ^[106] Учитывая распространенность азбуки Морзе и телеграфии, бегущих строк и телетайпов, мы ^{[ кто? ]} мог бы предположить, что все они были влияниями.

Тьюринг — его модель вычислений теперь называется машиной Тьюринга — начинает, как и Пост, с анализа человеческого компьютера, который он сводит к простому набору основных движений и «состояний ума». Но он идет еще дальше и создает машину как модель вычисления чисел. ^[107]

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

«Поведение компьютера в любой момент определяется символами, которые он наблюдает, и его «состоянием ума» в этот момент. Мы можем предположить, что существует граница B для числа символов или квадратов, которые компьютер может наблюдать в один момент. Если он хочет наблюдать больше, он должен использовать последовательные наблюдения. Мы также предположим, что число состояний ума, которые необходимо принять во внимание, конечно...

«Давайте представим, что операции, выполняемые компьютером, можно разделить на «простые операции», которые настолько элементарны, что их трудно представить далее разделенными». ^[108]

Сокращение Тьюринга дает следующее:

«Поэтому простые операции должны включать:

"(a) Изменения символа на одном из наблюдаемых квадратов

"(b) Изменения одного из наблюдаемых квадратов в другой квадрат в пределах L квадратов одного из ранее наблюдаемых квадратов.

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

«(А) Возможное изменение (а) символа вместе с возможным изменением состояния ума.

«(B) Возможное изменение (b) наблюдаемых квадратов вместе с возможным изменением состояния сознания»

«Теперь мы можем построить машину, которая будет выполнять работу этого компьютера». ^[108]

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

«Говорят, что функция «эффективно вычислима», если ее значения могут быть найдены с помощью какого-либо чисто механического процесса. Хотя довольно легко понять эту идею интуитивно, тем не менее желательно иметь какое-то более определенное, математически выражаемое определение. ... [он обсуждает историю определения почти так же, как представлено выше в отношении Гёделя, Хербранда, Клини, Черча, Тьюринга и Поста] ... Мы можем понимать это утверждение буквально, понимая под чисто механическим процессом тот, который могут быть выполнены машиной. Можно дать математическое описание в некоторой нормальной форме структур этих машин. Развитие этих идей приводит к авторскому определению вычислимой функции и к отождествлению вычислимость † с эффективной вычислимостью ... .

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

Дж. Б. Россер (1939 г.) и С. К. Клини (1943 г.)

Дж. Баркли Россер определил «эффективный [математический] метод» следующим образом (курсив добавлен):

«Эффективный метод» используется здесь в довольно особом смысле метода, каждый шаг которого точно определен и который наверняка даст ответ за конечное число шагов. В этом особом значении были даны три различных точных определения. [его сноска № 5; см. обсуждение ниже]. Простейший из них (благодаря Посту и Тьюрингу) говорит, по существу, что эффективный метод решения определенных наборов проблем существует, если можно построить машину, которая затем решить любую проблему из набора без вмешательства человека, кроме как вставить вопрос и (позже) прочитать ответ. Все три определения эквивалентны, поэтому не имеет значения, какое из них используется. Более того, тот факт, что все три эквивалентны, является очень сильным аргументом в пользу правильности любого из них» (Rosser 1939: 225–226).

Сноска № 5 Россера ссылается на работу (1) Черча и Клини и их определение λ-определимости, в частности, на его использование Черчем в его «Неразрешимой проблеме элементарной теории чисел» (1936); (2) Хербранд и Гёдель и их использование рекурсии, в частности, использование Гёделем в его знаменитой статье « О формально неразрешимых предложениях Principia Mathematica и родственных систем I» (1931); и (3) Пост (1936) и Тьюринг (1936–37) в их механизированных моделях вычислений.

Стивен К. Клини определил как свой теперь известный «Тезис I», известный как тезис Черча-Тьюринга . Но он сделал это в следующем контексте (выделено жирным шрифтом в оригинале):

«12. Алгоритмические теории … При построении полной алгоритмической теории мы описываем процедуру, выполнимую для каждого набора значений независимых переменных, которая обязательно завершается и таким образом, чтобы из результата мы могли прочитать определенный ответ «да» или «нет» на вопрос «истинно ли значение предиката?» (Клин 1943: 273)

История после 1950 г.

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

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

Примечания

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

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

внешняя ссылка

Найдите алгоритм в Викисловаре, бесплатном словаре.

В Викиучебнике есть книга на тему: Алгоритмы .

В Викиверситете вы можете узнать больше и научить других алгоритмам на кафедре алгоритмов.

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

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

Репозитории алгоритмов

• Репозиторий алгоритмов Стоуни-Брук - Государственный университет Нью-Йорка в Стоуни-Брук
• Сборник алгоритмов ACM — Association for Computing Machinery
• Stanford GraphBase – Стэнфордский университет