Введение в теорию алгоритмов

Понятие алгоритма. Неформальное определение алгоритма. Примеры алгоритмов. Основные свойства алгоритмов. Роль алгоритмов в информатике. Алгоритмические проблемы. Машина Тьюринга - описание и примеры. Рекурсивные функции.

Понятие “алгоритм” давно является привычным не только для математиков. Оно является концептуальной основой разнообразных процессов обработки информации. Возможность автоматизации таких процессов обеспечивается наличием соответствующих алгоритмов. С алгоритмами первое знакомство происходит в начальной школе при изучении арифметических действий с натуральными числами.

Слово алгоритм содержит в своем составе преобразованное географическое название Хорезм. Термин “алгоритм” обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми (Магомет, сын Моисея, из Хорезма). Он жил приблизительно с 783 по 850 гг., и в 1983 году отмечалось 1200 летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово “алгоритм” – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

Вплоть до 30-х годов нашего столетия понятие алгоритма оставалось интуитивно понятным, имевшем скорее методологическое, а не математическое значение. Так, к началу ХХ в. много ярких примеров дала алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале ХХ в. были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование разрешающего алгоритма – это можно сделать, используя интуитивное понятие алгоритма. Другое дело – доказать несуществование алгоритма – для этого нужно знать точно – что такое алгоритм.

Задача точного определения понятия алгоритма была решена в 30-х годах в работах Гильберта, Черча, Клини, Поста, Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Рекурсивная функция это функция, для которой существует алгоритм вычисления ее значений по произвольному значению аргумента. Класс рекурсивных функций был определен строго как конкретный класс функций в некоторой формальной системе. Был сформулирован тезис (называемый “тезис Черча”), утверждающий, что данный класс функций совпадает с множеством функций, для которых имеется алгоритм вычисления значений по значению аргументов. Другой подход заключался в том, что алгоритмический процесс определяется как процесс, осуществимый на конкретно устроенной машине (называемой “машиной Тьюринга”). Был сформулирован тезис (называемый “тезис Тьюринга”), утверждающий, что любой алгоритм может быть реализован на подходящей машине Тьюринга. Оба данных подхода, а также другие подходы (Марков, Пост) привели к одному и тому же классу алгоритмически вычислимых функций и подтвердили целесообразность использования тезиса Черча или тезиса Тьюринга для решения алгоритмических проблем. Поскольку понятие рекурсивной функции строгое, то с помощью обычной математической техники можно доказать, что решающая некоторую задачу функция не является рекурсивной, что эквивалентно отсутствию для данной задачи разрешающего алгоритма. Аналогично, не существование разрешающей машины Тьюринга для некоторой задачи равносильно отсутствию для нее разрешающего алгоритма. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости.

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

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

Установить нижнюю оценку – значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алгоритмической модели, и такие результаты получены только в очень жестких вычислительных моделях. В связи с этим получила развитие проблематика получения “относительных” нижних оценок, так называемая теория NP -полноты, связанная с труднорешаемостью переборных задач.

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

Пример 1

Возможными исходными данными и возможными результатами пусть служат всевозможные конечные последовательности букв a и b («слова в алфавите {a, b}»). Условимся называть переход от слова Х к слову Y «допустимым» в следующих двух случаях (ниже Р обозначает произвольное слово): 1) Х имеет вид аР, а Y имеет вид Pb; 2) X имеет вид baP, а Y имеет вид Paba. Формулируется предписание: «взяв какое-либо слово в качестве исходного, делай допустимые переходы до тех пор пока не получится слово вида aaP; тогда остановись, слово Р и есть результат». Это предписание образует А., который обозначим через Â. Возьмем в качестве исходного данного слово babaa. После одного перехода получим baaaba, после второго aabaaba. В силу предписания мы должны остановиться, результат есть baaba. Возьмём в качестве исходного данного слово baaba. Получим последовательно abaaba, baabab, abababa, bababab, babababa,... Можно доказать, что процесс никогда не кончится (т. е. никогда не возникает слово, начинающееся с aa и для каждого из получающихся слов можно будет совершить допустимый переход). Возьмём теперь в качестве исходного данного слово abaab. Получим baabb, abbaba, bbabab. Далее мы не можем совершить допустимый переход, и в то же время нет сигнала остановки. Произошла т.н. «безрезультативная остановка». Итак, Â применим к слову babaa и неприменим к словам baaba и abaab

Понятие задачи «в общем виде» уточняется при помощи понятия массовая проблема. Массовая проблема задаётся серией отдельных, единичных проблем и состоит в требовании найти общий метод (то есть алгоритм) их решения. Так, проблема численного решения уравнений данного типа и проблема автоматического перевода суть массовая проблема: образующими их единичными проблемами являются в 1-м случае проблемы численного решения отдельных уравнений данного типа, а во 2-м случае — проблемы перевода отдельных фраз. Ролью массовой проблемы и определяется как значение, так и сфера приложения понятия алгоритма Массовые проблемы чрезвычайно характерны и важны для математики: например, в алгебре возникают массовые проблемы проверки алгебраических равенств различных типов, в математической логике — массовые проблемы распознавания выводимости предложении из заданных аксиом и т.п. (для математической логики понятие алгоритм существенно ещё и потому, что на него опирается центральное для математической логики понятие исчисления, служащее обобщением и уточнением интуитивных понятий «вывода» и «доказательства»). Установление неразрешимости какой-либо массовой проблемы (например, проблемы распознавания истинности или доказуемости для какого-либо логико-математического языка), т. е. отсутствия единого алгоритма, позволяющего найти решения всех единичных проблем данной серии, является важным познавательным актом, показывающим, что для решения конкретных единичных проблем принципиально необходимы специфические для каждой такой проблемы методы. Существование неразрешимых массовых проблем служит, т. о., проявлением неисчерпаемости процесса познания.

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

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

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

Про алгоритм S говорят, что он: 1) «вычисляет функцию f», коль скоро его область применимости совпадает с областью определения f и S перерабатывает всякий x из своей области применимости в f (x), 2) «разрешает множество А относительно множества X», коль скоро он применим ко всякому х из Х и перерабатывает всякий х из Х S A в слово «да», а всякий х из Х \ A в слово «нет»; 3) «перечисляет множество В», коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В. Функция называется вычислимой, если существует вычисляющий её алгоритм. Множество называется разрешимым относительно X, если существует разрешающий его относительно Х алгоритм. Множество называется перечислимым, если либо оно пусто, либо существует перечисляющий его алгоритм.

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