История алгоритмов

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

Эволюция

Происхождение слова

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

Алгебра в начале координат переменных

Работы древнегреческих геометров, персидского математика Аль-Хорезми - часто считавшегося «отцом алгебры», и китайских и восточноевропейских математиков завершились у Лейбница понятием «ratiocinative calculus», логической алгебры.

Древние породы

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

- divide a by b, we obtain the remainder r
- replace a by b
- replace b by a
- continue as long as possible, otherwise we obtain the gcd.

Алгоритм Архимеда даёт приближение числа Pi.
Эратосфен определил алгоритм поиска простых чисел.
Аверроэс (1126 - 1198) использовал для своих вычислений алгоритм процесса.
В XII веке Аделард из Бата ввёл слово algorismus, происходящее от Аль Кваризми.

Символы, правила и парадоксы

Между 1800-ми и серединой 1900-х годов:
- Джордж Буль (1847) изобрёл бинарную алгебру, основу компьютеров. Фактически он объединил логику и вычисления в общей символике.
- Gottlob Frege (1879) and the language of formulas, which is a lingua characterica, язык, написанный специальными символами, «для чистой мысли», без всяких риторических прикрас... создаются с помощью специальных символов, манипулируемых в соответствии с четко определенными правилами.
- Джузеппе Пеано (1888) написал «Принципы арифметики, представленные новым методом», что является первой попыткой аксиоматизации математики на символическом языке.
- Альфред Норт Уайтхед и Бертран Рассел в их Principia Mathematica (1910 - 1913) в свою очередь упростили и улучшили работы Фреге.
- Курт Гедель (1931) приводит парадокс лжеца, сводящего правила рекурсии целиком к числам.

Первая формализация

Концепция была формализована в 1936 году машинами Алана Тьюринга и лямбда-исчислением Алонзо Чёрча, которые затем создали основы вычислительной техники.

Post, пространство символов

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

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

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

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

Turing and the Computer human

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

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

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

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

Поэтому простые операции должны включать:
1) Смена символов на одном из наблюдаемых квадратов.
2) Изменение от одного из наблюдаемых квадратов к другому квадрату, проходящему через N квадратов среди ранее наблюдавшихся квадратов".

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

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

Эффективный метод Россера

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

«» Эффективный метод используется здесь в конкретном смысле метода, в котором каждый шаг точно определен и который наверняка даст ответ за конечное число шагов. В этом смысле на сегодняшний день дано три точных определения. (1) Простейший из них (из-за Поста и Тьюринга) говорит, в сущности, что эффективный метод решения определённых наборов задач существует, если можно построить машину, которая будет решать любую задачу в наборе без участия человека, кроме как задавать вопрос и (позже) читать ответ. Все три определения эквивалентны, поэтому не имеет значения, какое из них использовать. Более того, тот факт, что все три эквивалентны, является веским аргументом в пользу обоснованности каждого из них".

(1) Россер ссылается на работы Чёрча и Клини и их определение i-определимости; Herbrand и G�ouml;del в их использовании рекурсии; Пост и Тьюринг с их механистической моделью вычислений.

Алгоритмическая теория Клини

Стивен К. Клини (1943) определил тезис, ныне известный и известный как «Тезис Чёрча-Тьюринга». В этом контексте:

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

См. также

Алгоритмы Определение алгоритма слова - Классификация - История алгоритмов - Список алгоритмов - Сито Эратосфена - Число Фибоначчи