Главная Промышленная автоматика.

0.3.15. Покажите, что Р-0.3.16. Покажите, что Р

Q эквивалентно -уР.

•Q эквивалентно PAQ->ложь.

*0.3.17. Множество логических связок полно, если для любого логического утверждения можно найти эквивалентное утверждение, содержащее только эти логические связки. Покажите, что {Л, } и {V> ~}-полные множества логических связок.

Замечания по литературе

Чёрч [1956] и Мендельсон [1968] написали хорошие учебники по математической логике Халмошу [1963] принадлежит удачное введение в булеоы алгебры.

0.4. АЛГОРИТМЫ (ЧАСТИЧНЫЕ И ВСЮДУ ОПРЕДЕЛЕННЫЕ)

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

0.4.1. Частичные алгоритмы

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

Чтобы быть точными, надо определить термины команда, вход и выход. Однако мы не будем углубляться здесь в детали такого определения, так как для наших целей годится любое „разумное" определение 2).

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

) Рекомендуются также книги Клини [J952, 1967). -Яриж. перев.

) Термин вкод здесь и далее понимается двояко: как набор входных переменных (аргументов) алгоритма (с указанием нх тина) и как любое конкретное значение входной переменной {или набор значений всех переменных). Аналогично понимается, термин тхоЬ. Из контекста обычно легко установить, что имеется а виду,- Прим, перев.

Пример 0.15. Рассмотрим алгоритм Евклида для определения наибольшего общего делителя двух положительных целых чисел р и .

Алгоритм 1. Алгоритм Евклида.

Вход, р и q, положительные целые числа.

Выход, g, наибольший общий делитель чисел ряд.

Метод.

Шаг 1. Найти г, остаток от деления р на д. Шаг 2. Если г = 0, положить gg и остановиться. В противном случае положить р = д, затем q = r и перейти к шагу I. □

Посмотрим, является ли алгоритм 1 частичным алгоритмом в смысле нашего определения. Алгоритм 1, несомненно, состоит из конечного множества команд (каждый шаг алгоритма можно считать одной командой) и имеет вход и выход. Но можно ли каждую команду выполнить механически с фиксированными затратами времени и памяти?

Строго говоря, ответ на этот вопрос должен быть отрицательным, потому что если рад достаточно велики, то затраты, которые могут потребоваться для вычисления остатка от деления р на q, будут в каком-то смысле пропорциональны величинам р и q.

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

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

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



) На самом деле верхняя граница для числа шагов при q > 1 равна ёзЯ- Доказательство этого утверждения оставляем читателю в качестве упражнения.

Частичный алгоритм может не остановиться на некоторых входах по нескольким причинам. Может случиться, что процесс впадет в бесконечный цикл. Например; если частичный алгоритм содержит команду:

Шаг 1. Если х = 0, то перейти к шагу 1; в противном случае остановиться,

то для л: -О этот частичный алгоритм никогда не остановится. Эту ситуацию можно варьировать бесконечно.

Мы будем заниматься главным образом алгоритмами, т. е. всюду определенными алгоритмами. Нас интересует не только доказательство корректности алгоритмов, но и оценка нх сложности. Два главных критерия при оценке того, насколько хорошо работает алгоритм, следующие:

(1) число выполненных элементарных механических операций как функция от величины входа (временная сложность);

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

Пример 0.17. В примере 0.16 МЫ видели, что число шагов алгоритма 1 (пример 0.15). требуемое для входа {р, (/), ограничено сверху величиной 2q. Объем используемой памяти равен трем ячейкам, по одной для р, q \\ г, если считать, что любое целое число может храниться в одной ячейке. Если предположить, что объем памяти, необходимый для хранения целого числа, зависит от длины бинарного представления этого числа, то объем используемой памяти пропорционален logart,гдe л -наибольшее из чисел р я q. □

0.4.3. Рекурсивные функции

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

С помощью частичного алгоритма можно определить также и язык. Возьмем алгоритм, которому можно предъявить произвольную цепочку X. После некоторого вычисления алгоритм выдает выход „да", если цепочка х принадлежит языку. Если х не принадлежит языку, то алгоритм может остановиться и сказать „нет", а может никогда не остановиться. Такой алгоритм определяет язык L как множество входных цепочек, для кото-

Теперь перед нами встает, по-видимому, самая важная проблема: доказательство того, что частичный алгоритм делает именно то, что он должен делать. Действительно ли то число g, которое алгоритм i вычисляет по каждой паре целых чисел р и q, является их наибольшим общим делителем? Ответ на этот вопрос утвердительный; доказательство этого утверждения мы оставляем в качестве упражнения.

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

0.4.2. Алгоритмы

Теперь мы наложим на частичные алгоритмы очень важное ограничение, чтобы получить то, что можно назвать всюду определенным алгоритмом (или просто алгоритмом).

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

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



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

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

Множество, определяемог частичным алгоритмом, называется рекурсивно перечислимым. Множество, определяемое всюду определенным алгоритмом, называется рекурсивным.

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

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

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

0.4.4. Задание алгоритмов

В предыдущем разделе было неформально определено, что мы понимаем под алгоритмом, частичным или всюду определенным. Можно дать строгие определения этих терминов, используя разные формализмы. Существует много формальных способов описания алгоритмов. Отметим следующие;

(1) Машины Тьюринга [Тьюринг, 1936-1937].

(2) Грамматики Хомского типа О [Хомский, 1959а, 1963].

(3) Алгоритмы Маркова [Марков, 1951].

(4) Лямбда-исчисление [Чёрч, 1941].

(5) Системы Поста [Пост, 1943].

(6) ТАГ-системы [Пост, 1965].

(7) Большинство языков программирования [Саммет, 1969].

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

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

Большинство языков программирования, по крайней мере в принципе, пригодны для задания любого частичного алгоритма. В гл. 11 (том 2) мы увидим, к чему приводит эта их способность, когда мы пытаемся оптимизировать программы.

Мы не будем здесь обсуждать детали формализмов, предназначенных для описания алгоритмов, хотя некоторые из них появятся в упражнениях. Очень доступное введение в эту область содержится в книге Минского [1967]).

В нашей книге, как мы уже видели, для описания алгоритмов используется неформальная запись.

0.4.5. Проблемы

Слово проблема мы будем употреблять довольно специфическим образом.

Определение. Проблема (или вопрос)-это утверждение (предикат), истинное или ложное в зависимости от значений входящих в него неизвестных (переменных) определенного типа. Проблема обычно формулируется как вопрос, и мы говорим, что ответ на вопрос - „да", если это утверждение истинно, и „нет", если утверждение ложно.

Пример 0.18. Примером проблемы служит следующее утверждение: „Целое число х меньше целого числа у". Эго утверждение можно выразить в более разговорном виде, устранив упоминание о типе переменных х ц. у м придав ему форму вопроса: »х меньше f/?" □

Определение. Частный случай проблемы-это набор допустимых значений ее неизвестных.

Например, частными случаями проблемы примера 0.18 являются упорядоченные пары целых чисел.

) Можно порекомендовать также книгу Мальцева [I965J. -Ярш*. перев.





0 1 2 3 4 [5] 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0019