Алгоритм

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

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

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

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

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

Само слово « алгоритм » происходит от имени математика 9-го века Мухаммада ибн Муса аль-Хваризми , чья нисба (идентифицирующая его как из Хорезма ) была латинизирована как Алгоритми . ^[14] Частичная формализация того, что станет современной концепцией алгоритма, началась с попыток решить Entscheidungsproblem (проблему решения), поставленную Дэвидом Гильбертом в 1928 году. Более поздние формализации были сформулированы как попытки определить « эффективную вычислимость » ^[15] или « эффективный метод ». ^[16] Эти формализации включали Гёделевский -Herbrand - Клини рекурсивные функции от 1930, 1934 и 1935, Алонзо Черч «s лямбда - исчисления 1936 года, Эмиль Post » s Рецептура 1 из 1936, и Алан Тьюринг «s машины Тьюринга из 1936-37 и 1939.

Этимология [ править ]

Слово «алгоритм» имеет свои корни в латинизации нисбы, указывающей на его географическое происхождение, от имени персидского математика Мухаммада ибн Мусы аль-Хорезми до алгоритма . ^{[17] [18]} Аль-Хваризми ( арабизированный персидский الخوارزمی c. 780–850) был математиком, астрономом , географом и ученым из Дома Мудрости в Багдаде , ^[11] имя которого означает «уроженец Хорезма », регион, который был частью Великого Ирана, а сейчас находится в Узбекистане . ^{[19] [20]}

Около 825 года аль-Хорезми написал трактат на арабском языке об индуистско-арабской системе счисления , который был переведен на латынь в XII веке. Рукопись начинается с фразы « Диксит Алгоризми» («Так говорил Аль-Хорезми»), где «Алгоризми» было латинизированным переводчиком имени Аль-Хорезми. ^[21] Аль-Хорезми был самым читаемым математиком в Европе в период позднего средневековья, в первую очередь благодаря другой его книге, « Алгебре» . ^[22] В позднесредневековой латыни algorismus , английское слово « алгоритмизм », искажение его имени, просто означало "десятичная система счисления ".^[23] В 15 веке, под влиянием греческого слова ἀριθμός ( арифмос ), «число» ( ср. «Арифметика»), латинское слово было изменено на algorithmus , и соответствующий английский термин «алгоритм» впервые засвидетельствован. в 17 веке; современный смысл был введен в 19 веке. ^[24]

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

Другое раннее использование этого слова относится к 1240 году в руководстве под названием Carmen de Algorismo, составленном Александром де Вильдье . Он начинается с:

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

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

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

Стихотворение нескольких сот строк в длиной и суммирует искусство вычисления с новыми стилизованными индийскими костьми ( Тали Indorum ) или индуистскими цифрами. ^[26]

Неофициальное определение [ править ]

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

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

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

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

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

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

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

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

Формализация [ править ]

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

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

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

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

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

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

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

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

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

Выражение алгоритмов [ править ]

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

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

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

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

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

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

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

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

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

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

Дизайн [ править ]

Было предложено разделить эту статью на новую статью под названием « Разработка алгоритмов» . ( Обсудить ) ( март 2020 )

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

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

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

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

Реализация [ править ]

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

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

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

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

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

Чайтин: «… программа« элегантна », под этим я подразумеваю, что это минимально возможная программа для получения результата, который она делает» ^[42]

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

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

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

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

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

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

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

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

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

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

Примеры [ править ]

Пример алгоритма [ править ]

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

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

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

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

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

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

Алгоритм Евклида [ править ]

Euclid «s алгоритм для вычисления наибольший общий делитель (НОД) двух чисел появляется как предложение II в книге VII („Элементарная теория чисел“) его элементов . ^[61] Евклид ставит задачу следующим образом: «Если даны два числа, не простые по отношению друг к другу, найти их наибольшую общую меру». Он определяет «число [быть] множеством, состоящим из единиц»: счетное число, положительное целое число, не включая ноль. «Измерение» означает размещение более короткой измерительной длины s последовательно ( q раз) вдоль большей длины l до тех пор, пока оставшаяся часть r не станет меньше меньшей длины s . ^[62] Говоря современным языком,остатокr = l - q × s , где q - частное, или остаток r - это «модуль», целочисленная дробная часть, оставшаяся после деления. ^[63]

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

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

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

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

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

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

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

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

ВХОД :

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

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

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

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

7 ЕСЛИ S> R ТО сделал измерения так GOTO 10 ЕЩЕ измерить еще раз,8 R ← R - S9 [Остаточный цикл]: GOTO 7 .

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

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

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

11 L ← R12 R ← S13 S ← L14 [Повторите процесс измерения]: GOTO 7

ВЫХОД :

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

СДЕЛАНО :

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

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

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

 5  REM алгоритм Евклида для наибольшего общего делителя  6  PRINT  «Введите два целых числа больше 0»  10  INPUT  A , B  20  IF  B = 0  THEN  GOTO  80  30  IF  A  >  B  THEN  GOTO  60  40  LET  B = B - A  50  GOTO  20  60  Пусть  A = A - B  70  GOTO  20  80  PRINT  A  90  END

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритмический анализ [ править ]

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

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

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

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

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

Эффективность исполнения [ править ]

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

Классификация [ править ]

Есть разные способы классификации алгоритмов, каждый со своими достоинствами.

По реализации [ править ]

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

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

Рекурсия

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

Логический

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

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

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

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

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

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

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

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

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

По парадигме дизайна [ править ]

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

Грубая сила или исчерпывающий поиск

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

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

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

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

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

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

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

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

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

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

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

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

Проблемы оптимизации [ править ]

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

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

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

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

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

Жадный метод

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

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

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

По специальности [ править ]

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

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

По сложности [ править ]

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

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

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

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

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

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

Правовые вопросы [ править ]

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

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

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

Древний Ближний Восток [ править ]

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

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

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

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

Использование символов в качестве "заполнителей" для чисел: алгебра [ править ]

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

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

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

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

Механические приспособления с дискретными состояниями [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Его пространство символов было бы

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

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

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

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

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

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

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

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

Редукция Тьюринга дает следующее:

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

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

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

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

"(A) Возможное изменение (a) символа вместе с возможным изменением настроения.

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

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

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

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

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

Дж. Б. Россер (1939) и С. К. Клини (1943) [ править ]

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

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

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

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

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

История после 1950 г. [ править ]

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

См. Также [ править ]

Заметки [ править ]

Библиография [ править ]

Дальнейшее чтение [ править ]

Внешние ссылки [ править ]

Поищите алгоритм в Викисловаре, бесплатном словаре.

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

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

Викискладе есть медиафайлы по теме алгоритмов .

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

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

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