Книга: Алгоритмы вокруг нас

Проиллюстрируем оба эти случая. Приведем пример бесконечного алгоритмического процесса. Всем известен алгоритм деления десятичных дробей. Числа 4,2 и 3 являются для него допустимыми исходными данными. При этом получается следующий процесс:

Искомый результат равен 1,4. Но совсем иная картина получится для чисел 20 и 3, которые тоже представляют собой допустимые исходные данные. Для них получится такой процесс:

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

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

1. Исходное данное умножить на 2. Перейти к выполнению п. 2.

2. К полученному числу прибавить единицу. Определить остаток у от деления этой суммы на 3. Перейти к выполнению п. 3.

3. Разделить исходное данное на у. Частное является искомым результатом. Конец.

Пусть целые неотрицательные числа (так называемые натуральные) будут допустимыми исходными данными для этого алгоритма.

Для числа 6 алгоритмический процесс будет протекать так.

Первый шаг: 6-2=12; переходим к п. 2.

Второй шаг: 12+1 = 13; у=1; переходим к п. 3.

Третий шаг: 6 : 1=6. Конец.

Искомый результат равен 6. Иначе будет протекать алгоритмический процесс для исходного данного 7.

Первый шаг: 7-2=14; переходим к п. 2.

Второй шаг: 14+1 = 15; у=0; переходим к п. 3.

Третий шаг: 7:0 — деление невозможно. Процесс натолкнулся на препятствие и безрезультатно оборвался.

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

§ 3. Понятность алгоритма

Анализируя интуитивное понятие алгоритма, мы замечаем еще одну особенность. Предполагается, что исполнитель правила всегда знает, как его выполнять. Говорят, что алгоритм понятен для исполнителя. В первых книгах по теории алгоритмов говорится даже об их общепонятности. С таким утверждением согласиться нельзя. Даже свойство понятности не так просто, как кажется на первый взгляд.

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

Свойство понятности можно, таким образом, истолковать как наличие алгоритма, определяющего процесс выполнения алгоритма, заданного в виде текста. Такое объяснение «понятности» позволяет предположить, что не только люди, но и животные и некоторые машины могут быть исполнителями алгоритмов.

Итак, каждому исполнителю известен алгоритм, которым нужно руководствоваться для выполнения других алгоритмов, адресованных исполнителям его класса. Исполнитель может этот алгоритм знать, например, если он человек, или может быть так дрессирован, чтобы его выполнять, если он животное, или может быть так устроен, чтобы его выполнять, если он машина.

В дальнейшем (гл. 9, § 4) читатель узнает, что про некоторые машины (ЭВМ) по отношению к некоторым алгоритмам выполнения алгоритмов (операционным системам) так и напрашивается антропоморфическое выражение «она' его знает». И все же даже у этих машин механизм понимания алгоритмов не тот, что у людей.

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

§ 4. Рекурсивные определения

Если хотят ввести новое понятие, то, как говорят математики, ему дают определение.

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

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

В. И. Даль — составитель первого толкового словаря русского языка. Возьмем для примера из словаря В. И. Даля[8] статью «Танцовать». В качестве первого же значения этого слова там приведено: «плясать». Посмотрим теперь статью «Плясать» и в качестве первого значения слова «плясать» прочитаем «танцовать».

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

Определение. Словом называется либо а) пустая строка букв, либо б) слово, к которому приписана буква.