Лекция 1. Основные понятия.

§ 1.1. Введение.

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

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

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

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

• Определение алгоритма через понятие вычислительной машины (машины Тьюринга, предложено Тьюрингом в 1937г.);

• Определение алгоритма через процедуру переработки слов по заданным правилам (нормальные алгоритмы, предложены Марковым в 1956г.);

• Определение алгоритма через рекурсивную функцию (предложено Клини и Геделем в 1936г.).

Как вскоре выяснилось, все эти понятия эквивалентны, что в некоторой степени свидетельствует о правильном направлении исследований в этой области.

§ 1.2. Алгоритмы: определение и основные свойства

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

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

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

Это понятие относится к исходным математическим понятиям, которые не могут быть определены через другие, более простые понятия. Иногда такое или подобное определение называют интуитивным, т.е. понятным из опыта.

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

• определенностью, то есть общепонятностью и точностью, не оставляющими место произволу,

• массовостью, то есть возможностью исходить из меняющихся в известных пределах значений исходных данных,

• результативностью, то есть направленностью на получение искомого результата,

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

Каждый алгоритм, в общем случае, должен задаваться следующими параметрами:

• множеством допустимых исходных данных,

• начальным состоянием,

• множеством допустимых промежуточных состояний,

• правилами перехода из одного состояния в другое,

• множеством конечных результатов,

• конечным состоянием.

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

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

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

• Есть проблемы, для которых алгоритм вообще не может существовать.

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

Кроме того математики стремились создавать более общие алгоритмы, которые могли решать разные классы задач. Возник вопрос: "А нельзя ли создать Всеобщий Алгоритм, который решал бы любую математическую задачу аксиоматической теории?". Известный математик Г.В.Лейбниц считал, что такой алгоритм будет найден. Однако в 1936 году американский ученый Черч формально доказал, что Всеобщего Алгоритма не существует.

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

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

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