3.2. Основные понятия теории алгоритмов

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

Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Понятие <алгоритм> сформировалось в математике в 20-х годах XX в. Началом систематической разработки теории алгоритмов можно считать 1936 г. и связывают это начало с публикацией работы А.А. Черча.

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

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

В основе формализации понятия <алгоритм> лежит идея построения алгоритмической модели. Составляющими такой модели должны быть конкретный набор элементарных шагов, способы определения следующего шага и т.д. От модели также требуется простота и универсальность. Требование простоты важно для того, чтобы выделить действительно необходимые элементы и свойства алгоритма и облегчить доказательства общих утверждений об этих свойствах. Универсальность необходима для того, чтобы модель позволяла описать любой алгоритм.

Результатами теоретических исследований явились три основных класса арифметических моделей.

Первый класс моделей основан на арифметизации алгоритмов. Предполагается, что любые данные можно закодировать числами, и как следствие - всякое их преобразование становится в этом случае арифметическим вычислением, алгоритмом в таких моделях есть вычисление значения некоторой числовой функции, а его элементарные шаги - арифметические операции. Последовательность шагов определяется двумя способами. Первый способ - суперпозиция, т.е. подстановка функции в функцию, а второй - рекурсия, т.е. определение значения функции через <ранее> вычисленные значения этой же функции. Функции, которые можно построить из целых чисел и арифметических операций с помощью суперпозиций и рекурсивных определений, называются рекурсивными функциями.

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

Отсутствие символа в ячейке обозначается специальным <пустым> символом < >. Головка всегда располагается над некоторой ячейкой ленты. Она может читать и писать символы, стирать их и перемещаться вдоль ленты. Число возможных символов конечно, и образуют алфавит машины А={а₁, ... , а_m}. Головка в каждый такт работы машины находится в одном из состояний. Множество таких состоянии конечно Q={q₁, ... , q_n} и среди них выделяют начальное q₁ и конечное q_z состояния.

Элементарный шаг машины Тьюринга состоит из следующих действий:

1. головка считывает символ, записанный в ячейке, над которой она находится;

2. считанный символ а_k и текущее состояние головки q_j, однозначно определяют новое состояние q_i новый записываемый символ а_l и перемещение головки d_p (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).

Устройство управления хранит и выполняет команды машины вида q_ja_k q_ia_ld_p.

Конкретную машину Тьюринга (и алгоритм соответственно) можно задать, перечислив элементы А, Q и команды машины.

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

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

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

Для нормального алгоритма задается алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения. Если в качестве алфавита взять алфавит русского языка, в качестве множества подстановок (1) ЯУ (2) ЛУ (3) СМ (4) Вб (5) РТ (6) ТР! (7) Ох (8) На, то, используя правила 1-3:

1) проверить возможность подстановок в порядке возрастания их номеров, и если она возможна (левая часть подстановки обнаружена в исходном слове), произвести подстановку (заменив левую часть на правую);

2) если в примененной подстановке имеется символ <!>, то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;

3) если ни одна подстановка не применима, то процесс преобразования завершен, можно обнаружить, что по заданному алгоритму исходное слово <слон> превращается в слово <муха> по следующей цепочке: <слон><суон><муон><мухн><муха>.

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

машине Тьюринга и другим моделям, уточняющим понятия алгоритма.

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