Tihomirova_Teoriya_algoritmov (1)

УДК 519.712(075) ББК 22.176.я7 Т46

Тихомирова А.Н. Теория алгоритмов: Учебное пособие. М.:

МИФИ, 2008. 176 с.

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

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

Работа подготовлена в рамках Инновационной образовательной программы МИФИ.

Рецензент д-р техн. наук, доц. Андросов В.А.

Оглавление

§ 2.5. Множества с мощностью, больше чем мощность континуума 91

4

Предисловие

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

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

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

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

Памяти проф. Поварова Г.Н. посвящается данная книга.

5

Введение

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

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

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

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

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

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

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

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

6

Глава 1. Формальные описания алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

7

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

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

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

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

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

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

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

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

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

существовать.

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

8

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

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

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

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

§1.2. Классические машины Тьюринга

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

9

•язык, на котором описывается множество правил поведения,

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

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

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

машина Тьюринга.

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

С помощью машины Тьюринга можно доказать существование или не существование алгоритмов решения различных задач. Так как машина выполняет определенный алгоритм, то к машине предъявляются требования, вытекающие из свойств алгоритмов. Во-первых, машина должна быть полностью детерминированной (вычисления должны быть точные и общепонятные) и действовать в соответствии с заданной системой правил. Во-вторых, она должна допускать ввод различных “начальных данных” (соответствующих различным задачам из данного класса задач). В-третьих, заданная система правил работы машины и класс решаемых задач должны быть согласованы так, чтобы всегда можно было “прочитать” результат работы машины.

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

10