Алгоритм -Algorithm

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 Высокоуровневое описание
«...проза, чтобы описать алгоритм, игнорируя детали реализации. На этом уровне нам не нужно упоминать, как машина управляет своей лентой или головкой».
2 Описание реализации
«...проза использовалась для определения того, как машина Тьюринга использует свою голову и как она хранит данные на своей ленте. На этом уровне мы не даем подробностей о состояниях или функции перехода».
3 Формальное описание
Наиболее подробный, «самый низкий уровень», дает «таблицу состояний» машины Тьюринга.

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

Дизайн

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

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

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

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

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

Алгоритм логического И-НЕ , реализованный электронным способом в микросхеме 7400
Примеры блок-схем канонических структур Бема-Якопини : ПОСЛЕДОВАТЕЛЬНОСТЬ (прямоугольники, спускающиеся по странице), ПОКА-ДЕЛАТЬ и ЕСЛИ-ТО-ИНАЧЕ. Эти три структуры состоят из примитивного условного GOTO ( IF test THEN GOTO step xxx, показан ромбом), безусловного GOTO (прямоугольник), различных операторов присваивания (прямоугольник) и HALT (прямоугольник). Вложение этих структур внутрь блоков присваивания приводит к сложным диаграммам (ср. Tausworthe 1977:100, 114).

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

Algorithm LargestNumber
Input: A list of numbers L.
Output: The largest number in the list L.
if L.size = 0 return null
largestL[0]
for each item in L, do
    if item > largest, then
        largestitem
return largest
  • « ← » обозначает присваивание . Например, « самый большойэлемент » означает, что значение самого большого изменяется на значение элемента .
  • " return " завершает алгоритм и выводит следующее значение.

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

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

Пример-диаграмма алгоритма Евклида из TL Heath (1908 г.) с добавлением дополнительных деталей. Евклид не идет дальше третьего измерения и не дает числовых примеров. Никомах приводит пример 49 и 21: «Я вычитаю меньшее из большего; остается 28; потом опять вычитаю из этого то же самое 21 (ибо это возможно); остается 7; я вычитаю это из 21, 14 есть влево; из которого я снова вычитаю 7 (ибо это возможно); 7 остается, но 7 нельзя вычесть из 7». Хит комментирует: «Последняя фраза любопытна, но ее значение достаточно очевидно, как и значение фразы об окончании «одним и тем же числом»» (Heath 1908: 300).

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

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

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

Графическое выражение алгоритма Евклида для нахождения наибольшего общего делителя для чисел 1599 и 650.
 1599 = 650×2 + 299
 650 = 299×2 + 52
 299 = 52×5 + 39
 52 = 39×1 + 13
 39 = 13×3 + 0

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

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

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

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

«Неэлегантный» - это перевод версии алгоритма Кнута с остаточным циклом на основе вычитания, заменяющим его использование деления (или инструкции «модуля»). Взято из Кнут 1973: 2–4. В зависимости от двух чисел «Неэлегантный» может вычислить НОД за меньшее количество шагов, чем «Элегантный».

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

ВВОД :

1 [Into two locations L and S put the numbers l and s that represent the two lengths]:
INPUT L, S
2 [Initialize R: make the remaining length r equal to the starting/initial/input length l]:
R ← L

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

3 [Ensure the smaller of the two numbers is in S and the larger in R]:
IF R > S THEN
the contents of L is the larger number so skip over the exchange-steps 4, 5 and 6:
GOTO step 7
ELSE
swap the contents of R and S.
4 L ← R (this first step is redundant, but is useful for later discussion).
5 R ← S
6 S ← L

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

7 IF S > R THEN
done measuring so
GOTO 10
ELSE
measure again,
8 R ← R − S
9 [Remainder-loop]:
GOTO 7.

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

10 IF R = 0 THEN
done so
GOTO step 15
ELSE
CONTINUE TO step 11,

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

11 L ← R
12 R ← S
13 S ← L
14 [Repeat the measuring process]:
GOTO 7

ВЫВОД :

15 [Done. S contains the greatest common divisor]:
PRINT S

СДЕЛАНО :

16 HALT, END, STOP.

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

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

  5 REM Euclid's algorithm for greatest common divisor
  6 PRINT "Type two integers greater than 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 LET 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 (Разность = уменьшаемое − вычитаемое), уменьшаемое может стать s (новая длина измерения), а вычитаемое может стать новым r (длина, которую нужно измерить); другими словами, «смысл» вычитания меняется на противоположный.

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

// Euclid's algorithm for greatest common divisor
int euclidAlgorithm (int A, int B) {
     A = abs(A);
     B = abs(B);
     while (B != 0) {
          while (A > B) {
               A = A-B;
          }
          B = B-A;
     }
     return A;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

int gcd(int A, int B) {
    if (B == 0)
        return A;
    else if (A > B)
        return gcd(A-B,B);
    else
        return gcd(A,B-A);
}
Рекурсивная реализация C алгоритма Евклида из приведенной выше блок -схемы
Рекурсия
Рекурсивный алгоритм — это алгоритм, который многократно вызывает (ссылается) сам на себя до тех пор, пока не совпадет определенное условие (также известное как условие завершения), что является методом, общим для функционального программирования . Итерационные алгоритмы используют повторяющиеся конструкции, такие как циклы, а иногда и дополнительные структуры данных, такие как стеки , для решения поставленных задач. Некоторые задачи естественным образом подходят для той или иной реализации. Например, башни Ханоя хорошо понимаются с помощью рекурсивной реализации. Каждая рекурсивная версия имеет эквивалентную (но, возможно, более или менее сложную) итеративную версию, и наоборот.
Логический
Алгоритм можно рассматривать как управляемый логический вывод . Это понятие можно выразить так: Алгоритм = логика + управление . Логический компонент выражает аксиомы, которые могут использоваться в вычислениях, а управляющий компонент определяет способ применения вывода к аксиомам. Это основа парадигмы логического программирования . В языках программирования с чистой логикой компонент управления фиксирован, а алгоритмы задаются только логическим компонентом. Привлекательность этого подхода заключается в элегантной семантике : изменение аксиом приводит к четко определенным изменениям в алгоритме.
Последовательный, параллельный или распределенный
Алгоритмы обычно обсуждаются с предположением, что компьютеры выполняют одну инструкцию алгоритма за раз. Эти компьютеры иногда называют последовательными компьютерами. Алгоритм , разработанный для такой среды, называется последовательным алгоритмом, в отличие от параллельных алгоритмов или распределенных алгоритмов . Параллельные алгоритмы используют преимущества компьютерных архитектур, в которых несколько процессоров могут работать над задачей одновременно, тогда как распределенные алгоритмы используют несколько машин, подключенных к компьютерной сети . Параллельные или распределенные алгоритмы делят проблему на более симметричные или асимметричные подзадачи и собирают результаты вместе. Потребление ресурсов в таких алгоритмах — это не только процессорные циклы на каждом процессоре, но и накладные расходы на обмен данными между процессорами. Некоторые алгоритмы сортировки могут быть эффективно распараллелены, но их коммуникационные накладные расходы являются дорогостоящими. Итерационные алгоритмы обычно распараллеливаемы. Некоторые задачи не имеют параллельных алгоритмов и называются последовательными задачами.
Детерминированный или недетерминированный
Детерминистические алгоритмы решают задачу с точным решением на каждом шаге алгоритма, тогда как недетерминированные алгоритмы решают задачи путем угадывания, хотя типичные догадки становятся более точными за счет использования эвристики .
Точное или приблизительное
В то время как многие алгоритмы достигают точного решения, алгоритмы аппроксимации ищут приближение, которое ближе к истинному решению. Аппроксимация может быть достигнута либо с использованием детерминированной, либо случайной стратегии. Такие алгоритмы имеют практическое значение для решения многих сложных задач. Одним из примеров приближенного алгоритма является задача о рюкзаке , где имеется множество заданных предметов. Его цель - упаковать рюкзак, чтобы получить максимальную общую стоимость. Каждый предмет имеет некоторый вес и некоторую ценность. Общий вес, который можно нести, не превышает некоторого фиксированного числа X. Таким образом, решение должно учитывать вес предметов, а также их стоимость.
Квантовый алгоритм
Они работают на реалистичной модели квантовых вычислений . Этот термин обычно используется для тех алгоритмов, которые кажутся квантовыми по своей сути или используют некоторые существенные особенности квантовых вычислений , такие как квантовая суперпозиция или квантовая запутанность .

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

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

Полный перебор или полный перебор
Это наивный метод пробовать все возможные решения, чтобы найти лучшее.
Разделяй и властвуй
Алгоритм « разделяй и властвуй » многократно сводит экземпляр проблемы к одному или нескольким более мелким экземплярам той же проблемы (обычно рекурсивно ), пока экземпляры не станут достаточно малы, чтобы их можно было легко решить. Одним из таких примеров «разделяй и властвуй» является сортировка слиянием . Сортировка может быть выполнена для каждого сегмента данных после разделения данных на сегменты, а сортировка всех данных может быть получена на этапе завоевания путем слияния сегментов. Более простой вариант «разделяй и властвуй» называется алгоритмом « уменьши и властвуй », который решает идентичную подзадачу и использует решение этой подзадачи для решения большей проблемы. Разделяй и властвуй разделяет проблему на несколько подзадач, поэтому этап завоевания более сложен, чем алгоритмы уменьшения и завоевания. Примером алгоритма уменьшения и завоевания является алгоритм бинарного поиска .
Поиск и перечисление
Многие задачи (например, игра в шахматы ) могут быть смоделированы как задачи на графах . Алгоритм исследования графа задает правила перемещения по графу и полезен для таких задач. В эту категорию также входят алгоритмы поиска , перечисление ветвей и границ и поиск с возвратом .
Рандомизированный алгоритм
Такие алгоритмы делают выбор случайно (или псевдослучайно). Они могут быть очень полезны при поиске приближенных решений для задач, где поиск точных решений может оказаться нецелесообразным (см. эвристический метод ниже). Для некоторых из этих задач известно, что самые быстрые приближения должны включать некоторую случайность . Могут ли рандомизированные алгоритмы с полиномиальной временной сложностью быть самыми быстрыми алгоритмами для некоторых задач — открытый вопрос, известный как проблема P и NP . Существует два больших класса таких алгоритмов:
  1. Алгоритмы Монте-Карло возвращают правильный ответ с высокой вероятностью. Например , RP является подклассом тех, которые выполняются за полиномиальное время .
  2. Алгоритмы Лас-Вегаса всегда возвращают правильный ответ, но время их работы ограничено только вероятностно, например, ZPP .
Снижение сложности
Этот метод включает в себя решение сложной проблемы путем преобразования ее в более известную проблему, для которой у нас есть (надеюсь) асимптотически оптимальные алгоритмы. Цель состоит в том, чтобы найти редукционный алгоритм, сложность которого не зависит от итогового редуцированного алгоритма. Например, один из алгоритмов выбора для нахождения медианы в несортированном списке включает в себя сначала сортировку списка (дорогая часть), а затем извлечение среднего элемента из отсортированного списка (дешевая часть). Эта техника также известна как трансформация и завоевание .
Обратное отслеживание
При таком подходе несколько решений создаются постепенно и от них отказываются, когда выясняется, что они не могут привести к действительному полному решению.

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

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

Линейное программирование
При поиске оптимальных решений линейной функции, связанной линейными ограничениями равенства и неравенства, ограничения задачи могут использоваться непосредственно для получения оптимальных решений. Существуют алгоритмы, способные решить любую задачу из этой категории, например популярный симплексный алгоритм . Проблемы, которые можно решить с помощью линейного программирования, включают задачу о максимальном потоке для ориентированных графов. Если задача дополнительно требует, чтобы одно или несколько неизвестных были целыми числами , то она классифицируется как целочисленное программирование . Алгоритм линейного программирования может решить такую ​​задачу, если можно доказать, что все ограничения для целочисленных значений являются поверхностными, т. е. решения в любом случае удовлетворяют этим ограничениям. В общем случае используется специализированный алгоритм или алгоритм, находящий приближенные решения, в зависимости от сложности задачи.
Динамическое программирование
Когда проблема имеет оптимальные подструктуры — это означает, что оптимальное решение проблемы может быть построено из оптимальных решений подзадач — и перекрывающиеся подзадачи , то есть одни и те же подзадачи используются для решения многих разных экземпляров проблемы, более быстрый подход, называемый динамическим программированием , позволяет избежать повторного вычисления решений, которые уже вычислены. Например, в алгоритме Флойда-Уоршалла кратчайший путь к цели из вершины во взвешенном графе можно найти, используя кратчайший путь к цели из всех соседних вершин. Динамическое программирование и запоминание идут рука об руку. Основное различие между динамическим программированием и разделяй и властвуй состоит в том, что в разделяй и властвуй подзадачи более или менее независимы, тогда как в динамическом программировании подзадачи перекрываются. Разница между динамическим программированием и простой рекурсией заключается в кэшировании или запоминании рекурсивных вызовов. Когда подзадачи независимы и нет повторения, запоминание не помогает; следовательно, динамическое программирование не является решением всех сложных проблем. Используя запоминание или поддерживая таблицу уже решенных подзадач, динамическое программирование снижает экспоненциальный характер многих задач до полиномиальной сложности.
Жадный метод
Жадный алгоритм подобен алгоритму динамического программирования тем, что он работает, исследуя подструктуры, в данном случае не проблемы, а заданного решения. Такие алгоритмы начинают с некоторого решения, которое может быть задано или каким-то образом построено, и улучшают его, внося небольшие модификации. Для одних задач они могут найти оптимальное решение, а для других останавливаются на локальных оптимумах , то есть на решениях, которые не могут быть улучшены алгоритмом, но не являются оптимальными. Наиболее популярное использование жадных алгоритмов - это поиск минимального остовного дерева, где с помощью этого метода возможно найти оптимальное решение. Huffman Tree , Kruskal , Prim , Sollin — жадные алгоритмы, которые могут решить эту задачу оптимизации.
Эвристический метод
В задачах оптимизации эвристические алгоритмы могут использоваться для поиска решения, близкого к оптимальному, в тех случаях, когда поиск оптимального решения нецелесообразен. Эти алгоритмы работают, приближаясь к оптимальному решению по мере их продвижения. В принципе, если запускать бесконечное количество времени, они найдут оптимальное решение. Их заслуга в том, что они могут найти решение, очень близкое к оптимальному, за относительно короткое время. К таким алгоритмам относятся локальный поиск , запретный поиск , имитация отжига и генетические алгоритмы . Некоторые из них, такие как имитация отжига, являются недетерминированными алгоритмами, тогда как другие, такие как запретный поиск, являются детерминированными. Когда известна граница ошибки неоптимального решения, алгоритм далее классифицируется как алгоритм аппроксимации .

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

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

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

По сложности

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

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

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

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

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

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

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

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

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

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

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

Алгоритмы арифметики также встречаются в древнеегипетской математике , восходящей к математическому папирусу Райнда около 1550 г. до н.э. Позднее алгоритмы использовались в древней эллинистической математике . Двумя примерами являются Решето Эратосфена , которое было описано во « Введении в арифметику » Никомаха , и алгоритм Евклида , который впервые был описан в «Элементах» Евклида ( ок.  300 г. до н.э. ).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«двусторонняя бесконечная последовательность пространств или ящиков… Решатель задач или рабочий должен двигаться и работать в этом символьном пространстве, имея возможность находиться и работать только в одном ящике за раз… ящик состоит в том, чтобы допустить только два возможных состояния, то есть быть пустым или немаркированным и иметь на нем одну метку, скажем, вертикальную черту.
«Одна клетка должна быть выделена и названа отправной точкой... конкретная задача должна быть задана в символической форме с помощью конечного числа ячеек [т. е. ВХОД], отмеченных штрихом. , ВЫВОД] должен быть задан в символической форме такой конфигурацией отмеченных прямоугольников...
«Набор направлений, применимых к общей проблеме, устанавливает детерминированный процесс применительно к каждой конкретной проблеме. Этот процесс завершается только тогда, когда речь идет о направлении типа (С) [т.е. СТОП]». Узнайте больше о машине Пост-Тьюринга
Статуя Алана Тьюринга в Блетчли-парке

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

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

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

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

«Поэтому простые операции должны включать:
"(a) Изменения символа на одном из наблюдаемых квадратов
"(b) Изменения одного из наблюдаемых квадратов в другой квадрат в пределах L квадратов одного из ранее наблюдаемых квадратов.

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

«(А) Возможное изменение (а) символа вместе с возможным изменением состояния ума.
«(B) Возможное изменение (b) наблюдаемых квадратов вместе с возможным изменением состояния сознания»
«Теперь мы можем построить машину, которая будет выполнять работу этого компьютера».

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

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

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

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

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

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

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

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

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

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

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

Заметки

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

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

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

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