Алгоритмы вокруг нас (стр. 3 из 9)

Сколько бы ни продолжался процесс, он не заканчивается и не встречает препятствий. Оказывается, что нельзя получить для исходных данных 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] статью «Танцовать». В качестве первого же значения этого слова там приведено: «плясать». Посмотрим теперь статью «Плясать» и в качестве первого значения слова «плясать» прочитаем «танцовать».

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

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

Пункт а) является прямой частью определения. В силу этого пустая строка букв (т. е. то, что стоит между кавычками в записи « ») является словом. Обычно такое слово называют пустым. В математике принято допускать существование пустых слов, содержащих 0 букв. В силу второй части определения, приписывая к пустому слову какую-либо букву, мы снова получим слово. Такое слово обычно называют однобуквенным. Мы видим, что вторая часть определения не просто говорит, что слово есть слово, а расширяет это понятие. Применяя пункт б) второй раз, мы получим двухбуквенные слова и т, д.

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

Теперь вернемся к понятию алгоритма. Его связь с понятием алгоритма выполнения алгоритмов такова, что допускает возможность рекурсивного определения алгоритма, что мы И сделаем в дальнейшем (гл. 8, § 7).

§ 5. Определенность алгоритма

Обратим внимание еще на одну особенность, присущую каждому алгоритму. Исполнитель алгоритма не только не нуждается в какой-либо фантазии или сообразительности, но, более того, алгоритм не оставляет места для проявления этих качеств, если исполнитель ими обладает. Выполняя алгоритм, действуют механически. Может быть, по мнению читателя это плохо? Может быть, эта черта алгоритма в какой-то мере подавляет творческие способности людей? Ни в коем случае! Люди могут в полной мере проявлять свои творческие способности, разрабатывая алгоритмы. Но после того как они созданы, такое проявление творческих способностей было бы неоправданным расходом психической энергии. Алгоритмы позволяют ее экономить. Таким образом, формулировка алгоритма так точна, что полностью определяет все действия исполнителя.

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

Читателю, настроенному критически, может показаться, что алгоритмы, приведенные в § 1, не очень точны. Например, результат посадки цветов при повторном выполнении алгоритма может не полностью совпадать с результатом первого выполнения (осуществленного, например, в прошлом году). Однако в пределах требуемой в данной области применения точности оба результата следует признать одинаковыми. Абсолютные точность и однозначность должны быть присущи математическим алгоритмам, а «практические» алгоритмы должны быть практически точны.

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