Алгоритм - Algorithm

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

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

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

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

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

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

Этимология

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Выражающие алгоритмы

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

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

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

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

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

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

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

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

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

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

Дизайн

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

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

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

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

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

Выполнение

Логическая И-НЕ алгоритм реализован в электронном виде в 7400 чип

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

Графическое выражение алгоритма Евклида для нахождения наибольшего общего делителя 1599 и 650.

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

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

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

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

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

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

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

ВХОД:

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

E0: [Убедитесь р ≥ s.]

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

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

7 ЕСЛИ S> R ТО выполнено измерение, поэтому НАЙТИ 10  ИНАЧЕ измерьте еще раз,8   R ← R - S9   [Remainder-loop]: НАЙТИ 7.

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

10 ЕСЛИ R = 0, ТО сделал это ПЕРЕЙДИТЕ шаг 15   ЕЩЕ ПРОДОЛЖИТЬ шаг 11,

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

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

ВЫХОД:

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

СДЕЛАНО:

16 HALT, END, STOP.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

int gcd(int А, int B) {    если (B == 0)        возвращаться А;    еще если (А > B)        возвращаться gcd(А-B,B);    еще        возвращаться gcd(А,B-А);}

Рекурсия

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

Логический

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Жадный метод

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

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

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

По направлениям обучения

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

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

По сложности

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

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

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

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

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

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

Проблемы с законом

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Математика с XIX века до середины XX века.

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

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

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

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

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

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

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

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

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

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

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

Статуя Алана Тьюринга в Bletchley Park

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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

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

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

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

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

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