Теория синтаксического анализа, перевода и компиляции - Том 1 (Теория синтаксического анализа, перевода и компиляции), страница 8

Частичные алгоритмы Начнем с несколько более общего понятия частичного алгоритлеа. Вообще говоря, частичный алгоритм состоит из конечного числа команд, каждая из которых может выполняться механически за фиксированное время и с фиксированными затратами. У частичного алгоритма может быть любое число входов и выходов. Чтобы быть точными, надо определить термины команда, вход и выход. Однако мы не будем углубляться здесь в детали такого определения, так как для наших целей годится любое „разумное" определение '). Хорошим примером частичного алгоритма служит программа в каком-нибудь машинном языке. Программа состоит из конечного числа машинных команд, причем для выполнения каждой команды требуется вычисление фиксированного объема.

Однако часто бывает очень трудно понять алгоритмы, записанные на языке машинных команд. Поэтому в нашей книге принята более описательная запись алгоритмов. Приведем пример записи того типа, который мы будем использовать для описания алгоритмов. ') Рекомендуются также книги Кляня [ь962, )967!.— Прим. перев. ') Термин вход здесь н двмее поннмзется двояко. 'кзк набор входных переменнык (вргументоя) вдгорнтма [е уквзвпнем пх ткпв) н кзк любое конкрет. ное знвченне входной переменной [нян набор значепнй всех переменных). днзяогячно понимается термнп выход. Нз контексте обычно легко установить, что имеется н ннду.— Прим.

перев. 38 П 0.15. Рассмотрим алгоритм Евклида для определения наибольшего общего делителя двух положительных ц р И 0. Алгоритм 1. Алгоритм Евклида. В од. н е[, положительные целые числа. х . р Выход. д, наибольший общий делитель чисел р и д. Мел!од. Шаг 1. Найти г, остаток от деления р на е[. Шаг 2. Если г=О, положить у=а и остановиться. В противном случае положить р = е), затем а = г и перейти к шагу 1.

Г[ м, является ли алгоритм 1 частичным алгоритмом осмотрим, являет ненно состоит в смысле нашего определения. Алгоритм, несом из конечного множества команд (каждый шаг алгоритма можно считать одной командой) и имеет вход и выход. Но можно ли каждую команду вь шолнить механически с фиксированными затратами времени и памятие Строго говоря, ответ па этот вопрос должен быть отрицательным, потому что о если р и Ч достаточно велики, то затраты, которые могут потре о по ребоваться для вычисления остатка от деления м р на а, удут в како, б а ом-то смысле пропорциональны величина Однако мы моглн бы заменить шаг 1 последовательностью то ые в совокупности вычисляют остаток от деления хо имых ля выполр на е), причем количество ресурсов, необходи д. о ного такого шага, фиксировано и не зависит от р и а. т вместе (При этом число повторений каждого шага возрастает вм с р и е[.) Эти шаги могли бы, например, быть реализацией обычного метода деления с помощью карандаша и бумаги.

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

Однако читатель должен помнить, что если элементарны а ные шаги связаны только с числамп ограниченной величины, то для р б ля аботы с п оизвольпыыи числами могут потребоваться дополнительные ресурсы. 39 ГЛ. О ПРВЛВАРИТЕЛЬНЫС МАТЕМАТИЧЕСКИЕ СВРЦЕИИЙ Теперь перед нами встает, по-нидимому, самая важная проблема; доказательство того, что частичный алгоритм делает именно то, что он должен делать. Действительно ли то число а, которое алгоритм 1 вычисляег по каждой паре целых чисел р и д, является их наибольшим общим делителемг Ответ па этот вопрос утвердительный; доказательство этого утверждения мы оставляем в качестве упражнения. Можно, однако, мимоходом отметить один полезный способ доказательства того, что частичный алгоритм работает как падо,— индукцию по числу выполненных шагов.

0.4.л. Алгоритмы Теперь мы наложим на частичные алгоритмы очень важное ограничение, чтобы получить то, чтб можно назвать всюду определенным алгоритмом (или просто алгоритмом). Определение. Частичный алгоритм останавливается на данном входе, если существует такое натуральное число Т, что после выполнения 1 (не обязательно различных) элементарных команд этого алгоритма либо ие окажется ни одной команды, которую теперь можно выполнить, либо последней выполненной командой была команда „остановиться".

Частичный алгоритм, который останавливается на всех входах, т. е. на всех значениях входных данных, называется всюду определенным алгоршпжол или просто алгоритжолц Пример 0.16. Рассмотрим частичный алгоритм из примера 0.15. Заметим, что шаги 1 и 2 должны выполняться поочередно. После шага ! должен выполняться шаг 2. После шага 2 либо выполняется шаг 1, либо следующий шаг невозможен, т. е. алгоритм останавливается. Можно доказать, что для каждого входа р и Ч алгоритм останавливается не более чем через 2д шагов') и, значит, этот частичный алгоритм является просто алгоритмом.

Доказательство основано на том обстоятельстве, что величина Г, вычисляемая на шаге 1, меньше а, откуда вытекает, что последовательные значения переменной а, получающиеся после выполнения шага 1, образуют монотонно убыва4ощую последовательность. Таким образом, к тому моменту, когда шаг 2 выполнится в д-й раз, величина Г, которая всегда меньше текущего значения о и ве может быть отрицательной, должна стать равной нулю, Когда Г=-О, алгоритм останавливается. () ') Нв свмом деле верхняя Грвппцв для числа шагов прп д > 1 равна 4!оя,г. Доквэательство этол утверждения оставляем чвтэтелю в качестве упражнения. 40 0.4. АЛГОРИТМЫ (ЧАСТИЧНЫЕ И ВЯОДУ ОПРЕДЕЛЕННЫЕ! Частичный алгоритм может не остановиться на некоторых входах по нескольким причинам.

Может случиться, что процесс впадет в бссконечный цикл. Например; если частичный алгоритм содержит команду: Шаг 1. Если х= — О, то перейти к шагу 1; в противном случае остановиться, то для х=О этот частичный алгоритм никогда не остановится. Эту ситуацию можно варьировать бесконечно. Мы будем заниматься главным образом алгоритмами, т. е. всюду определенными алгоритмами. Нас интересует не только доказательство корректности алгоритмов, но и оценка их сложности.

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

В примере О 16 мы видели, что число шагов алгоритма ! (пример О.!5), требуемое для входа (р, д), ограничено сверху величиной 2о. Обьем используемой памяти равен трем ячейкам, по одной для р, д и г, если считать, что любое целое число может храниться в одной ячейке. Если предположить, что объем памяти, необходимый для храпения целого числа, зависит от длины бинарного представления этого числа, то объем используемой памяти пропорционален 1ойвп, где и — наибольшее из чисел р и а.

г) 0.4.3. Рекурсивные 4руниции Частичный алгоритм определяет некоторое отображениемножества всех подходящих входов во множество выходов.Отображение, определяемое частичным алгоритмом, называется частично- рекурсивной функцией или просто рекург44гной функцие!1. Если алгоритм всюду определен, то отображение называется оба(гргкдрсивной функцией, С помощью частичного алгоритма можно определить также и язык.

Возьмем алгоритм, которому можно предъявить произвольную цепочку х. Послс нскоторого вычисления алгоритм выдает выход, ча", если цепочка х принадлежит языку. Если х ве принадлежит языку, то алгоритм может остановиться и сказать „нет", а может никогда не остановиться. Такой алгоритм опреде,чает язык Е как множество входных цепочек, для кото- ГЛ. О. ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЬГКИЕ ГВЕДЕ НИЯ Ньи АЛГОРИТМЫ 0)АСТИЧНЫЕ И ВСЮДЧ ОПРЕДЕЛЕННЫЕ) рых он выдает выход „да". Поведение частичного алгоритма иа цепочке, не принадлежащей языку, нельзя считать допустимым с практической точки зрения. Если по прошествии некоторого времени частичный алгоритм все еще не Остановился на входе х, мы не знаем, то ли х принадлежит языку, но алгоритм еще не закончил вычисление, то ли х пе принадлежит языку и алгоритм никогда не остановится, Если бы мы определили язык с помощью всюду определенного алгоритма, то последний останавливался бы на всех входах.

Следовательно, по отношеншо к такому алгоритму наше терпение оправдано, так как нам известно, что, если ждать достаточно долго, алгоритм в конце концов остановится и скажет либо „да", либо „нет". Множество, определяемое частичным алгоритмом, называется рекурсивно лергчислимым. Множество, определяемое всюду определенным алгоритмом, называется рекурсивным. Если использовать более точные определения, можно строго доказать, что существуют множества, которые не являются рекурсивпо перечнслимыми. Можно также показать, что существуют рекурсивно перечислимые множества, которые не являются рекурсивными.