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

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

 

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

 

Развитие

 

• Происхождение названия
• Алгебра, происхождение переменных
• Алгоритмика в древней истории
• Символы, правила и парадоксы
• Первая формализация
• Пространство символов Поста
• Тьюринг и “человеческий” компьютер
• Эффективный метод Россера
• Алгоритмическая теория Клини

 

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

 

Слово алгоритм происходит от имени персидского математика Абу Абдула Мухаммеда ибн Муса Аль-Хорезми, жившего в девятом веке. Изначально оно звучало как “алгоризм” и обозначало правила арифметических вычислений с использованием индо-арабских цифр, но позднее, в XVIII в. , в европейских переводах это слово трансформировалось в привычное “алгоритм”. Значение этого слова сузилось и стало обозначать все действия для решения для решения задач.

 

Алгебра, происхождение  переменных

 

Работы древнегреческих геометров, персидского математика Аль-Хорезми, которого часто называют отцом алгебры, китайских и восточноевропейских  математиков, квинтэссенцией которых  стало понятие Лейбница “calculus ratiocinator”, алгебра логики.

 

 

 

 

 

Алгоритмика в древней  истории

 

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

 

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

- разделить число а на b, r в остатке;

- заменить a на b;

- заменить b на r;

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

 

Алгоритм Архимеда позволяет с  определенной точностью найти число Pi.

Эратосфен определил алгоритм получения  простых чисел.

Аверроэс (1126-1198 гг.) использовал алгоритмические  методы для вычислений.

Аделард Батский (XII в.) вводит понятие  “алгоритмус”, происходящее от имени  Аль-Хорезми.

 

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

 

С начала XIX в. до середины XX в. :

 

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

Готлоб Фреге (1879 г.) создает формулу языка (lingua characterica) - язык, написанный с помощью специальных символов, “для чистой мысли”, то есть без риторических украшений... построенный на конкретных символах, управляемых согласно определенным правилам.

Джузеппе Пеано (1888 г.) Его работа “Принципы арифметики, представленные в новом методе” была первой попыткой аксиоматизации математики на языке символов.

Альфред Норт Уайтхед и Бертран Рассел в своем труде “ Principia Mathematica” (1910 - 1913 гг.) упростили и расширили работу Фреге.

Курт Гёдель (1931 г.) ссылается на парадокс лжеца и тем самым полностью сводит правила рекурсии к числовому представлению.

 

 

 

 

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

 

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

 

Пространство символов Поста

 

Эмиль Пост (1936 г.) описал действия “компьютера” следующий образом:

 

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

 

Пространство символов представляет из себя следующее:

 

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

 

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

 

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

 

Тьюринг и “человеческий” компьютер

 

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

 

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

 

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

 

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

 

“Давайте представим, что операции, производимые компьютером, разделены на “простейшие операции”, которые настолько элментарны, что их дальнейшее деление трудно представить.”

 

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

 

“Тем не менее, эти простейшие операции должны включать в себя:

1) Изменение символа на одной  из исследуемых клеточек

2) Преобразование одной исследуемой  клетки в другую из числа  L ранее исследованных клеток.”

 

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

1) Возможное изменение (а) символа  вместе с возможным изменением  “состояния разума”

2) Возможное изменение (b) исследуемой клетки с возможным изменением “состояния разума”.”

 

“Теперь мы можем сконструировать  машину, выполняющую работу этого  компьютера.”

 

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

 

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

 

“”Эффективный метод” здесь имеется  в виду, как определенный метод, каждый шаг которого точно определен, и  который может дать ответ за конечное число шагов. Принимая это во внимания, можно выявить три точных определения¹. Простейшее из этих утверждений говорит, что эффективный метод решения задач существует, если построить машину, которая будет решать любую задачу без вмешательства человека, задача которого будет лишь в том, чтобы предоставить ей вопрос, а затем прочесть ответ. Все три определения эквивалентны, поэтому неважно, какое использовать. Более того, их эквивалентность в большой степени говорит о правильности каждого отдельного их них.”

 

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

 

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

 

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

¹ Россер ссылается на работы Чёрча и Клини и их “i-определенности”, работы Эрбана и Гёделя и их использование рекурсии, Поста и Тьюринга и их механические модели вычислений.