Теория алгоритмов

ВЫСШЕЕ ОБРАЗОВАНИЕ

серия основана в 1 996 г.






В.И. Игошин


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




УЧЕБНОЕ ПОСОБИЕ




Рекомендовано
                     УМО по образованию в области подготовки педагогических кадров в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности 01.03.01 «Математика»





znanium.com

Москва ИНФРА-М 2019

УДК 512.8; 161.2(075.8)
ББК 22.12; 87.4я73
     И269

   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

      Игошин В.И.
И269 Теория алгоритмов : учеб. пособие / В.И. Игошин. — М. : ИНФРА-М, 2019. — 318 с. — (Высшее образование).
         ISBN 978-5-16-005205-2
         Подробно изложены три формализации понятия алгоритма — машины Тьюринга, рекурсивные функции и нормальные алгоритмы Маркова, доказана их эквивалентность. Рассмотрены основные теоремы общей теории алгоритмов, теория разрешимых и перечислимых множеств, алгоритмически неразрешимые массовые проблемы, теория сложности вычислений и массовых проблем, алгоритмические проблемы математической логики и других разделов математики. Охарактеризованы взаимосвязи теории алгоритмов с компьютерами и информатикой.
         Для студентов университетов, технических и педагогических вузов, обучающихся по специальностям «Математика», «Прикладная математика», «Математик-педагог», «Учитель математики» на уровнях бакалавриата, магистратуры, а также специалитета.

УДК 512.8; 161.2(075.8)
ББК 22.12; 87.4я73

ISBN 978-5-16-005205-2

© Игошин В.И., 2012

            Предисловие










   Конкретные алгоритмы в математике и практике известны давно. В настоящее время, особенно в связи с глобальной компьютеризацией, они прочно вошли в нашу жизнь. Развитие математики и математической логики, а также в немалой степени стремительный прогресс компьютерной техники вызвали к жизни и заставили развиться в 30-60-ые годы прошлого века общую науку об алгоритмах - теорию алгоритмов. В ней объектом исследования стало именно понятие алгоритма как таковое и его самые общие свойства. Предтечами этой теории явились идеи голландского математика Л.Э.Я.Брауэра и немецкого математика Г.Вейля, высказанные ими в 20-ые годы XX в., в которых они обратили внимание на различие между конструктивными и неконструктивными доказательствами в математике. Рассуждая конструктивно при доказательстве существ вования какого-либо объекта с заданными свойствами, математик указывает способ (алгоритм) его получения. В отличие от этого, неконструктивное доказательство, или, как говорят, доказательство чистого существования не позволяет явно построить такой объект; оно лишь устанавливает логическое противоречие, если предположить, что такого объекта не существует.
   Сначала были выработаны несколько формализаций до того лишь интуитивно осознаваемого понятия алгоритма - машины Тьюринга, рекурсивные функции, алгоритмы Маркова, - доказана их эквивалентность и сформулирован знаменитый тезис Чёрча. Это позволило строго доказать алгоритмическую неразрешимость большого количества массовых проблем и начать развивать общую (или абстрактную) теорию алгоритмов, в которой конкретный формализм отошёл на второй план, а главными понятиями, по существу, снова стали интуитивно понимаемые понятия алгоритма и вычислимой функции.

3

   Всем этим вопросам и посвящается данное учебное пособие.
   В главе I рассматриваются примеры алгоритмов из реальной жизни и из математики, обсуждается понятие алгоритма на интуитивной основе и отмечается необходимость его уточнения.
   Главы II - IV посвящены конкретным формализациям понятия алгоритма - машинам Тьюринга, рекурсивным функциям и нормальным алгоритмам Маркова.
   В главе V рассматриваются основные методы общей теории алгоритмов - метод нумераций и метод диагонализации (или диагональный метод Кантора). С их помощью доказываются фундаментальные результаты общей теории алгоритмов, установленные С.Клини - теорема о параметризации (sm-птеорема) и теорема о неподвижной точке; обсуждаются применения этих теорем в теории и практике программирования.
   Разрешимым и перечислимым множествам посвящается глава VI. Здесь два классических способа задания множеств изучаются с точки зрения алгоритмической эффективности, конструктивности. Важность понятий разрешимости и перечислимости множеств для оснований математики связана с тем, что язык теории множеств является в известном смысле универсальным языком математики.
   В главе VII рассматриваются алгоритмически неразрешимые массовые проблемы. Сначала в качестве понятия, уточняющего понятие алгоритма, используется понятие машины Тьюринга (§7.1). Затем проблема алгоритмической разрешимости рассматривается в рамках общей теории алгоритмов. Завершается глава рассмотрением частично разрешимых массовых проблем и связанных с ними частично разрешимых предикатов.
   Вслед за общей теорией алгоритмов стали возникать и развиваться многочисленные теории различных конкретных алгоритмов, призванных решать те или иные конкретные математические задачи, являвшиеся, в основном, математическими моделями реальных научных и производственных задач. Эти конкретные теории питали своими идеями и проблемами общую теорию алгоритмов. Так, в общей теории возникли проблемы сложности алгоритмов, проблемы сведения одних массовых проблем к другим при их алгоритмическом решении и т.д. В свою очередь, общая теория алгоритмов создавала методологическую основу для многочисленных конкретизаций.
   Вопросам сложности вычислений и массовых проблем посвящена глава VIII. В ней рассматриваются способы сравнения и классификации массовых проблем и алгоритмов по их сложности, выделя

4

ются различные классы сложности массовых проблем, важнейшими из которых являются классы Р, NP и NP-полных массовых проблем.
   Наконец, завершают книгу две главы IX и X, посвящённые алгоритмическим проблемам математической логики и различных разделов математики. Среди них - проблемы полноты формальной арифметики и разрешимости формализованного исчисления предикатов первого порядка, десятая проблема Гильберта о разрешимости диофантовых уравнений, проблема тождества, слов в полугруппах и группах, проблема действительных корней многочлена с действительными коэффициентами.
   Теория алгоритмов развивалась в тесном взаимодействии с математической логикой. Это, вне всякого сомнения, обусловлено тесной взаимосвязью алгоритмического и логического мышления человека, схожестью алгоритмов с процессами построения логических умозаключений, использованием обеими дисциплинами формальных языков. Теория алгоритмов наряду с неотделимой от неё математической логикой являются фундаментальными теоретическими основаниями, на которых зиждутся теория и практика компьютеров, программирования и информатики. Ведь каждая компьютерная программа представляет собой выражение алгоритма решения задачи на одном из алгоритмических языков, которые тесно связаны с формализованными языками математической логики. Так что овладение основами теории алгоритмов является в настоящее время неотъемлемым компонентом образования всякого высококвалифицированного специалиста, имеющего дело с перечисленными областями.
   Курс теории алгоритмов излагается вслед за курсом математической логики. В данном учебном пособии мы будем использовать следующие наши учебные пособия: Игошин В.И. Математическая логика. - М.: Издательство ИНФРА-М, 2011 (ссылка на него будет делаться следующим образом: Учебник МЛ) и Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов. -М.: Издательский центр ’’Академия”, 2008 (на него будем ссылаться так: Задачник).
   В конце книги приведён обширный список литературы, разделённый по темам.


г. Саратов,
1 июля 2011 г.                                 В.Игошин

5

Глава I


            НЕФОРМАЛЬНОЕ (ИНТУИТИВНОЕ) ПРЕДСТАВЛЕНИЕ ОБ АЛГОРИТМАХ



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


            1.1.  Алгоритмы в жизни и в математике


   В этом параграфе рассмотрим примеры алгоритмов, известные из практической жизни и из математики.
   Алгоритмы в жизни. Понятие алгоритма стихийно формировалось с древнейших времён. Современный человек понимает под алгоритмом чёткую систему инструкций о выполнении в определённом порядке некоторых действий для решения всех задач какого-то данного класса.
   Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности. Многие наши действия доведены до бессознательного автоматизма, мы порой и не осознаём, что они регламентированы неким алгоритмом - чёткой системой инструкций. Например, наши действия при входе в магазин ’’Универсам” (сдать свою сумку, получить корзину с номером, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, предъявить чек контролёру, взять свою сумку, переложить в неё продукты, сдать корзину, покинуть магазин). Второй пример - приготовление манной каши (500 мл молока довести до кипения, при тщательном помешивании засыпать 100 г манной крупы, при помешивании довести до кипения и варить 10 минут). Автоматизм выполнения этих и многих других действий не позволяет нам осознавать их алгоритмическую сущность.


6

   Но есть немало таких действий, выполняя которые мы тщательно следуем тон или иной инструкции. Это главным образом непривычные действия, профессионально не свойственные нам. Например, если вы фотографируете один-два раза в год, то, купив проявитель для плёнки, будете весьма тщательно следовать инструкции (алгоритму) по его приготовлению: ’’Содержимое большого пакета растворить в 350 мл воды при температуре 18-20 С. Там же растворить содержимое малого пакета, Объём раствора довести до 500 мл. Раствор профильтровать. Проявлять 3-4 роликовых фотоплёнки”. Второй пример. Если вы никогда раньше не пекли торт, то, получив рецепт (алгоритм) его приготовления, постараетесь выполнить в указанной последовательности все его предписания.
   Алгоритмы в математике. Большое количество алгоритмов встречается при изучении математики буквально с первых классов школы. Это, прежде всего, алгоритмы выполнения четырёх арифметических действий над различными числами — натуральными, целыми, дробными, комплексными. Вот пример такого алгоритма: ’’Чтобы из одной десятичной дроби вычесть другую, надо: 1) уравнять число знаков после запятой в уменьшаемом и вычитаемом; 2) записать вычитаемое под уменьшаемым так, чтобы запятая оказалась под запятой; 3) произвести вычитание так, как вычитают натуральные числа; 4) поставить в полученной разности, запятую под запятыми в уменьшаемом и вычитаемом”.
   Вот пример алгоритма сложения приближенных чисел. Найти сумму чисел p, q и s, где p « 3,1416, q « 2,718 ns « 7,45.
   1.    Выделим слагаемое с наименьшим числом десятичных знаков. Таким слагаемым является число 7,45 (два десятичных знака).
   2.    Округлим остальные слагаемые, оставляя в них столько десятичных знаков, сколько их имеется в выделенном слагаемом: 3,1416 -3,14; 2,718« 2,72.
   3.    Выполним сложение приближённых значений чисел: 3,14 + 2,72 + 7,45 = 13,31.
   Итак, p + q + s « 13,31.
   Немало алгоритмов в геометрии: алгоритмы геометрических построений с помощью циркуля и линейки (деление пополам отрезка и угла, опускание и восстановление перпендикуляров, проведение параллельных прямых), алгоритмы вычисления площадей и объёмов различных геометрических фигур и тел.
   При изучении математики в вузе были освоены процедуры вычисления наибольшего общего делителя двух натуральных чисел

7

(алгоритм Евклида), определителей различных порядков, рангов матриц с рациональными элементами, интегралов от рациональных функций, приближённых значений корней уравнений и систем и т.д. Все эти процедуры являются ничем иным, как алгоритмами. Наконец в курсе математической логики были рассмотрены алгоритмы разрешимости формализованного исчисления высказываний (см. Учебник МЛ. §16) и разрешимости в логике предикатов (§23).
    Алгоритм Евклида. Это - алгоритм для нахождения наибольшего общего делителя НОД(т, п) двух натуральных чисел m, п. Рассмотрим его поподробнее с точки зрения стоящей перед нами задачи - охарактеризовать общие свойства и черты интуитивно представляемого нами понятия алгоритма.
    Даны натуральные числа m > п > 0.
   1)  Первый таг: делим m на п:
   m п пЪ^ + щ.       (п > гД
   Если ri = 0, то НОД^, п) = п.
   Если riy^O, тоНОД^п) = НОД(п,гД,         (1)
   и переходим ко второму шагу.
   2)  Второй шаг: делим п на r±:
   п = г± • b₂ + r₂.  (ri > r₂)
   Если r₂ = 0, то НОД (п, ri) = П   Если r₂#0, тоНОД(п,гД =НОД(гъг₂),        (2)
   и переходим к третьему шагу.
    3) Третий шаг: делим ri на r₂:
    rl = !- ■ b₃+ r₃- (r₂ > r₃).
    Если r₃ = 0, то НОД(г1,г₂) = r₂.
    Если r₃/0, то НОД(гьг₂) = НОД(г₂,г₃),     (3)
    и переходим к следующему шагу: делим r₂ на r₃ и так далее:


    rfc-2 =k-k-b • bk +Гк.   rr-l >Tk),
    rk-1 = rk • bk₊l + rk₊l. (rₖ > rk₊l) .
    Таким образом, получаем убывающую последовательность натуральных чисел:
        п > Щ > r-2 > ... > rₖ-l > rk > Tk₊! > 0 ,
которая обрывается (является конечной), то есть rfₑ₊ᵢ = 0 для некоторого k & N (так как п & N). Учитывая равенства (1), (2), (3), ... , получаем:

8

   НОД(т, n) = Н0Д(п,Г1) = НОД(г₁,г₂) = НОД(г₂,г₃) = ...
   ... = НОД(Гк-₂,Гк-₁') = НОДДк-!,Гк) = Гк .
   Чёткость предписаний данного алгоритма не допускает ни малейшей двусмысленности.
   Таким образом, мы видим, что алгоритмы широко распространены как в практике, так и в науке и требуют более внимательного к себе отношения и тщательного изучения методами математической науки.


            1.2. Неформальное понятие алгоритма и необходимость его уточнения


   Неформальное понятие алгоритма. Прежде чем перейти к математическому изучению понятия алгоритма, постараемся внимательно проанализировать рассмотренные примеры алгоритмов и выявить их общие типичные черты и особенности.
   1) Каждый алгоритм предполагает наличие некоторых начальных или исходных данных, а в результате применения приводит к получению определённого искомого результата. Например, в алгоритме с проявителем начальные данные — содержимое большого и малого пакетов, вода. Искомый результат - готовый к употреблению проявитель для плёнки. При вычислении ранга матрицы начальными данными служит прямоугольная таблица, составленная из m • n рациональных чисел, результат - натуральное число, являющееся рангом данной матрицы.
   Говоря о начальных данных для алгоритма, имеют в виду так называемые допустимые начальные данные, т.е. такие начальные данные, которые сформулированы в терминах данного алгоритма. Так, к числу допустимых начальных данных для алгоритма варки манной каши никак не отнесёшь элементы множества натуральных чисел, а к числу начальных данных алгоритма Евклида - молоко и манную крупу (или даже комплексные числа).
   Среди допустимых начальных данных для алгоритма могут быть такие, к которым он применим, т.е. отправляясь от которых можно получить искомый результат, а могут быть такие, к которым данный алгоритм неприменим, т.е. отправляясь от которых искомого результата получить нельзя. Неприменимость алгоритма к допустимым начальным данным может заключаться либо в том, что

9

алгоритмический процесс никогда не оканчивается (в этом случае говорят, что он бесконечен), либо в том, что его выполнение во время одного из шагов наталкивается на препятствие, заходит в тупик (в этом случае говорят, что он безрезультатно обрывается). Проиллюстрируем на примерах оба случая.
    Пример 1.2.1. Приведём пример бесконечного алгоритмического процесса. Всем известен алгоритм деления десятичных дробей. Числа 5,1 и 3 являются для него допустимыми начальными данными, применение к которым алгоритма деления приводит к искомому результату 1,7. Иная картина возникает для чисел 20 и 3, которые также представляют собой допустимые начальные данные для алгоритма деления. Но для них алгоритмический процесс продолжается бесконечно (вечно), порождая бесконечную периодическую дробь: 6,66666... . Таким образом, этот процесс не встречает препятствий и никогда не оканчивается, так что получить искомый результат для начальных данных 20 и 3 оказывается невозможно. Отметим, что обрыв процесса произвольным образом (и взятие приближённого результата) не предусматривается данным алгоритмом.
    Пример 1.2.2. Теперь приведём пример алгоритма, заходящего в тупик, безрезультатно обрывающегося. Вот его предписания:
    1. Исходное число умножить на 2. Перейти к выполнению п. 2;
    2.    К полученному числу прибавить 1. Перейти к выполнению и. 3;
    3.    Определить остаток у от деления полученной в п. 2 суммы на 3. Перейти к выполнению п. 4;
    4,    Разделить исходное число на у. Частное является искомым результатом. Конец.
    Пусть натуральные (целые положительные) числа будут допустимыми начальными данными для этого алгоритма. Для числа 6 алгоритмический процесс будет проходить так:
    Первый шаг: 6 • 2 — 12; переходим к п. 2;
    Второй шаг: 12 + 1 — 13; переходим к п. 3;
    Третий шаг: у = 1, переходим к п. 4;
    Четвёртый шаг: 6:1 = 6. Конец.
    Искомый результат равен 6. Иначе будет протекать алгоритмический процесс для исходного данного 7:
    Первый шаг: • • 2 = 14; переходим к п. 2;
    Второй шаг: 14 + 1 = 15; переходим к п. 3;

10