В математике и информатике алгоритм ( / ˈ æ l ɡ ə r ɪ ð əm / _ ⓘ ) — это конечная последовательностьстрогихинструкций, обычно используемая для решения класса конкретныхзадачили выполнениявычислений.[1]Алгоритмы используются в качестве спецификаций для выполнениявычисленийиобработки данных. Более продвинутые алгоритмы могут использоватьусловные выражения, чтобы перенаправить выполнение кода по различным маршрутам (так называемоеавтоматическое принятие решений) и сделать правильныевыводы(так называемыеавтоматические рассуждения), в конечном итоге достигаяавтоматизации. Использование человеческих характеристик в качестве метафорического описания машин уже практиковалосьАланом Тьюрингомс такими терминами, как «память», «поиск» и «стимул».[2]
Напротив, эвристика — это подход к решению проблем, который может быть не полностью определен или не может гарантировать правильные или оптимальные результаты, особенно в проблемных областях, где нет четко определенного правильного или оптимального результата. [3] Например, рекомендательные системы социальных сетей полагаются на эвристику таким образом, что, хотя в популярных средствах массовой информации 21-го века их широко называют «алгоритмами», они не могут дать правильные результаты из-за характера проблемы.
В качестве эффективного метода алгоритм может быть выражен в пределах конечного объема пространства и времени [4] и на четко определенном формальном языке [5] для вычисления функции . [6] Начиная с начального состояния и начального ввода (возможно, пустого ), [7] инструкции описывают вычисление, которое при выполнении проходит через конечное [8] число четко определенных последовательных состояний, в конечном итоге производя «выход» [ 9] и завершается в конечном конечном состоянии. Переход от одного состояния к другому не обязательно является детерминированным ; некоторые алгоритмы, известные как рандомизированные алгоритмы , включают случайные входные данные. [10]
С древности были засвидетельствованы пошаговые процедуры решения математических задач. Сюда входит вавилонская математика (около 2500 г. до н. э.), [11] египетская математика (около 1550 г. до н. э.), [11] индийская математика (около 800 г. до н. э. и позже; например , Шулба-сутры , школа Кералы и Брахмасфутасиддханта ), [12] [13] Оракул Ифа (около 500 г. до н. э.), греческая математика (около 240 г. до н. э., например , решето Эратосфена и алгоритм Евклида ), [14] и арабская математика (9 век, например, криптографические алгоритмы для взлома кода, основанные на частотном анализе ). [15]
Около 825 года иранский ученый и эрудит Мухаммад ибн Муса аль-Хорезми написал «Китаб аль-Хисаб аль-хинди» («Книга индийских вычислений») и « Китаб аль-джам' ва'ль-тафрик аль-Хисаб аль-хинди» («Сложение и вычитание в индийской арифметике»). Оба эти текста в настоящее время утеряны в оригинальном арабском языке. (Однако другая его книга по алгебре сохранилась.) [16]
В начале XII века появились латинские переводы указанных текстов аль-Хорезми, включающие индуистско-арабскую систему счисления и арифметику : Liber Alghoarismi de practica arismetrice (приписывается Иоанну Севильскому ) и Liber Algorismi de numero Indorum (приписывается Аделарду Батскому ). . [17] Таким образом, alghoarismi или algorismi — это латинизация имени Аль-Хорезми; текст начинается с фразы Dixit Algorismi («Так говорил Аль-Хорезми»). [18]
В 1240 году Александр Вильдье пишет латинский текст под названием «Кармен де Альгорисмо» . Оно начинается с:
Haec algorismus ars praesens dicitur, in qua / Talibus Indorum fruimur bis quinque figuris.
что переводится как:
Алгоризм — это искусство, с помощью которого мы в настоящее время пользуемся теми индийскими цифрами, которых число два раза по пять.
Стихотворение состоит из нескольких сотен строк и обобщает искусство вычислений с помощью индийских игральных костей нового стиля ( Тали Индорум ) или индуистских цифр. [19]
Около 1230 года английское слово «алгоризм» засвидетельствовано, а затем Чосером в 1391 году. Английский язык принял французский термин. [20] [21]
В 15 веке под влиянием греческого слова ἀριθμός ( арифмос , «число»; ср. «арифметика») латинское слово было изменено на алгоритмус .
В 1656 году в английском словаре Glossographia сказано: [22]
Алгоризм ([ лат. algorismus ] ) Искусство использования шифров или нумерации с помощью шифров; навыки ведения бухгалтерского учета.
Augrime ([ латинский ] алгоритмус ) умение вести бухгалтерский учет или нумерацию.
В 1658 году в первом издании «Нового мира английских слов» говорится: [23]
Алгоритм (слово, составленное из арабского и испанского языков ), искусство расчета с помощью шифров.
В 1706 году в шестом издании « Нового мира английских слов» говорится: [24]
Алгоритм , искусство вычислений или счета с помощью чисел, которое содержит пять основных правил арифметики, а именно. Нумерация , сложение , вычитание , умножение и деление ; к этому можно добавить «Извлечение корней ». Его также называют Logistica Numeralis .
Алгоризм , практическая операция в нескольких частях ложной арифметики или алгебры ; иногда его принимают за практику общей арифметики с использованием десяти цифр.
В 1751 году в «Спутнике молодого алгебраиста» Дэниел Феннинг противопоставляет термины «алгоризм» и «алгоритм» следующим образом: [25]
Алгоритм означает первые принципы , а алгоритм — практическую часть, или знание того, как применить алгоритм на практике.
По крайней мере [обновлять], с 1811 года термин « алгоритм » на английском языке означает «пошаговая процедура». [26] [27]
В 1842 году в «Словаре науки, литературы и искусства» говорится:
АЛГОРИТМ означает искусство вычислений применительно к какому-то конкретному предмету или каким-то особым способом; как алгоритм чисел; алгоритм дифференциального исчисления. [28]
В 1928 году началась частичная формализация современной концепции алгоритмов с попыток решить Entscheidungsproblem ( проблему принятия решения), поставленную Дэвидом Гильбертом . Более поздние формализации были оформлены как попытки определить « эффективную вычислимость » [29] или «эффективный метод». [30] Эти формализации включали рекурсивные функции Гёделя – Эрбрана – Клини 1930, 1934 и 1935 годов, лямбда -исчисление Алонзо Чёрча 1936 года, формулу 1 Эмиля Поста 1936 года и машины Тьюринга Алана Тьюринга 1936–37 годов. и 1939 год.
Одним из неофициальных определений является «набор правил, который точно определяет последовательность операций», [31] [ для проверки требуется цитата ] , который включает в себя все компьютерные программы (включая программы, которые не выполняют числовые вычисления) и (например) любые предписанная бюрократическая процедура [32] или кулинарная книга рецептов . [33]
В общем, программа является алгоритмом только в том случае, если она в конечном итоге останавливается [34] — даже несмотря на то, что иногда могут оказаться желательными бесконечные циклы .
Прототипическим примером алгоритма является алгоритм Евклида , который используется для определения максимального общего делителя двух целых чисел; пример (есть и другие) описан в блок-схеме выше и в качестве примера в следующем разделе.
Булос, Джеффри и 1974, 1999 предлагают неформальное значение слова «алгоритм» в следующей цитате:
Ни один человек не может писать достаточно быстро, или достаточно долго, или достаточно мало† («†«меньше и меньше без ограничений… вы будете пытаться писать на молекулах, на атомах, на электронах»), чтобы перечислить всех членов перечислимо бесконечное множество, записывая их имена одно за другим в некоторых обозначениях. Но люди могут сделать кое-что не менее полезное в случае некоторых перечислимо бесконечных множеств: они могут дать явные инструкции по определению n-го члена множества для произвольного конечного n . Такие инструкции должны быть даны совершенно явно, в такой форме, в которой их могла бы выполнить вычислительная машина или человек , способный выполнять лишь самые элементарные операции с символами. [35]
« Счетно бесконечное множество» — это такое множество, элементы которого можно привести во взаимно однозначное соответствие с целыми числами. Таким образом, Булос и Джеффри говорят, что алгоритм подразумевает инструкции для процесса, который «создает» выходные целые числа из произвольного « входного» целого числа или целых чисел, которые теоретически могут быть сколь угодно большими. Например, алгоритм может представлять собой алгебраическое уравнение, такое как y = m + n (т. е. две произвольные «входные переменные» m и n , которые производят выход y ), но попытки различных авторов дать определение этому понятию показывают, что это слово подразумевает гораздо больше, что-то порядка (для примера сложения):
Понятие алгоритма также используется для определения понятия разрешимости — понятия, которое является центральным для объяснения того, как формальные системы возникают, исходя из небольшого набора аксиом и правил. В логике время, необходимое для выполнения алгоритма, не может быть измерено, поскольку оно явно не связано с обычным физическим измерением. Такая неопределенность, которая характеризует продолжающуюся работу, приводит к отсутствию определения алгоритма , которое подходило бы как к конкретному (в некотором смысле), так и к абстрактному использованию этого термина.
Большинство алгоритмов предназначены для реализации в виде компьютерных программ . Однако алгоритмы реализуются и другими средствами, например, в биологической нейронной сети (например, человеческий мозг , реализующий арифметику , или насекомое, ищущее пищу), в электрической цепи или в механическом устройстве.
Алгоритмы играют важную роль в том, как компьютеры обрабатывают данные. Многие компьютерные программы содержат алгоритмы, в которых подробно описываются конкретные инструкции, которые компьютер должен выполнять — в определенном порядке — для выполнения определенной задачи, например расчета зарплаты сотрудников или печати табелей успеваемости студентов. Таким образом, алгоритмом можно считать любую последовательность операций, которую можно смоделировать с помощью полной по Тьюрингу системы. Среди авторов, отстаивающих этот тезис, — Мински (1967), Сэвидж (1987) и Гуревич (2000):
Мински: «Но вместе с Тьюрингом мы также будем утверждать... что любая процедура, которую можно было бы «естественно» назвать эффективной, на самом деле может быть реализована с помощью (простой) машины. Хотя это может показаться крайностью, аргументы... ...в ее пользу трудно опровергнуть». [41] Гуревич: «… Неофициальный аргумент Тьюринга в пользу его тезиса оправдывает более сильный тезис: каждый алгоритм может быть смоделирован машиной Тьюринга … согласно Сэвиджу [1987], алгоритм — это вычислительный процесс, определяемый машиной Тьюринга». [42]
Машины Тьюринга могут определять вычислительные процессы, которые не завершаются. Неформальные определения алгоритмов обычно требуют, чтобы алгоритм всегда завершался. Это требование делает задачу определения того, является ли формальная процедура алгоритмом, невозможной в общем случае — из-за основной теоремы теории вычислимости , известной как проблема остановки .
Обычно, когда алгоритм связан с обработкой информации, данные могут быть прочитаны из источника ввода, записаны на устройство вывода и сохранены для дальнейшей обработки. Сохраненные данные рассматриваются как часть внутреннего состояния объекта, выполняющего алгоритм. На практике состояние хранится в одной или нескольких структурах данных .
Для некоторых из этих вычислительных процессов алгоритм должен быть строго определен и указан таким образом, чтобы он применялся во всех возможных обстоятельствах, которые могут возникнуть. Это означает, что любые условные шаги должны рассматриваться систематически, в каждом конкретном случае; критерии для каждого случая должны быть ясными (и вычислимыми).
Поскольку алгоритм представляет собой точный список точных шагов, порядок вычислений всегда имеет решающее значение для функционирования алгоритма. Обычно предполагается, что инструкции перечислены в явном виде и описываются как начинающиеся «сверху» и идущие «вниз» — идея, которая более формально описывается потоком управления .
До сих пор обсуждение формализации алгоритма предполагало предпосылки императивного программирования . Это наиболее распространенная концепция, которая пытается описать задачу в дискретных, «механических» терминах. С этой концепцией формализованных алгоритмов связана операция присваивания , которая устанавливает значение переменной. Оно происходит из интуитивного представления « памяти » как блокнота. Пример такого задания можно найти ниже.
Некоторые альтернативные концепции того, что представляет собой алгоритм, см. в функциональном программировании и логическом программировании .
Алгоритмы могут быть выражены во многих видах обозначений, включая естественные языки , псевдокод , блок-схемы , драконовые диаграммы , языки программирования или управляющие таблицы (обрабатываемые интерпретаторами ). Выражения алгоритмов на естественном языке имеют тенденцию быть многословными и неоднозначными и редко используются для сложных или технических алгоритмов. Псевдокод, блок-схемы, драконовые диаграммы и контрольные таблицы — это структурированные способы выражения алгоритмов, позволяющие избежать многих двусмысленностей, характерных для утверждений, основанных на естественном языке. Языки программирования в первую очередь предназначены для выражения алгоритмов в форме, которую может выполнить компьютер, но они также часто используются как способ определения или документирования алгоритмов.
Существует большое разнообразие возможных представлений, и можно выразить данную программу машины Тьюринга как последовательность машинных таблиц ( подробнее см. Конечный автомат , таблица переходов состояний и таблица управления ), как блок-схемы и драконовые диаграммы ( см. диаграмму для получения дополнительной информации) или как форму элементарного машинного кода или ассемблерного кода, называемого «наборами четверок» ( более подробную информацию см. в разделе «Машина Тьюринга »).
Представления алгоритмов можно разделить на три принятых уровня описания машины Тьюринга, а именно: [43]
Пример простого алгоритма «Сложить m+n», описанного на всех трех уровнях, см. в разделе «Примеры».
Разработка алгоритма относится к методу или математическому процессу решения проблем и разработки алгоритмов. Разработка алгоритмов является частью многих теорий решения, таких как «разделяй и властвуй» или динамическое программирование в рамках исследования операций . Методы проектирования и реализации алгоритмов также называются шаблонами проектирования алгоритмов [44] с примерами, включая шаблон метода шаблона и шаблон декоратора.
Одним из наиболее важных аспектов разработки алгоритмов является эффективность использования ресурсов (время выполнения, использование памяти); Обозначение «большое О» используется, например, для описания роста алгоритма во время выполнения по мере увеличения размера входных данных.
Типичные этапы разработки алгоритмов:
IF test THEN GOTO step xxx, показанного ромбом), безусловного GOTO (прямоугольник), различных операторов присваивания (прямоугольник) и HALT (прямоугольник). Вложение этих структур внутри блоков присваивания приводит к образованию сложных диаграмм (ср. Tausworthe 1977: 100, 114).«Элегантные» (компактные) программы, «хорошие» (быстрые) программы : Понятие «простота и элегантность» неофициально появляется у Кнута и именно у Хайтина :
Чайтин предваряет свое определение словами: «Я покажу, что невозможно доказать, что программа «элегантна » » — такое доказательство решило бы проблему остановки (там же).
Алгоритм и функция, вычислимая алгоритмом : для данной функции может существовать несколько алгоритмов. Это справедливо даже без расширения доступного программисту набора команд. Роджерс отмечает, что «... важно различать понятие алгоритма , то есть процедуры, и понятие функции, вычислимой алгоритмом , то есть отображения, полученного с помощью процедуры. Одна и та же функция может иметь несколько разных алгоритмов». [47]
К сожалению, может существовать компромисс между качеством (скоростью) и элегантностью (компактностью) — элегантная программа может выполнить больше шагов для завершения вычислений, чем менее элегантная. Ниже приведен пример использования алгоритма Евклида.
Компьютеры (и компьютеры), модели вычислений : Компьютер (или человеческий «компьютер» [48] ) — это машина ограниченного типа, «дискретное детерминированное механическое устройство» [49] , которое слепо следует своим инструкциям. [50] Примитивные модели Мельзака и Ламбека [51] свели это понятие к четырем элементам: (i) дискретные, различимые местоположения , (ii) дискретные, неразличимые счетчики [52] (iii) агент и (iv) список инструкций которые эффективны относительно возможностей агента. [53]
Мински описывает более подходящий вариант модели «абака» Ламбека в своей книге «Очень простые основы для вычислимости ». [54] Машина Мински последовательно выполняет свои пять (или шесть, в зависимости от того, как считать) инструкций, если только условный IF-THEN GOTO или безусловный GOTO не изменят ход программы вне последовательности. Помимо HALT, машина Мински включает три операции присваивания (замены, подстановки) [55] : ZERO (например, содержимое ячейки заменяется на 0: L ← 0), SUCCESSOR (например, L ← L+1) и DECREMENT (например, L ← L − 1). [56] Редко программисту приходится писать «код» с таким ограниченным набором команд. Но Минский показывает (как и Мельзак и Ламбек), что его машина Тьюринга имеет только четыре основных типа инструкций: условный GOTO, безусловный GOTO, присвоение/замена/подстановка и HALT. Однако для полноты по Тьюрингу также требуется несколько различных инструкций присваивания (например, DECREMENT, INCREMENT и ZERO/CLEAR/EMPTY для машины Мински); их точная спецификация в некоторой степени зависит от проектировщика. Безусловный GOTO удобен; его можно создать, инициализируя выделенную ячейку нулем, например, командой «Z ← 0»; после этого инструкция IF Z=0 THEN GOTO xxx является безусловной.
Моделирование алгоритма: компьютерный (компьютерный) язык : Кнут советует читателю, что «лучший способ изучить алгоритм — это попробовать его… немедленно возьмите ручку и бумагу и проработайте пример». [57] А как насчет симуляции или исполнения реальной вещи? Программист должен перевести алгоритм на язык, который сможет эффективно выполнять симулятор/компьютер/компьютер. Стоун приводит пример: при вычислении корней квадратного уравнения компьютер должен знать, как извлечь квадратный корень. Если это не так, то для того, чтобы алгоритм был эффективным, он должен предоставлять набор правил для извлечения квадратного корня. [58]
Это означает, что программист должен знать «язык», эффективный по отношению к целевому вычислительному агенту (компьютер/компьютер).
Но какую модель следует использовать для моделирования? Ван Эмде Боас отмечает, что «даже если мы основываем теорию сложности на абстрактных, а не на конкретных машинах, произвольность выбора модели сохраняется. Именно в этот момент вступает в силу понятие моделирования ». [59] При измерении скорости набор команд имеет значение. Например, подпрограмма в алгоритме Евклида для вычисления остатка выполнялась бы намного быстрее, если бы у программиста была доступна инструкция « модуля », а не просто вычитание (или, что еще хуже: просто «уменьшение» Мински).
Структурированное программирование, канонические структуры : Согласно тезису Чёрча-Тьюринга , любой алгоритм может быть вычислен с помощью модели, известной как полная по Тьюрингу , и, согласно демонстрациям Мински, полнота по Тьюрингу требует только четырех типов инструкций — условный GOTO, безусловный GOTO, присваивание, HALT. Кемени и Курц отмечают, что, хотя «недисциплинированное» использование безусловных GOTO и условных IF-THEN GOTO может привести к « спагетти-коду », программист может писать структурированные программы, используя только эти инструкции; с другой стороны, «также возможно и не слишком сложно писать плохо структурированные программы на структурированном языке». [60] Таусворт дополняет три канонические структуры Бема-Якопини : [61] ПОСЛЕДОВАТЕЛЬНОСТЬ, ЕСЛИ-ТО-ЛИБО и ПОКА-ДЕЛАТЬ, еще двумя: ДЕЛАТЬ-ПОКА и СЛУЧАЙ. [62] Дополнительным преимуществом структурированной программы является то, что ее корректность можно доказать с помощью математической индукции . [63]
Символы канонических блок-схем [64] : графическое средство, называемое блок-схемой, предлагает способ описания и документирования алгоритма (и соответствующей ему компьютерной программы). Подобно потоку программы на машине Мински, блок-схема всегда начинается вверху страницы и продолжается вниз. Его основных символов всего четыре: направленная стрелка, показывающая ход выполнения программы, прямоугольник (SEQUENCE, GOTO), ромб (IF-THEN-ELSE) и точка (ИЛИ-связь). Канонические структуры Бема – Якопини состоят из этих примитивных форм. Подструктуры могут «вкладываться» в прямоугольники, но только в том случае, если из надстройки происходит единственный выход. Символы и их использование для построения канонических структур показаны на схеме.
Один из простейших алгоритмов — найти наибольшее число в списке чисел случайного порядка. Чтобы найти решение, необходимо просмотреть каждое число в списке. Отсюда следует простой алгоритм, который можно сформулировать в высокоуровневом описании в английской прозе следующим образом:
Описание высокого уровня:
(Квази-)формальное описание: Написанное прозой, но гораздо ближе к языку высокого уровня компьютерной программы, ниже приводится более формальное кодирование алгоритма в псевдокоде или пиджин-коде :
Алгоритм наибольшего числаВходные данные: список чисел L .Выходные данные: Самое большое число в списке L .
если L.size = 0 вернуть нулевой наибольший ← L [0] для каждого элемента в L , сделать, если элемент > самый большой , то самый большой ← элемент вернуть самый большой
В математике алгоритм Евклида или алгоритм Евклида — это эффективный метод вычисления наибольшего общего делителя (НОД) двух целых чисел (числ), наибольшего числа, которое делит их оба без остатка . Оно названо в честь древнегреческого математика Евклида , впервые описавшего его в своих «Началах» ( ок. 300 г. до н. э. ). [65] Это один из старейших широко используемых алгоритмов. Его можно использовать для приведения дробей к их простейшей форме , а также он является частью многих других теоретико-числовых и криптографических вычислений.
Евклид ставит задачу так: «Давны два числа, не простые друг другу, найти их наибольшую общую меру». Он определяет «число, [чтобы быть] множеством, состоящим из единиц»: счетное число, положительное целое число, не включая ноль. «Измерить» значит разместить более короткую измерительную длину s последовательно ( q раз) вдоль большей длины l до тех пор, пока оставшаяся часть r не станет меньше более короткой длины s . [66] Говоря современными словами, остаток r = l − q × s , q — частное, или остаток r — это «модуль», цело-дробная часть, оставшаяся после деления. [67]
Чтобы метод Евклида был успешным, начальные длины должны удовлетворять двум требованиям: (i) длины не должны быть равны нулю, И (ii) вычитание должно быть «правильным»; т. е. тест должен гарантировать, что меньшее из двух чисел вычитается из большего (или они могут быть равны, поэтому их вычитание дает ноль).
Первоначальное доказательство Евклида добавляет третье требование: две длины не должны быть простыми друг другу. Евклид оговорил это для того, чтобы построить доведение до абсурда доказательство того, что общая мера этих двух чисел на самом деле является наибольшей . [68] Хотя алгоритм Никомаха такой же, как и алгоритм Евклида, когда числа просты друг с другом, он дает число «1» для их общей меры. Итак, если быть точным, то на самом деле это алгоритм Никомаха.
1599 = 650×2 + 299 650 = 299×2 + 52 299 = 52×5 + 39 52 = 39×1 + 1339 = 13×3 + 0Для выполнения алгоритма Евклида требуется всего несколько типов инструкций — некоторые логические проверки (условный переход), безусловный переход, присваивание (замена) и вычитание.
Следующий алгоритм оформлен как четырехшаговая версия алгоритмов Евклида и Никомаха, разработанная Кнутом, но вместо использования деления для нахождения остатка он использует последовательные вычитания более короткой длины 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 СТОП, КОНЕЦ, СТОП.Следующая версия алгоритма Евклида требует всего шесть основных инструкций, чтобы выполнить то, что для «Неэлегантного» требуется тринадцать; хуже того, «Неэлегантный» требует больше типов инструкций. [ уточнить ] Блок-схему «Elegant» можно найти вверху этой статьи. В (неструктурированном) языке Basic шаги пронумерованы, а инструкция представляет собой инструкцию присваивания, обозначенную ←.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 ПЕРЕХОД К 20 80 ПЕЧАТЬ A 90 КОНЕЦ Как работает «Элегантный» : вместо внешнего «евклидового цикла» «Элегантный» вычисляет остаток от деления по модулю и сдвигает переменные A и B на каждой итерации. Следующий алгоритм можно использовать с языками программирования семейства C :
// Алгоритм Евклида для определения наибольшего общего делителя int euclidAlgorithm ( int A , int B ) { A = abs ( A ); В = абс ( В ); если ( A == 0 || B == 0 ) { return 0 ; } do { int res = A % B ; А = Б ; Б = рез ; } Пока ( B > 0 ); вернуть А ; Делает ли алгоритм то, чего хочет его автор? Несколько тестовых случаев обычно дают некоторую уверенность в основных функциях. Но тестов недостаточно. Для тестовых случаев один источник [69] использует числа 3009 и 884. Кнут предложил 40902, 24140. Другой интересный случай — два относительно простых числа 14157 и 5950.
Но «исключительные случаи» [70] необходимо выявлять и проверять. Будет ли «Неэлегантный» работать правильно, когда R > S, S > R, R = S? То же самое для «Элегантного»: B > A, A > B, A = B? (Да для всех). Что произойдет, если одно число равно нулю, а оба числа равны нулю? («Неэлегантный» вычисляет всегда во всех случаях; «Элегантный» вычисляет всегда, когда A = 0.) Что произойдет, если введены отрицательные числа? Дробные числа? Если входные числа, т. е. область определения функции, вычисленной алгоритмом/программой, должны включать только положительные целые числа, включая ноль, то сбои в нуле указывают на то, что алгоритм (и программа, которая его реализует ) является частичной функцией, а не общая функция . Заметной неудачей из-за исключений является авария ракеты Ariane 5 рейса 501 (4 июня 1996 г.).
Доказательство правильности программы с помощью математической индукции : Кнут демонстрирует применение математической индукции к «расширенной» версии алгоритма Евклида и предлагает «общий метод, применимый для доказательства достоверности любого алгоритма». [71] Таусворт предлагает, чтобы мерой сложности программы была длина доказательства ее корректности. [72]
Элегантность (компактность) против качества (скорость) . Имея всего шесть основных инструкций, «Элегантный» является явным победителем по сравнению с «Неэлегантным» с тринадцатью инструкциями. Однако «Неэлегантный» быстрее (он достигает HALT за меньшее количество шагов). Анализ алгоритма [73] показывает, почему это так: «Элегантный» выполняет две условные проверки в каждом цикле вычитания, тогда как «Неэлегантный» выполняет только одну. Поскольку алгоритм (обычно) требует множества проходов, в среднем много времени тратится на выполнение «B = 0?» тест, который необходим только после вычисления остатка.
Можно ли улучшить алгоритмы? : Как только программист считает программу «подходящей» и «эффективной», то есть вычисляет функцию, задуманную ее автором, возникает вопрос: можно ли ее улучшить?
Компактность «Неэлегантного» можно улучшить, исключив пять ступеней. Но Чайтин доказал, что сжатие алгоритма не может быть автоматизировано с помощью обобщенного алгоритма; [74] скорее, это можно сделать только эвристически ; т. е. путем исчерпывающего поиска (примеры можно найти в Busy Beaver ), проб и ошибок, сообразительности, проницательности, применения индуктивных рассуждений и т. д. Обратите внимание, что шаги 4, 5 и 6 повторяются в шагах 11, 12 и 13. Сравнение с «Элегантный» подсказывает, что эти шаги вместе с шагами 2 и 3 можно исключить. Это уменьшает количество основных инструкций с тринадцати до восьми, что делает его «более элегантным», чем «Элегантный», с девятью шагами.
Скорость «Элегантного» можно улучшить, переместив «B=0?» тест за пределами двух циклов вычитания. Это изменение требует добавления трех инструкций (B = 0?, A = 0?, GOTO). Теперь «Elegant» быстрее вычисляет числа примеров; всегда ли это так для любых данных A, B и R, S потребует детального анализа.
Часто важно знать, сколько определенного ресурса (например, времени или памяти) теоретически требуется для данного алгоритма. Разработаны методы анализа алгоритмов получения таких количественных ответов (оценок); например, алгоритм, который складывает элементы списка из n чисел, потребует времени , используя обозначение большого О. Алгоритму всегда нужно помнить только два значения: сумму всех элементов на данный момент и его текущую позицию во входном списке. Поэтому говорят, что требуется пространство , равное , если пространство, необходимое для хранения входных чисел, не учитывается или если оно учитывается.
Разные алгоритмы могут выполнять одну и ту же задачу с разным набором инструкций за меньшее или большее время, пространство или « усилия », чем другие. Например, алгоритм двоичного поиска (со стоимостью ) превосходит последовательный поиск (стоимостью ) при использовании для поиска по таблицам в отсортированных списках или массивах.
Анализ и изучение алгоритмов — это дисциплина информатики , которая часто практикуется абстрактно, без использования конкретного языка программирования или реализации. В этом смысле анализ алгоритмов похож на другие математические дисциплины, поскольку он фокусируется на основных свойствах алгоритма, а не на особенностях какой-либо конкретной реализации. Обычно для анализа используется псевдокод , поскольку это самое простое и общее представление. Однако в конечном итоге большинство алгоритмов обычно реализуются на определенных аппаратных/программных платформах, и их алгоритмическая эффективность в конечном итоге проверяется с использованием реального кода. Для решения «разовой» проблемы эффективность конкретного алгоритма может не иметь существенных последствий (если только n не чрезвычайно велико), но для алгоритмов, предназначенных для быстрого интерактивного, коммерческого или длительного научного использования, это может иметь решающее значение. Масштабирование от маленького n до большого n часто приводит к появлению неэффективных алгоритмов, которые в остальном безвредны.
Эмпирическое тестирование полезно, поскольку оно может выявить неожиданные взаимодействия, влияющие на производительность. Тесты можно использовать для сравнения возможных улучшений алгоритма до/после после оптимизации программы. Однако эмпирические тесты не могут заменить формальный анализ, и их не так просто выполнить честно. [75]
Чтобы проиллюстрировать потенциальные улучшения, возможные даже в хорошо зарекомендовавших себя алгоритмах, недавнее значительное нововведение, касающееся алгоритмов БПФ (широко используемых в области обработки изображений), может сократить время обработки до 1000 раз для таких приложений, как медицинская визуализация. [76] В общем, повышение скорости зависит от особых свойств задачи, которые очень распространены в практических приложениях. [77] Ускорение такого масштаба позволяет вычислительным устройствам, широко использующим обработку изображений (например, цифровым камерам и медицинскому оборудованию), потреблять меньше энергии.
Существуют различные способы классификации алгоритмов, каждый из которых имеет свои преимущества.
Один из способов классификации алгоритмов — по средствам реализации.
Другой способ классификации алгоритмов — по методологии или парадигме их проектирования . Существует определенное количество парадигм, каждая из которых отличается от другой. Более того, каждая из этих категорий включает в себя множество различных типов алгоритмов. Некоторые распространенные парадигмы:
Для задач оптимизации существует более конкретная классификация алгоритмов; алгоритм решения таких задач может относиться к одной или нескольким общим категориям, описанным выше, а также к одному из следующих:
Каждая область науки имеет свои проблемы и нуждается в эффективных алгоритмах. Связанные проблемы в одной области часто изучаются вместе. Некоторыми примерами классов являются алгоритмы поиска , алгоритмы сортировки , алгоритмы слияния , числовые алгоритмы , графовые алгоритмы , строковые алгоритмы , вычислительные геометрические алгоритмы , комбинаторные алгоритмы , медицинские алгоритмы , машинное обучение , криптография , алгоритмы сжатия данных и методы синтаксического анализа .
Поля имеют тенденцию перекрываться друг с другом, и усовершенствования алгоритмов в одной области могут улучшить результаты в других, иногда совершенно несвязанных областях. Например, динамическое программирование было изобретено для оптимизации потребления ресурсов в промышленности, но сейчас используется для решения широкого круга задач во многих областях.
Алгоритмы можно классифицировать по количеству времени, которое им необходимо для выполнения, по сравнению с размером входных данных:
Некоторые задачи могут иметь несколько алгоритмов разной сложности, в то время как другие задачи могут не иметь алгоритмов или не иметь известных эффективных алгоритмов. Также существуют отображения некоторых проблем на другие проблемы. Благодаря этому оказалось более целесообразным классифицировать сами задачи, а не алгоритмы, на классы эквивалентности на основе сложности наилучших возможных алгоритмов для них.
Прилагательное «непрерывный» в применении к слову «алгоритм» может означать:
В логическом программировании алгоритмы рассматриваются как имеющие как «логический компонент, который определяет знания, которые будут использоваться при решении проблем, так и компонент управления, который определяет стратегии решения проблем, посредством которых эти знания используются». [82]
Алгоритм Евклида иллюстрирует такой взгляд на алгоритм. [83] [84] Вот представление логического программирования, в котором используется :- для обозначения «if» и отношение gcd(A, B, C) для представления функции gcd(A, B) = C:
НОД ( А , А , А ). НОД ( A , B , C ) :- A > B , НОД ( A - B , B , C ). НОД ( A , B , C ) :- B > A , НОД ( A , B - A , C ).В языке логического программирования Ciao отношение НОД может быть представлено непосредственно в функциональной записи:
НОД ( А , А ) := А . НОД ( A , B ) := НОД ( A - B , B ) :- A > B . НОД ( A , B ) := НОД ( A , B - A ) :- B > A .Реализация Ciao преобразует функциональную нотацию в реляционное представление на Прологе , извлекая встроенные вычитания AB и BA как отдельные условия:
НОД(А, А, А).НОД(A, B, C):- A > B, A' есть AB, gcd(A', B, C).НОД(А, В, С):- В > А, В' есть ВА, НОД(А, В, С).Результирующая программа имеет чисто логическое (и «декларативное» ) чтение как рекурсивное (или индуктивное) определение, независимое от того, как логика используется для решения задач:
НОД чисел A и A равен A.НОД A и B равен C, если A > B и A' равен AB, а НОД A' и B равен C.НОД A и B равен C, если B > A и B' равен BA, а НОД A и B' равен C.Различные стратегии решения проблем превращают логику в разные алгоритмы. Теоретически, учитывая пару целых чисел A и B, рассуждения вперед (или «снизу вверх») могут использоваться для генерации всех экземпляров отношения НОД, завершающегося, когда генерируется желаемый НОД из A и B. Конечно, предварительные рассуждения в этом случае совершенно бесполезны. Но в других случаях, таких как определение последовательности Фибоначчи [82] и Datalog , предварительные рассуждения могут быть эффективной стратегией решения проблем. (См., например, логическую программу для вычисления чисел Фибоначчи в Algorithm = Logic + Control ).
В отличие от неэффективности прямого рассуждения в этом примере, обратное (или «сверху вниз») рассуждение с использованием разрешения SLD превращает логику в алгоритм Евклида:
Чтобы найти НОД C двух заданных чисел A и B:Если А = В, то С = А.Если A > B, то пусть A' = AB и найдите НОД A' и B, который равен C.Если B > A, то пусть B' = BA и найдите НОД A и B', который равен C.Одним из преимуществ представления алгоритма в виде логического программирования является то, что его чисто логическое чтение облегчает проверку правильности алгоритма по сравнению со стандартным нерекурсивным определением НОД. [83] Вот стандартное определение, написанное на Прологе:
НОД ( A , B , C ) :- делит ( C , A ), делит ( C , B ), forall (( делит ( D , A ), делит ( D , B )), D =< C ). делит ( C , Number ) :- между ( 1 , Number , C ), 0 - это число по модулю C .Это определение, которое является спецификацией алгоритма Евклида, также можно выполнить на Прологе: обратные рассуждения рассматривают спецификацию как алгоритм грубой силы, который перебирает все целые числа C от 1 до A, проверяя, делит ли C оба A и B. , а затем для каждого такого C снова перебирает все целые числа D между 1 и A, пока не найдет C такое, что C больше или равно всем D, которые также делят A и B. Хотя этот алгоритм безнадежно неэффективен, он показывает, что формальные спецификации часто могут быть написаны в форме логического программирования и могут выполняться на Прологе для проверки того, что они правильно представляют неформальные требования .
Сами по себе алгоритмы обычно не патентоспособны. В Соединенных Штатах заявка, состоящая исключительно из простых манипуляций с абстрактными понятиями, числами или сигналами, не представляет собой «процессы» (USPTO 2006), поэтому алгоритмы не подлежат патентованию (как в деле Готшалк против Бенсона ). Однако практическое применение алгоритмов иногда патентоспособно. Например, в деле Даймонд против Дира применение простого алгоритма обратной связи для отверждения синтетического каучука было признано патентоспособным. Патентование программного обеспечения является спорным [85] , и существуют критикуемые патенты, связанные с алгоритмами, особенно алгоритмами сжатия данных , такие как патент Unisys LZW .
Кроме того, некоторые криптографические алгоритмы имеют ограничения на экспорт (см. экспорт криптографии ).
Самые ранние свидетельства существования алгоритмов можно найти в вавилонской математике древней Месопотамии (современный Ирак). Шумерская глиняная табличка , найденная в Шуруппаке недалеко от Багдада и датированная ок. В 2500 году до нашей эры был описан самый ранний алгоритм деления . [11] Во времена династии Хаммурапи ок. 1800 – ок. 1600 г. до н.э. на вавилонских глиняных табличках описаны алгоритмы вычисления формул . [86] Алгоритмы также использовались в вавилонской астрономии . Вавилонские глиняные таблички описывают и используют алгоритмические процедуры для расчета времени и места важных астрономических событий. [87]
Алгоритмы арифметики также встречаются в древнеегипетской математике , начиная с Математического папируса Ринда ок. 1550 г. до н.э. [11] Позднее алгоритмы использовались в древней эллинистической математике . Двумя примерами являются Решето Эратосфена , которое было описано во «Введении в арифметику» Никомаха , [88] [14] : Глава 9.2 , и алгоритм Евклида , который был впервые описан в «Началах» Евклида ( ок. 300 г. до н. э .). [14] : Глава 9.1.
Метки для подсчета: Чтобы отслеживать свои стада, мешки с зерном и деньги, древние использовали подсчет: накапливали камни или отметки, нацарапанные на палках, или делали отдельные символы из глины. Благодаря использованию знаков и символов вавилонянами и египтянами в конечном итоге появились римские цифры и счеты (Дилсон, стр. 16–41). Метки счета занимают видное место в арифметике унарной системы счисления, используемой в вычислениях на машине Тьюринга и машине Пост-Тьюринга .
Мухаммад ибн Муса аль-Хорезми , персидский математик , написал « Аль-Джабр» в 9 веке. Термины « алгоризм » и «алгоритм» произошли от имени аль-Хваризми, а термин « алгебра » — из книги «Аль-Джабр» . В Европе слово «алгоритм» первоначально использовалось для обозначения набора правил и методов, используемых Аль-Хорезми для решения алгебраических уравнений, а затем было обобщено для обозначения любого набора правил или методов. [89] В конечном итоге это привело к появлению у Лейбница идеи рационального исчисления ( около 1680 г. ):
На полтора столетия опередив свое время, Лейбниц предложил алгебру логики, алгебру, которая определяла бы правила манипулирования логическими понятиями так же, как обычная алгебра определяет правила манипулирования числами. [90]
Первый криптографический алгоритм дешифрования зашифрованного кода был разработан Аль-Кинди , арабским математиком 9-го века , в «Рукописи о расшифровке криптографических сообщений» . Он дал первое описание криптоанализа с помощью частотного анализа , самого раннего алгоритма взлома кода . [15]
Часы : Болтер считает изобретение часов с весовым приводом «ключевым изобретением [Европы в средние века]», в частности, спусковой механизм [91] , который обеспечивает нам тикание и такт механических часов. «Точная автоматическая машина» [92] немедленно привела к «механическим автоматам », начиная с XIII века, и, наконец, к «вычислительным машинам» — разностной машине и аналитическим машинам Чарльза Бэббиджа и графини Ады Лавлейс , середина XIX века. [93] Лавлейсу приписывают первое создание алгоритма, предназначенного для обработки на компьютере — аналитической машины Бэббиджа, первого устройства, считавшегося настоящим Тьюринг-полным компьютером, а не просто калькулятором — и иногда его называют «первым программистом в истории», как В результате, хотя полная реализация второго устройства Бэббиджа будет реализована только спустя десятилетия после ее жизни.
Логические машины 1870 г. – «Логические счеты» и «логическая машина» Стэнли Джевонса : техническая проблема заключалась в сокращении булевых уравнений , когда они представлены в форме, аналогичной тому, что сейчас известно как карты Карно . Джевонс (1880) описывает сначала простые «счеты» из «деревянных пластинок, снабженных булавками, устроенных так, чтобы любую часть или класс [логических] комбинаций можно было выбрать механически ... Однако совсем недавно я сократил систему в полностью механическую форму и, таким образом, воплотили весь косвенный процесс вывода в том, что можно назвать логической машиной . фортепиано [и т. д.]…». С помощью этой машины он мог проанализировать « силлогизм или любой другой простой логический аргумент». [94]
Эту машину он продемонстрировал в 1870 году членам Королевского общества. [95] Другой логик, Джон Венн , однако, в своей книге «Символическая логика» 1881 года предвзято отнесся к этим усилиям: «Я не слишком высоко оцениваю интерес или важность того, что иногда называют логическими машинами… это не кажется Я считаю, что любые устройства, известные в настоящее время или которые могут быть открыты, действительно заслуживают названия логических машин»; подробнее см. в разделе «Характеристики алгоритмов» . Но чтобы не отставать, он также представил «план, несколько аналогичный, насколько я понимаю, счетам профессора Джевона … [И] [а] выигрыш, соответствующий логической машине профессора Джевонса, можно описать следующее изобретение. Я предпочитаю называть ее просто машиной логических диаграмм... но я полагаю, что она могла бы делать в полной мере все, что можно рационально ожидать от любой логической машины». [96]
Жаккардовый ткацкий станок, перфокарты Холлерита, телеграфия и телефония - электромеханическое реле : Белл и Ньюэлл (1971) указывают, что жаккардовый ткацкий станок (1801 г.), предшественник карт Холлерита (перфокарты, 1887 г.), и «технологии телефонной коммутации» были корнями дерева, что привело к созданию первых компьютеров. [97] К середине 19-го века телеграф , предшественник телефона, использовался во всем мире, его дискретное и различимое кодирование букв в виде «точек и тире» было обычным звуком. К концу 19 века использовалась бегущая лента ( около 1870-х годов ), а также карты Холлерита при переписи населения США 1890 года. Затем появился телетайп ( ок. 1910 г. ) с перфолентой, в которой код Бодо был записан на ленте.
Телефонно-коммутационные сети электромеханических реле (изобретены в 1835 г.) легли в основу работ Джорджа Стибица (1937 г.), изобретателя цифрового суммирующего устройства. Работая в Bell Laboratories, он наблюдал «обременительное» использование механических калькуляторов с шестернями. «Однажды вечером в 1937 году он пошел домой, намереваясь проверить свою идею… Когда работа была окончена, Стибиц сконструировал устройство двоичного сложения». [98 ]
Математик Мартин Дэвис отмечает особую важность электромеханического реле (с двумя его «двоичными состояниями» — разомкнутым и замкнутым ):
Символы и правила . Математика Джорджа Буля (1847, 1854), Готтлоба Фреге (1879) и Джузеппе Пеано (1888–1889) в быстрой последовательности свела арифметику к последовательности символов, управляемых правилами. «Принципы арифметики» Пеано , изложенные новым методом (1888 г.), были «первой попыткой аксиоматизации математики на символическом языке ». [100]
Но Хейеноорт отдает должное Фреге (1879): «Это, пожалуй, самая важная работа, когда-либо написанная по логике... в которой мы видим « язык формул», то есть lingua характерика , язык, написанный специальными символами. «для чистой мысли», то есть свободной от риторических украшений... построенной из конкретных символов , которыми манипулируют в соответствии с определенными правилами » . их Principia Mathematica (1910–1913).
Парадоксы : В то же время в литературе появился ряд тревожных парадоксов, в частности парадокс Бурали-Форти (1897), парадокс Рассела (1902–03) и парадокс Ричарда . [102] Полученные соображения привели к появлению статьи Курта Гёделя (1931) — он конкретно цитирует парадокс лжеца — которая полностью сводит правила рекурсии к числам.
Эффективная вычислимость . Пытаясь решить проблему Entscheidungsproblem , определенную Гильбертом в 1928 году, математики сначала приступили к определению того, что подразумевается под «эффективным методом», или «эффективным расчетом», или «эффективной вычислимостью» (т. е. расчетом, который приведет к успеху). ). В быстрой последовательности появились следующие: Алонсо Чёрч , Стивен Клини и Дж. Б. Россер , λ-исчисление [103] — тонко отточенное определение «общей рекурсии» из работы Гёделя, действующее на основе предложений Жака Эрбрана (ср. Принстонские лекции Гёделя в 1934) и последующие упрощения Клини. [104] Доказательство Чёрча [105] о том, что проблема Entscheidungsproblem неразрешима, определение Эмилем Постом эффективной вычислительной способности, когда рабочий бездумно следует списку инструкций, чтобы двигаться влево или вправо через последовательность комнат и в то же время либо отмечать, либо стирать бумагу. или просмотрите бумагу и примите решение «да» или «нет» относительно следующей инструкции. [106] Доказательство Алана Тьюринга неразрешимости проблемы Entscheidungsproblem с помощью его «автоматической машины» [107] — по сути, почти идентично «формулировке» Поста, определению «эффективного метода», данному Дж. Баркли Россером. «в смысле «машина». [108] Предложение Клини о предшественнике « Тезиса Чёрча », который он назвал «Тезисом I», [109] и несколько лет спустя Клини переименовал свою диссертацию в «Тезис Чёрча» [110] и предложил «Тезис Тьюринга». [111]
Эмиль Пост (1936) описал действия «компьютера» (человека) следующим образом:
Его символическое пространство будет
Работа Алана Тьюринга [113] предшествовала работе Стибитца (1937); неизвестно, знал ли Стибиц о работах Тьюринга. Биограф Тьюринга считал, что использование Тьюрингом модели, похожей на пишущую машинку, проистекает из юношеского интереса: «Алан мечтал изобрести пишущие машинки еще мальчиком; у миссис Тьюринг была пишущая машинка, и он вполне мог бы начать с вопроса, что означало, называя пишущая машинка «механическая » . [114] Учитывая распространенность в то время азбуки Морзе, телеграфии, телеграфных машин и телетайпов, вполне возможно, что все они оказали влияние на Тьюринга в юности.
Тьюринг — его модель вычислений теперь называется машиной Тьюринга — начинает, как и Пост, с анализа человеческого компьютера, который он сводит к простому набору основных движений и «состояний ума». Но он идет еще дальше и создает машину как модель вычисления чисел. [115]
Сокращение Тьюринга дает следующее:
«Возможно, некоторые из этих изменений обязательно вызывают изменение состояния ума. Следовательно, наиболее общую операцию следует рассматривать как одну из следующих:
Несколько лет спустя Тьюринг расширил свой анализ (тезис, определение) таким убедительным выражением:
Дж. Баркли Россер определил «эффективный [математический] метод» следующим образом (курсив добавлен):
Сноска Россера № 5 ссылается на работу (1) Чёрча и Клини и их определение λ-определимости, в частности, на использование его Чёрчем в его « Неразрешимой проблеме элементарной теории чисел» (1936); (2) Эрбранд и Гёдель и их использование рекурсии, в частности, использование Гёделем в его знаменитой статье « О формально неразрешимых утверждениях принципов математики и родственных систем I» (1931); и (3) Пост (1936) и Тьюринг (1936–37) в их моделях механизмов вычислений.
Стивен К. Клини определил свой ныне знаменитый «Тезис I», известный как тезис Чёрча-Тьюринга . Но он сделал это в следующем контексте (жирный шрифт в оригинале):
Ряд усилий был направлен на дальнейшее уточнение определения «алгоритма», и эта деятельность продолжается из-за проблем, касающихся, в частности, оснований математики (особенно тезиса Чёрча-Тьюринга ) и философии разума (особенно аргументов об искусственном интеллекте ). Дополнительные сведения см. в разделе Характеристики алгоритмов .
Однако ему нужен новый алгоритм, исчерпывающий метод, с помощью которого теоремы могут быть установлены без двусмысленности и многословия, [...]
[...] следующий уровень абстракции центральной бюрократии: глобально действующие алгоритмы.
Алгоритм — это рецепт, метод или техника выполнения чего-либо.
Эта статья включает общедоступные материалы Пола Э. Блэка. "алгоритм". Словарь алгоритмов и структур данных . НИСТ .
{{cite book}}: |journal=игнорируется ( помощь ){{cite book}}: |journal=игнорируется ( помощь ) , ISBN 0-671-49207-1 . См. Глава «Дух истины» содержит историю, ведущую к его доказательству, и обсуждение его. 
