Раздел 4. Элементы теории алгоритмов

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

Алгоритм — это общий, единообразный, точно установленный способ реше­ния любой задачи из данной массовой проблемы. Таким образом, алгоритм всегда связан с решением массовой проблемы. Задачи такого класса отлича­ются друг от друга знамениями входящих в них параметров. Примеры алго­ритмов: извлечение квадратного корня, предельный переход, нахождение производной и т. п. Приведенное понятие алгоритма нестрогое. В нем встре­чаются слова, точный смысл которых не установлен, например "способ". Тем не менее даже при таком определении можно выделить некоторые характер­ные черты алгоритма:

1. Дискретность. Каждая последующая величина получается из значений предыдущих по определенному закону. Все величины получаются после­довательно друг за другом.

2. Детерминированность. Между всеми величинами, получаемыми алго­ритмом, существует жесткая причинная связь. Последующие значения за­висят от предыдущих.

3. Элементарность шагов алгоритма. Закон получения последующей сис­темы величин из предшествующей должен быть простым.

4. Массовость. Начальная система величин выбирается из некоторого множе­ства. Начальные условия могут варьироваться в бесконечных пределах.

5. Результативность. Конечный результат всегда должен быть получен.

Слово «алгоритм» происходит от имени математика аль Хорезми. Интуитивное понятие алгоритма работает, когда речь идет о найденном алгоритме

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

В уточнении понятия алгоритма выделяются три направления:

1. Уточнение понятия эффективно вычислимой функции. Этим занимались Л. Черч и К. Гедель. В результате был выделен класс частично рекурсив­ных функций, имеющих строгое математическое определение.

2. Машинная арифметика. Здесь сущность понятия алгоритма раскрывается путем рассмотрения процессов, осуществляемых в вычислительной ма­шине.

3. Направление, связанное с понятием нормальных алгоритмов из работ А. Маркова.

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

Первое направление – уточнение понятия алгоритма – связано с точным описанием специального класса функций, называемых рекурсивными. Число­вые функции, значения которых можно вычислить посредством алгоритма, называются вычислимыми функциями. Понятие алгоритма здесь не определе­но формально точно, поэтому понятие вычислимой функции оказывается ин­туитивным. Однако совокупность вычислимых функций, соответствующих условиям, т. е. удовлетворяющих характерным чертам алгоритма для многих процессов, оказалась одной и той же, легко описываемой в математи­ческих терминах. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций в самом широком понимании алгоритма, называется совокупностью рекурсивных функций. Рекурсивные функции впервые описаны Геделем, затем в 1936 г. Черч при­шел к такому же классу функций. Анализ идей, лежащих в основе определе­ния рекурсивных функций, позволил Черчу высказать гипотезу о том, что класс рекурсивных функций тождественен классу всюду определенных вы-числимых функций. Эта гипотеза известна под именем тезиса Черча, дока­зать ее нельзя, т. к. понятие вычислимой функции точно не определено. В силу тезиса Черча вопрос о вычислимости функции равносилен вопросу о ее рекурсивности. Понятие рекурсивной функции строгое. Поскольку в ал­горитмических проблемах речь обычно идет не об алгоритмах, а о вычисли­мости некоторых специальным образом подобранных, решающих проблему функциях, то можно строго доказать, что решающая конкретную задачу функция не может быть рекурсивной, а следовательно, не существует и алго­ритма решения этой задачи. Именно этим путем Черч доказал неразреши­мость алгоритмической проблемы логики предикатов.

Если первое направление уточняет понятие алгоритма через класс рекурсив­ных функций, то второе, связанное с машинной арифметикой, сначала уточ­няет понятие алгоритма, а затем определяет класс вычислимых функций. Это направление развито Постом и Тьюрингом. Основная идея этого направле­ния заключается в том, что алгоритмические процессы — это процессы, ко­торые могут имитироваться на подходяще построенных машинах, которые описываются в точных математических терминах. В результате оказывается, что сложные процессы можно моделировать на простых устройствах. Всякий алгоритм может быть задан некоторой функциональной схемой и реализован в соответствующей машине Тьюринга. Эта гипотеза называется тезисом Тьюринга. Его также нельзя доказать по той же причине, что и тезис Черча. Все известные до сих пор алгоритмы могут быть заданы посредством тью- ринговых функциональных схем.

Третье направление — теория нормальных алгоритмов Маркова.

Будем называть алфавитом А всякое непустое конечное множество симво­лов; сами символы называются буквами. Словом в алфавите А называется всякая конечная последовательность букв этого алфавита. Простейшими дей­ствиями в нормальных алгоритмах Маркова являются последовательные за­мены вхождений подслов специального вида на другие слова. Нормальный алгоритм может переводить слово а в слово Р, причем на множестве слов используемого алфавита слово Р однозначно определяется этим алфавитом и словом а. Нормальный алгоритм может быть и не применим к слову а, если он не преобразует а ни в какое слово.

Основное положение об «универсальности» нормальных алгоритмов — прин­цип нормализации, любой алгоритм над конечным алфавитом А эквивален­тен относительно А некоторому нормальному алгоритму над А. Этот принцип подобен тезисам Черча и Тьюринга и недоказуем из-за неопределенности формального понятия алгоритма. На практике достаточно ограни­читься алгоритмами, действующими на последовательностях натуральных чисел и выдающих в качестве значений также последовательности натураль­ных чисел. Действия нормальных алгоритмов Маркова похожи на действия машин Тьюринга.

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

Не нашли, что искали? Воспользуйтесь поиском: