Алгоритм - Algorithm


Из Википедии, свободной энциклопедии

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

В математике и информатике , алгоритм ( / æ л ɡ ə г ɪ ð əm / ( слушать )Об этом звуке ) является однозначной спецификации , как решить класс проблем. Алгоритмы могут выполнять вычисления , обработка данных и автоматизированных мыслительные задачи.

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

Понятие алгоритма существует в течение многих столетий. Греческие математики использовали алгоритмы в решете Эратосфена для нахождения простых чисел, и алгоритм Евклида для нахождения наибольшего общего делителя двух чисел.

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

содержание

Этимология

Слово «алгоритм» имеет свои корни в латинизации имя Мухаммад ибн Муса аль-Хорезми в качестве первого шага к algorismus . Аль-Хорезми ( арабский : الخوارزمي , персидский : خوارزمی ., С 780-850) был персидский математик, астроном , географ и исследователь в Доме Мудрости в Багдаде , чье имя означает «уроженец Хорезма », а область , которая была частью Большого Ирана и в настоящее время в Узбекистане .

О 825, аль-Хорезми написал арабский язык трактат на индо-арабской системе счисления , которая была переведена на латинский в 12 веке под названием Algoritmi де Numero Indorum . Это название означает «Algoritmi о численности индейцев», где «Algoritmi» был переводчиком в латинизация имени Аль-Хорезми. Аль-Хорезми был самым читаемым математик в Европе в эпоху позднего Средневековья, в первую очередь через другой из его книг, в алгебре . В конце средневековой латыни, algorismus , английский « алгоритм », порча его имени, просто означает «десятичную систему счисления». В 15 - м века, под влиянием греческого слова ἀριθμός «число» ( ср «арифметика»), латинское слово было изменено на algorithmus , и соответствующий английский термин «алгоритм» является первым засвидетельствован в 17 веке; современный смысл был введен в 19 веке.

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

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

НАЕС algorismus АРС Praesens dicitur, в ква / Talibus Indorum fruimur бис Quinque figuris.

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

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

Стихотворение длиной несколько сотен строк и обобщает искусство вычисления с новым стилем индийских кости или Talibus Indorum или индуистскими цифрами.

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

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

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

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

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

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

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

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

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

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

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

Гуревич: «... неформальный аргумент Тьюринга в пользу своего тезиса оправдывает более сильный тезис: каждый алгоритм может быть смоделирована машиной Тьюринга ... согласно Savage [1987], алгоритм представляет собой вычислительный процесс, определенный с помощью машины Тьюринга» ,

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

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

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

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

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

выражая алгоритмы

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

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

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

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

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

дизайн

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

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

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

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

Реализация

Логическое NAND алгоритм , реализованный в электронном виде в 7400 чипе

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

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

Блок - схема примеры канонических структур Сут-Jacopini : последовательность (прямоугольники нисходящих страницы), то WHILE-DO и IF-THEN-ELSE. Три конструкции выполнены из примитивного условного оператора GOTO ( ЕСЛИ тест = TRUE THEN GOTO шаг ххх ) (бриллиант), безусловная GOTO (прямоугольник), различные операторы присваивания (прямоугольник) и HALT (прямоугольник). Вложение этих структур внутри присваивания-блоков приводит к сложным схемам (см Tausworthe 1977: 100, 114).

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

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

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

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

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

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

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

Мински описывает более благоприятную вариацию модели Ламбека в «счеты» в его «очень простой Основы для вычислимости ». Машина Мински протекает последовательно через пять (или шесть, в зависимости от того, как один подсчитывает) инструкции, если либо условного IF-THEN GOTO или безусловного GOTO не изменяет программный поток из последовательности. Кроме HALT, машина Мински включает в себя три задания (замена, замещение) операции: ZERO (например , содержимое места заменены на 0: L ← 0), правопреемником (например , L ← L + 1) и декремента (например , L ← L - 1 ). Редко должен программист писать «код» с таким ограниченным набором команд. Но Мински показывают (как Мелзак и Ламбек) , что его машина является Тьюринг только четыре общих типов инструкций: условным оператор GOTO, безусловным GOTO, назначение / заменами / замещением и HALT.

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

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

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

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

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

Примеры

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

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

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

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

  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
  • «←» обозначает задание . Например, « самый большойпункт » означает , что значение больших изменений в стоимости пункта .
  • « Возврат » завершает алгоритм и выводит следующее значение.

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

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

Евклида алгоритм «s вычислить наибольший общий делитель (НОД) двух чисел появляется в предложении II в книге VII („Элементарная теория чисел“) его элементов . Евклид ставит проблему таким образом: «Учитывая два числа не простых друг с другом, чтобы найти их наибольшую общую меру». Он определяет «Ряд [быть] множество состоит из единиц»: число подсчета, положительное целое число , не включая нуля. Для того, чтобы «измерить», чтобы разместить более короткой по продолжительности измерения длины сек последовательно ( Q раз) вдоль большей длины л до тех пор , оставшаяся часть г не меньше , чем короче длина х . В современных слов, остальное г = л - д × с , д , являющийся фактор, или остаточный г является «модуль», целое число-дробная часть оставшихся после разделения.

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

Первоначальное доказательство Евклида добавляет третье требование: две длины не должны быть простыми друг с другом. Евклид это предусмотрено так , чтобы он мог построить такие противное доказательство того, что общая мера два чисел является на самом деле самым большим . Хотя алгоритм Никомах таким же , как Евклид, когда числа взаимно просты друг с другом, он дает число „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.

Безвкусная программа для алгоритма Евклида

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

Следующий алгоритм оформлена в виде четырех шагов версии Кнута от Евклида и Никомаха, но, вместо того чтобы использовать разделение , чтобы найти остаток, он использует последовательные вычитаний тем короче длина s от оставшейся длины г до г не меньше , чем с . Описание высокого уровня, выделены жирным шрифтом, адаптирован из Кнут 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

Е0: [Обеспечение гсек .]

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 6
  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

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

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

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

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

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

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.

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

Следующий вариант алгоритма Евклида требует только шесть основных инструкций , чтобы делать то , что тринадцать обязаны делать по «безвкусный»; хуже, «безвкусный» требует большего количества типов инструкций. Блок - схема «Элегант» можно найти в верхней части этой статьи. В (неструктурированной) 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

Следующая версия может быть использована с объектно-ориентированных языков:

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

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

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

Делает ли алгоритм , что его автор хочет, чтобы это сделать? Несколько тестов обычно достаточно , чтобы подтвердить основные функциональные возможности . Один источник использует 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).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К реализации

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

Рекурсия
Рекурсивный алгоритм является тот , который не вызывает (делает ссылку на) себя несколько раз , пока некоторое условие (также известный как условие завершения) соответствует, который является общим для метода функционального программирования . Итерационные алгоритмы используют повторяющиеся конструкции , как петли , а иногда и дополнительные структуры данных , как стеки , чтобы решить данные проблемы. Некоторые проблемы естественным образом подходят для реализации одного или другого. Например, башни Ханоя хорошо понимают , используя рекурсивную реализацию. Каждая рекурсивная версия имеет эквивалент (но , возможно , более или менее сложные) итерационный вариант, и наоборот.
логический
Алгоритм можно рассматривать как контролируемый логический вывод . Это понятие может быть выражено следующим образом: Алгоритм = + логики управления . Логический элемент выражает аксиомы , которые могут быть использованы при вычислении и компонент управления определяет то , какой образ вычета применяется к аксиомам. Это является основой для логического программирования парадигмы. В чистых языках логического программирования, компонент управления является фиксированной и алгоритмы определяются путем подачи только логическую составляющую. Привлекательность этого подхода заключается в том, что элегантная семантика : изменение аксиом создает четко определенные изменения в алгоритме.
Последовательный, параллельный или распределенной
Алгоритмы обычно обсуждается в предположении , что компьютеры выполнения одной команды алгоритма в то время. Эти компьютеры иногда называют серийные компьютеры. Алгоритм предназначен для такой среды называется последовательный алгоритм, в отличие от параллельных алгоритмов или распределенных алгоритмов . Параллельные алгоритмы воспользоваться компьютерными архитектурами , где несколько процессоров могут работать над проблемой , в то же время, в то время как распределенные алгоритмы используют несколько машин , связанные с компьютерной сетью . Параллельные или распределенные алгоритмы разделить проблему на более симметричные или асимметричные подзадачи и собрать результаты вместе. Потребление ресурсов в таких алгоритмов не только циклы процессора на каждом процессоре , но и накладные расходы связи между процессорами. Некоторые алгоритмы сортировки можно распараллелить эффективно, но их накладные расходы связи стоит дорого. Итерационные алгоритмы , как правило , параллелизуемые. Некоторые проблемы не имеют параллельных алгоритмов и называются по своей сути последовательные проблемы.
Детерминированный или недетерминирована
Детерминированные алгоритмы решить проблему с точным решением на каждом шаге алгоритма , тогда как недетерминированные алгоритмы решения задач с помощью угадывания хотя типичные догадки сделаны более точным путем использования эвристики .
Точное или приближенное
Хотя многие алгоритмы достигают точное решение, алгоритмы аппроксимации искать приближение, которое ближе к истинному решению. Приближение может быть достигнуто путем либо с помощью детерминированной или случайной стратегии. Такие алгоритмы имеют практическое значение для многих трудных проблем. Одним из примеров приближенного алгоритма является проблемой рюкзака , где есть множество заданных элементов. Его цель состоит в том, чтобы упаковать рюкзак , чтобы получить максимальную общую стоимость. Каждый элемент имеет некоторый вес и какую - то ценность. Общий вес , который может быть осуществлен не более некоторым фиксированное число X. Таким образом, решение должно учитывать вес элементов, а также их стоимость.
Квантовый алгоритм
Они работают на реалистичной модели квантовых вычислений . Термин обычно используется для тех алгоритмов , которые кажутся по своей природе кванта, или использовать какую - то существенную особенность квантовых вычислений , такие как квантовая суперпозицию или квантовую запутанность .

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

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

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

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

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

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

По области исследования

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

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

По сложности

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Работа древних греческих геометров ( алгоритм евклидовой ), индийский математик Brahmagupta , и персидский математик Аль-Хорезми (от имени термины «чей алгоритм » и «алгоритм» являются производными), и математиков Западной Европы увенчалась Лейбниц «ы понятие исчисления ratiocinator (ца 1680):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заметки

Список используемой литературы

  • Axt, P (1959). «Об иерархии Subrecursive и примитивно рекурсивная Градусы». Труды Американского математического общества . 92 (1): 85-105. DOI : 10,2307 / 1993169 . JSTOR  1993169 .
  • Белл, К. Гордон и Newell, Allen (1971), Компьютерные Структуры: Чтения и примеры , McGraw-Hill Book Company, Нью - Йорк. ISBN  0-07-004357-4 .
  • Blass, Andreas ; Гуревич, Юрий (2003). «Алгоритмы: поиски абсолютных определений» (PDF) . Бюллетень Европейской ассоциации по теоретической информатике . 81 . Включает в себя превосходную библиографию 56 ссылок.
  • Bolter, David J. (1984). Человек Тьюринга: Западная культура в компьютерный век (1984 -е изд.). Chapel Hill, NC: Университет Северной Каролины Пресс. ISBN  978-0-8078-1564-9 ., ISBN  0-8078-4108-0
  • Boolos, Джордж ; Джеффри, Ричард (1999) [1974]. Computability и логика (4 - е изд.). Cambridge University Press, London. ISBN  978-0-521-20402-6 .: Ср Глава 3 машины Тьюринга , где они обсуждают «определенные перечислимых множеств не эффективно (механически) перечислимы».
  • Burgin, Марк (2004). Супер-рекурсивные алгоритмы . Springer. ISBN  978-0-387-95569-8 .
  • Campagnolo, ML, Мур, С. и Коста, JF (2000) Аналог характеристика subrecursive функций. В Proc. 4 - й конференции по вещественным числам и компьютерам , Odense университет, стр. 91-109
  • Церковь, Алонзо (1936а). «Неразрешимая проблема теории элементарных чисел». Американский журнал математики . 58 (2): 345-363. DOI : 10,2307 / 2371045 . JSTOR  2371045 .Перепечатано в неразрешимых , с. 89ff. Первое выражение «Thesis Церкви». См , в частности , стр 100 ( неразрешимый ) , где он определяет понятие «эффективной вычислимости» в терминах «алгоритм», и он использует слово « конечен» и т.д.
  • Церковь, Алонзо (1936b). «Обратите внимание на проблеме разрешения». Журнал символической логики . 1 (1): 40-41. DOI : 10,2307 / 2269326 . JSTOR  2269326 . Церковь, Алонзо (1936). «Поправка к Ноте на проблеме разрешения». Журнал символической логики . 1 (3): 101-102. DOI : 10,2307 / 2269030 . JSTOR  2269030 .Перепечатано в неразрешимых , с. 110ff. Церковь показывает , что проблема разрешение неразрешимо в около 3 страниц текста и 3 страниц сносок.
  • Daffa»Али Абдулла аль (1977). Мусульманская вклад в математику . Лондон: Крум Хелм. ISBN  978-0-85664-464-1 .
  • Дэвис, Мартин (1965). Неразрешимые: Основные документы О Неразрешимые предложений, неразрешимых проблем и вычислимых функций . Нью - Йорк: Raven Press. ISBN  978-0-486-43228-1 .Дэвис дает комментарии перед каждой статьей. Бумаги Геделя , Алонза Церковь , Тьюринг , Россер , Клини и Эмиль сообщение включены; процитированный в статье перечислены здесь по имени автора.
  • Дэвис, Мартин (2000). Двигатели логики: Математики и Происхождение компьютера . Нью - Йорк: WW Nortion. ISBN  978-0-393-32229-3 .Дэвис предлагает краткие биографии Лейбница , Буль , Фрег , Кантор , Гильберт , Гедель и Тьюринг с фон Нейманом , как шоу-кражей злодей. Очень краткие биографии о Жаккар , Бэббиджа , Ада Лавлейс , Клод Шеннон , Говард Айкен и т.д.
  •  Эта статья включает в себя материалы для общественности области  из  NIST документа:  черный, Пол Э. «алгоритм» . Словарь алгоритмов и структур данных .
  • Дин, Тим (2012). «Эволюция и моральное разнообразие». Baltic International Yearbook познания, логики и связи . 7 .
  • Деннет, Daniel (1995). Опасная идея Дарвина . Сложность . 2 . Нью - Йорк: Touchstone / Simon & Schuster. п. 32. Bibcode : 1996Cmplx ... 2a..32M . DOI : 10.1002 / (SICI) 1099-0526 (199609/10) 2: 1 <32 :: АИД-CPLX8> 3.0.CO; 2-Н . ISBN  978-0-684-80290-9 .
  • Dilson, Джесси (2007). Abacus ((1968, 1994) под ред.). Пресс-Мартин, Нью - Йорк. ISBN  978-0-312-10409-2 ., ISBN  0-312-10409-X
  • Юрий Гуревич , Последовательные машины абстрактных состояний Захвата последовательных алгоритмов , ACM Transactions по компьютерной логике, Том 1, № 1 (июля 2000 г.), стр. 77-111. Включает в библиографии 33 источников.
  • Хейенорта, Жан (2001). От Фреге до Гёделя, источник книги по математической логике, 1879-1931 ((1967) под ред.). Harvard University Press, Cambridge. ISBN  978-0-674-32449-7 ., 3 - е издание 1976 [?], ISBN  0-674-32449-8 (ПБК) .
  • Ходжес, Эндрю (1983). Алан Тьюринг: Энигма . Physics Today . 37 . Нью - Йорк: Саймон и Шустер . п. 107. Bibcode : 1984PhT .... 37k.107H . DOI : 10,1063 / 1,2915935 . ISBN  978-0-671-49207-6 ., ISBN  0-671-49207-1 . Ср Глава «Дух Истины» для истории , ведущей к и обсуждение, его доказательство.
  • Клини, Стивен К. (1936). «Общие рекурсивные функции натуральных чисел» . Mathematische Annalen . 112 (5): 727-742. DOI : 10.1007 / BF01565439 .Представлено Американского математического общества, сентябрь 1935 г. Перепечатано в неразрешимых , с. 237ff. Определение Клини «общей рекурсия» (известная сейчас , как мю-рекурсия) было использована Церковью в своей статье 1935 неразрешимая проблема в теории элементарных чисел , которые оказались «проблема решения» быть «неразрешимым» (т.е. отрицательного результата).
  • Клини, Стивен К. (1943). «Рекурсивные Предикаты и кванторы». Американские Операции математического общества . 54 (1): 41-73. DOI : 10,2307 / 1990131 . JSTOR  1990131 .Перепечатано в неразрешимых , с. 255ff. Клини уточнить его определение «общей рекурсии» и продолжил в главе «12. Алгоритмических теории» постулировать «диссертацию I» (стр 274.); он позже повторить этот тезис (в Клини 1952: 300) и назовите его «Тезис Чёрча» (Клини , 1952: 317) (то есть Церковь тезис ).
  • Клини, Стивен К. (1991) [одна тысяча девятьсот пятьдесят два]. Введение в метаматематику (Десятый ред.). North-Holland Publishing Company. ISBN  978-0-7204-2103-3 .
  • Кнут, Дональд (1997). Фундаментальные алгоритмы, Третье издание . Чтение, Массачусетс: Addison-Wesley. ISBN  978-0-201-89683-1 .
  • Кнут, Дональд (1969). Том 2 / Получисленные алгоритмы, Искусство программирования Первое издание . Чтение, Массачусетс: Addison-Wesley.
  • Косовский, Н. К. Элементы математической логики и ее применение в теории Subrecursive алгоритмов , LSU Публ., Ленинград, 1981
  • Kowalski, Роберт (1979). "Алгоритм = Логика + Control". Коммуникации по АКМ . 22 (7): 424-436. DOI : 10,1145 / 359131,359136 .
  • А. А. Марков (1954) Теория алгоритмов . [Перевод Jacques J. Шор-Кона и сотрудников PST] Выходные данные Москва, Академия наук СССР, 1954 [т.е., Иерусалим, Израиль Программа для научных переводов, 1961; можно получить в Управлении технических служб, Департамент США по торговле, Вашингтон] Описание 444 р. 28 см. Добавлено ШД в русском переводе работ Математического института АН СССР, v 42. Оригинальное название:. Теория algerifmov. [QA248.M2943 Дартмут колледж библиотека. Департамент США по торговле, Бюро технической службы, номер OTS 60-51085.]
  • Мински, Марвин (1967). Исчисление: Конечные и бесконечные машины (первый ред.). Prentice-Hall, Englewood Cliffs, NJ. ISBN  978-0-13-165449-5 .Мински расширяет свою «... идея алгоритма - эффективная процедура ...» в главе 5.1 вычислимости, эффективных процедур и алгоритмов. Бесконечные машины.
  • Пост, Эмиль (1936). «Конечные комбинаторные процессы, Лекарственная форма I». Журнал символической логики . 1 (3): 103-105. DOI : 10,2307 / 2269031 . JSTOR  2269031 .Печатается в неразрешимых , стр. 289ff. Сообщение определяет простой алгоритмический-подобный процесс человека писать метки или стирать знаки и идущие от коробки к коробке и в конечном счете останавливая, как он следует список простых инструкций. Это цитируется Клини как один источник его «тезис Я», так называемой Тезис Черча-Тьюринга .
  • Роджерс, младший, Хартли (1987). Теория рекурсивных функций и эффективная вычислимость . MIT Press. ISBN  978-0-262-68052-3 .
  • Россера, JB (1939). «Неофициальная экспозиция доказательств теоремы Гёделя и Чёрч теоремы». Журнал символической логики . 4 (2): 53-60. DOI : 10,2307 / 2269059 . JSTOR  2269059 .Перепечатано в неразрешимых , с. 223ff. Здесь находится знаменитое определение россеровское о «эффективном методе»:»... способ каждого шаг , который точно предопределен и который, несомненно, производят ответ в конечном числе шагов ... машина , которая будет решить любую проблему набор, без вмешательства человека за вставив вопрос и (позже) чтение ответа»(стр. 225-226, неразрешимый )
  • Сантос-Ланг, Кристофер (2014). «Моральная экология Подходы к этике Machine» (PDF) . В ван Rysewyk, Саймон; Pontier, Маттис. Машина Медицинская этика . Интеллектуальные системы, управление и автоматизация: Наука и техник. 74 . Швейцария: Springer. стр. 111-127. DOI : 10.1007 / 978-3-319-08108-3_8 . ISBN  978-3-319-08107-6 .
  • Скотт, Майкл Л. (2009). Язык программирования Прагматика (3 - е изд.). Morgan Kaufmann Publishers / Elsevier. ISBN  978-0-12-374514-9 .
  • Sipser, Майкл (2006). Введение в теорию вычислений . PWS Publishing Company. ISBN  978-0-534-94728-6 .
  • Трезвый, Эллиот; Уилсон, Дэвид Слоан (1998). Поступай с другими: Эволюция и психологии бескорыстного поведения . Cambridge: Harvard University Press.
  • Камень, Гарольд С. (1972). Введение в организацию компьютеров и структуры данных (1972 ред.). McGraw-Hill, Нью - Йорк. ISBN  978-0-07-061726-1 .Ср в частности , в первой главе под названием: Алгоритмы, машины Тьюринга и программы . Его лаконичное неофициальное определение: «... любая последовательность инструкций , которые могут быть подчинялись роботом, называется алгоритмом » (стр . 4).
  • Tausworthe, Роберт C (1977). Унифицированная разработка компьютерных программ Часть 1 Methods . Englewood Cliffs Нью - Джерси: Prentice-Hall, Inc. ISBN  978-0-13-842195-3 .
  • Тьюринг, Алан М. (1936-37). «О вычислимых числах, с приложением к проблеме разрешению». Труды Лондонского математического общества . Серия 2. 42 : 230-265. DOI : 10,1112 / ПНИЛИ / s2-42.1.230 ., Исправления, там же, т. 43 (1937) , стр. 544-546. Перепечатано в неразрешимых , с. 116ff. Знаменитая статья Тьюринга завершена в диссертации магистра в то время как в Королевском колледже Кембриджского Великобритании.
  • Тьюринг, Алан М. (1939). «Система логики на основе ординалов». Труды Лондонского математического общества . 45 : 161-228. DOI : 10,1112 / ПНИЛИ / s2-45.1.161 . ЛВП : 21,11116 / 0000-0001-91CE-3 .Печатается в неразрешимых , стр. 155ff. Бумаги Тьюринга , который определил «оракул» его докторская диссертация в то время как в Принстоне.
  • США по патентам и товарным знакам (2006), 2106,02 **> Математические алгоритмы: 2100 патентоспособности , Руководство по патенту экспертизы Процедура (MPEP). Последняя редакция августа 2006

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

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

хранилища алгоритма
Конспект лекций