Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

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

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

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

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

2) каков бы ни был алгоритм А, вычисляющий f, его сигнализи­ рующая не меньше фь

Разумеется, чем ближе друг к другу верхняя и нижняя оценки Ф1 и фг, тем точнее охарактеризована сложность самой функции f.

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

Теория сложности зависит от положенных в ее основу концеп­ ций алгоритма (рекурсивные функции, машины Тьюринга и т. п.), а также от выбранной меры сложности.

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

Рассмотрим оценки сложности алгоритма применительно к ма­ шинам Тьюринга.

' С каждой конфигурацией k, к которой применима машина Тью­ ринга, можно ассоциировать число, характеризующее сложность процесса M{k) в том или ином смысле.

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

Работу машины М будем характеризовать следующими сигнали­ зирующими функциями:

66

Сигнализирующий оператор Т ставит в соответствие каждой одноместной функции щ(х) ее сигнализирующую Фг(х) (Ф =

которого для любого а все решения могут быть эффективно найдены.

1.7. Формальные преобразования алгоритмов

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

Можно определить сильную и слабую эквивалентность алгорит­

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

горитма вводится понятие «входа» и «выхода». Для каждого вхо­ да, который имеет смысл для данного алгоритма, выполнение ал­ горитма может приводить к некоторому выходу. Пусть Xi и х% — вхо­ ды алгоритмов Ui и U2 соответственно. Алгоритмы Ui и U2 счи­ таются эквивалентными, если из условия х\ = х2 следует, что если хотя бы один алгоритм, например Uu имеет выход t/i, то и другой алгоритм также имеет выход у2, причем yi = у2.

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

В этом случае между некоторыми входами xi алгоритма Ui и входами х2 алгоритма и2 конструктивно задается некоторый изо­ морфизм / (в данном случае понимаемый просто как однозначное соответствие). Аналогично задается некоторый изоморфизм / между выходами г/i и у2 алгоритмов Ut и U2 соответственно.

68

Предикат от двух конструктивных объектов А и В «быть в соот­ ветствии, заданном изоморфизмом L» будем обозначать через

AL~B.

Эквивалентность теперь будет определяться следующим обра­ зом. Алгоритмы Ui и U2 считаются эквивалентными, если из усло­ вия х\~Хг следует, что если хотя бы один алгоритм имеет выход у и

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

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

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

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

69