A08DPPMAT_UPS2006D00

Министерство образования и науки Российской Федерации Государственное образовательное учреждение высшего профессионального образования

«Уральский государственный педагогический университет»

А.П. Ильиных

ТЕОРИЯ АЛГОРИТМОВ

Учебное пособие

Екатеринбург 2006

УДК 510.5 И 45

РЕЦЕНЗЕНТ: член-корреспондент РАН, доктор физико-математи- ческих наук, профессор А.А.Махнев.

И 45 Ильиных А.П. Теория алгоритмов: учебное пособие / Урал. гос. пед. ун-т.– Екатеринбург, 2006. – 149 с.

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

УДК 510.5

c Уральский государственный

педагогический университет, 2006c Ильиных А.П., 2006

Содержание

Лекция 1. Алгоритмы в математике. Основные черты алгоритмов . . . 4 Лекция 2. Числовые функции и алгоритмы их вычисления . . . . . . . . . 11 Лекция 3. Примитивно рекурсивные функции . . . . . . . . . . . . . . . . . . . . . 19 Лекция 4. Частично рекурсивные функции. Тезис Черча . . . . . . . . . . . 28 Лекция 5. Машины Тьюринга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35 Лекция 6. Машины с неограниченными регистрами . . . . . . . . . . . . . . . 42 Лекция 7. Вычислимость частично рекурсивных функций на МНР 53 Лекция 8. Нумерации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 Лекция 9. Универсальные функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 Лекция 10. Нормальные алгорифмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 Лекция 11. Неразрешимые алгоритмические проблемы . . . . . . . . . . 104 Лекция 12. Алгоритмические проблемы в логике и математике . . . 119 Лекция 13. Разрешимые и множества и предикаты . . . . . . . . . . . . . . . 130 Лекция 14. Перечислимые и диофантовы множества . . . . . . . . . . . . . 137 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

3

Лекция 1. Алгоритмы в математике. Основные черты алгоритмов

Алгоритмы в математике. Понятие алгоритма является одним из основных понятий современной науки. Во многих разделах математики, логики и информатики возникают вычислительные процедуры механического характера. В них требуется найти решение конкретной задачи по некоторому общему правилу (алгоритму) для решения задач данного класса. Алгоритмом является, например, правило сложения натуральных чисел, записанных в десятичной системе счисления. Оно описывает способ для вычисления суммы произвольных натуральных чисел. Зная общее правило, мы применяем его к конкретной паре чисел, например, к числам x 5627, y 4283, и получаем их сумму. В алгебре рассматривается алгоритм Евклида для нахождения НОД целых чисел или многочленов, в информатике — алгоритм обхода вершин графа и т.д.

Рассмотрим неформальное определение понятия алгоритма. Это определение не является строгим математическим определением, а является лишь разъяснением понятия на интуитивном уровне.

Алгоритм — это точное предписание, которое задает вычислительную процедуру. Данная процедура перерабатывает исходный набор данных P (входной объект) и направлена на получение обусловленного этими данными результата Q (объекта на выходе). Она состоит из отдельных, элементарных шагов — тактов работы алгоритма. Каждый шаг заключается в смене одного набора данных другим набором (объектом, состоянием). Переход от предыдущего состояния к последующему происходит по заранее заданному, конечному набору инструкций. Эти инструкции не должны предполагать никаких догадок и вероятностных соображений со стороны человека или машины, нужно только точно их исполнять.

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

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

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

4

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

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

Считается, что алгоритм A применим к исходному набору данных P тогда и только тогда, когда выполнен случай 1, т.е. когда процесс вычислений заканчивается и получен результат вычислений Q. Этот результат будем обозначать через A P . В случаях 2 и 3 результат A P не существует.

Само слово «алгоритм» происходит от латинской транслитерации «alchorismi» или «algorismi» арабского имени среднеазиатского ученого ал-Хорезми´ Мухаммеда бен Муса (780–847). По латинским переложениям арифметического трактата алХорезми средневековая Европа познакомилась с индийской десятичной позиционной системой счисления.

Основные черты алгоритмов. Итак, мы привели разъяснение, а не строгое определение алгоритма. Отметим некоторые характерные черты понятия алгоритма.

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

Детерминированность алгоритма. В алгоритмическом процессе происходит преобразование объекта P на входе в объект Q на выходе алгоритма. При этом все шаги алгоритма A, величины промежуточных вычислений и выходной объект Q однозначно обусловлены заданием парыA, P . Это свойство – детерминированность алгоритма. Детерминированность алгоритма означает, что при повторном выполнении A с объектом P на входе снова получится объект Q. Тем самым обеспечивается возможность сообщения алгоритма одним лицом другому лицу. При этом другое лицо сможет выполнять алгоритм без участия первого. В частности, возможна передача выполнения алгоритма компьютеру.

5

Массовость алгоритма. Говоря об алгоритме, мы уже отмечали такое его свойство, как массовость — требование найти единый алгоритм для решения не отдельной задачи, а серии задач из некоторого класса. Отдельные задачи класса получаются при варьировании входных данных. Поэтому для каждого алгоритма существует некоторая фиксированная, потенциально бесконечная совокупность X возможных начальных данных. Из этой совокупности выбирается объект P , поступающий на вход алгоритма. Например, в алгоритме сложения натуральных чисел в качестве X выступает множество всех пар a, b , где a, b – произвольные натуральные числа.

Изучая алгоритмы, мы придерживаемся некоторых соглашений — абстракций теории алгоритмов. В качестве примера рассмотрим абстракцию потенциальной осуществимости. Как уже отмечалось, алгоритмический процесс при выработке результата Q из исходных данных P совершает несколько отдельных шагов. Число таких шагов может быть настолько велико, что достижение результата Q является практически неосуществимым. Однако в общей теории алгоритмов мы не учитываем практическую осуществимость и считаем возможным выполнить любое конечное число шагов. Это положение называется абстракцией потенциальной осуществимости. Это же положение предполагает, что мы можем оперировать со сколько угодно большими объектами, например, сколь угодно длинными словами и т.п. Американский математик Эдвард Каснер назвал число 10100 «гуголом». Гугол больше, чем количества элементарных частиц в известной нам части Вселенной. Поэтому мы не можем практически осуществить работу со словом из 10100 букв. Однако абстракция потенциальной осуществимости разрешает нам оперировать с такими большими объектами.

Теория алгоритмов, как и любая дисциплина, кроме связи с другими дисциплинами имеет собственную проблематику. Рассмотрим в качестве примера следующий вопрос. Пусть имеется алгоритм A с множеством начальных данных X. Объект P X поступает на вход алгоритма A. К нему применяются инструкции данного алгоритма с намерением получить результат вычислений. Возможно, что на выходе алгоритма получится результат вычислений A P , а возможно такого результата нет.

Поэтому в произвольном алгоритме наряду с множеством начальных данных X имеется подмножество D в X, состоящее в точности из тех объектов P X, для которых существует результат вычислений A P .

6

Множество D называется областью применимости алгоритма. Считаем, что алгоритм A реализуется некоторой машиной M . Поместим в нее входной объект P и запустим машину. После миллиона тактов работы машины мы начинаем подозревать, что машина никогда не остановится. Но, может быть, нам нужно подождать, машина совершит еще несколько тактов работы и выдаст результат?

Как нам заранее знать, что остановка машины все же произойдет? Для этого нужно придумать алгоритм B, который по объекту P и программе машины определяет, остановится M или нет. Тем самым алгоритм B для P X определяет, верно ли, что P D или нет. Было бы хорошо, если бы алгоритм B всегда существовал. К сожалению, это не так, что будет установлено в дальнейших лекциях.

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

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

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

Формализации Черча, Тьюринга и Маркова. В двадцатых годах XX века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Она заключалась в попытке дать строгое математическое определение алгоритма, которое соответствовало бы имевшимся в то время интуитивным представлениям об алгоритме. Решение данной проблемы было получено в первой половине XX века. Мы рассмотрим следующие три варианта определения алгоритма.

7

1)С точки зрения А.Черча и С. Клини, в алгоритмическом процессе

вычисляется значение некоторой функции f x1, x2, . . . , xn , определенной на множестве натуральных чисел.

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

2)С точки зрения английского математика А.Тьюринга алгоритмический процесс — это работа некоторой воображаемой вычислительной машины — машины Тьюринга. Он предложил отождествить интуитивное понятие «алгоритм» с точным понятием «машина Тьюринга». В качестве вычислительной машины будет также рассмотрена машина с неограниченными регистрами (МНР). Это абстрактная машина, более сходная с реальным компьютером по сравнению с машиной Тьюринга.

3)Третий вариант определения алгоритма предложил в 1947 г. российский математик А.А.Марков. С его точки зрения, алгоритмический процесс – это переработка слов некоторого алфавита с помощью точно описанных правил переработки. Вместо интуитивного понятия «алгоритм» А.А.Марков вводит строгое понятие «нормальный алгорифм».

Каждый из трех вариантов определения понятия алгоритма фиксирует свой класс K рассматриваемых объектов, свои правила переработки, окончания и опознания результата. Однако эти три варианта определения понятия алгоритма равносильны. Это означает, что при подходящей кодировке объекты из K можно трактовать в виде объектов, с которыми работают при другом определении алгоритма. То же самое с правилами переработки, правилами окончания и опознания результата. При этом оказывается, что для всех определений и утверждений при одном определении алгоритма возникают аналогичные определения и утверждения при другом определении. Поэтому мы имеем взаимную моделируемость этих понятий. Это указывает на то, что мы открыли некоторую самостоятельную сущность — понятие алгоритма, а три различных определения отражают в разных формах это понятие.

В последующих лекциях будут подробно изучены данные три формы точного определения понятия алгоритма.

8

Упражнения к лекции 1

ЗАДАЧА 1. Рассмотрим в качестве алгоритма A одну из следующих операций: сложение, вычитание, умножение, деление натуральных чисел. В каждом случае описать множество объектов на входе и на выходе алгоритма A. Верно ли, что объект A P на выходе алгоритма A существует для произвольного объекта P ?

ЗАДАЧА 2. Среди инструкций алгоритма A имеется следующая. Нужно подбросить игральную кость и в зависимости от того, какое число выпало, четное или нечетное, выполнить одну из двух соответствующих инструкций. Какому необходимому требованию, предъявляемому к понятию алгоритма, не удовлетворяет данный набор инструкций?

ЗАДАЧА 3. Задан алгоритм A, на вход которого поступает произвольное натуральное число n. Требуется определить, является ли число n простым числом. Считаем шагами работы алгоритма A проверку делимости числа n на 2, на 3, . . .

1 Приведите оценку для числа шагов, достаточных для получения результата.

2 Пусть Q A P — объект на выходе алгоритма A. Как можно описать объект Q? К какому типу данных естественно отнести объект Q? Есть ли этот тип данных в языках программирования?

ЗАДАЧА 4. В лекции 1 обсуждалась следующая задача. Указать некоторый алгоритм B, который по произвольному объекту P , предъявленному на вход алгоритма A, определяет, будет ли получен результат вычислений Q A P . Верно ли, что B существует в случае, когда A— алгоритм нахождения обратной матрицы?

ЗАДАЧА 5. Пусть A — произвольный алгоритм. Какой из вариантов утверждений правильный?

1 В алгоритме A обязана (не обязана) иметься граница для размера входного объекта P ?

2 Число инструкций алгоритма A всегда конечно (возможно бесконечное число инструкций).

ЗАДАЧА 6. Возможна ли ситуация, когда для исполнения алгоритма нужна информация, отличная от инструкций алгоритма и его входного объекта?

9

ЗАДАЧА 7. В каком из следующих пунктов речь идет об абстракции потенциальной осуществимости? Указать в этом случае правильный вариант ответа. Подтвердить этот вариант ответа на конкретном алгоритме.

1 В алгоритме рассматривается правило для решения не отдельной задачи, а правило для решения серии задач.

2 Число шагов конкретного алгоритма может быть произвольным натуральным числом (число шагов конкретного алгоритма ограничено некоторым числом n, так как при большем количестве шагов невозможна их практическая реализация).

3 По произвольному объекту P , предъявленному на вход алгоритма A, мы должны знать о количестве шагов, за которые получим A P .

4 Количество инструкций алгоритма конечно, но может быть сколько угодно большим натуральным числом.

ЗАДАЧА 8. Какой из пунктов а) или б) нужно выбрать в предложениях 1 и 2 ?

1 Пусть имеется некоторое правило, и нам нужно признать это правило в качестве алгоритма для решения некоторого класса задач. Для этого: а) мы должны располагать точным определением алгоритма; б) нам достаточно интуитивного представления о понятии алгоритма.

2 Пусть нам требуется проверить доказательство несуществования некоторого алгоритма. Для этого: а) мы должны располагать точным определением алгоритма; б) нам достаточно интуитивного представления о понятии алгоритма.

ЗАДАЧА 9. Пусть для произвольного числа n 1, 2, 3, . . . нужно найти цифру с номером n после запятой в десятичной дроби, изображающей число π. Существует ли алгоритм для выполнения поставленной задачи?

ЗАДАЧА 10. Для произвольного алгоритма A возможны три случая завершения работы: 1 работа с выдачей результата; 2 бесконечная работа алгоритма; 3 безрезультатная остановка. Показать, что случай 3 введением некоторой дополнительной инструкции можно свести к случаю 2 .

10