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

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

«Rp. Arpenali 0,05 D. t. d. N 20 intabulS. По 1 таблетке З раза в день».[5]

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

А вот за столом сидит школьник. Чем он занят? По его словам, он готовит уроки. Какое к этому имеют отношение алгоритмы? Оказывается — большое. Он решает примеры по арифметике, складывает десятичные дроби. Спросите его, как он это делает, и он вам ответит:

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

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

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

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

Не только дети, но и взрослые большую часть своего времени расходуют на выполнение алгоритмов. Многие инструкции и приказы, определяющие наши действия на работе,— это алгоритмы. Даже окончив работу и желая отдохнуть, мы постоянно сталкиваемся с ними. Представьте себе, что, сняв любительский кинофильм, вы собираетесь его проявить. У вас в руках недавно купленный набор «Химикаты для обращаемых кинопленок». Что же вы находите, вскрыв его? Конечно, химикаты, но кроме них инструкцию. Вот один из ее пунктов.

«Приготовление отбеливающего раствора.

Содержимое пакета «Д» растворить в 500 мл воды при температуре 18—20° С, затем осторожно добавить содержимое пакета «Е». Объем раствора довести до 1000 мл. Раствор профильтровать»

Это опять алгоритм.

Всюду алгоритмы. Они окружают нас, переплетаются, проникают друг в друга; шага нельзя ступить, не наталкиваясь на них. Но как разительно отличаются «алгоритмические джунгли» от настоящих, в которых густые спутавшиеся растения стесняют нас, цепко держат в плену. Удивительным образом алгоритмы не связывают нас, а ведут самыми надежными путями к решению сложнейших проблем.

§ 2. Исходные данные и результаты. Массовость алгоритма

Итак, мы в «джунглях». Но чтобы в них ориентироваться, нужно понять, что такое алгоритм. Приведенные выше примеры уже позволяют осуществить некоторый анализ; еще ряд примеров содержит глава 2, в которую можно «подглядывать».

Сразу бросается в глаза, что каждый алгоритм предполагает наличие некоторых исходных данных и приводит к получению определенного искомого результата. Например, в § 1 для алгоритма приготовления детской пищи исходными данными являются порции кефира (50 г), крупяного отвара (45 г) и сахарного песка (5 г), а результатом — соответствующее количество детской пищи (очевидно, 100 г). Для медицинского рецепта (алгоритма) исходным данным является медикамент арпенал, используемый для лечения язвы желудка, а результатом—-коробочка с двадцатью таблетками и надписью «по 1 таблетке 3 раза в день». Для алгоритма сложения исходным данным является пара слагаемых (чисел), а результатом—сумма (опять число).

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

Можно подумать, что каждый алгоритм задает вполне определенный процесс. К сожалению, не совсем так. Только для самых простых алгоритмов можно говорить об определенных алгоритмических процессах. Для более сложных алгоритмов (мы это увидим на стр. 20) указать определенный процесс нельзя. Но для тех алгоритмов, о которых мы уже говорили, существование такого процесса не вызывает сомнения. Поэтому пока мы говорим о наиболее простых алгоритмах; будем считать, что каждый из них задает вполне определенный алгоритмический процесс.

Но вернемся к анализу тех предметов, которые могут быть исходными данными и результатами. Очевидно, для каждого алгоритма можно брать различные варианты исходных данных. Это видно из того, что, например, для алгоритма приготовления детской пищи можно слова «граммы» при описании исходных данных понимать как «весовые части». Качество получаемой пищи при этом не изменится. Может измениться только ее количество. Для рецепта приготовления лимонного желе, очевидно, так и сделано. Многие алгоритмы остаются в силе для различных вариантов исходных данных. Алгоритм сложения можно применить к парам любых положительных чисел. Алгоритм дополнительного кормления щенят годится не только, например, для Рексика и Бобика, но и для других щенят.

Замеченное нами свойство алгоритмов, перечисленных в § 1 (их применимость к большому числу вариантов исходных данных), называют их массовостью. Долгое время считали, что пригодность алгоритмов для многих частных случаев является настолько существенной и важной их чертой, что должна войти в научное определение алгоритма. Это исключало[6] многие правила из компетенции науки (из-за их «недостаточной» массовости) и затрудняло[7] как научные исследования, так и применение их результатов на практике (а вдруг перед нами именно ненаучный случай?), что представляет собой серьезные неудобства.

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

Расплывчатость термина «массовость» подтверждается известным парадоксом Эвбулида, который иногда называют парадоксом кучи. Сущность его можно передать, задавая себе ряд вопросов и тут же отвечая на них. Один камень — это куча? Нет. А два камня? Тоже нет. А три? В конце концов мы либо придем к выводу, что куч не существует, либо вынуждены будем признать, что есть такое число камней, увеличение которого на единицу приводит к получению кучи. И то и другое противоречит фактам и является следствием расплывчатости понятия кучи. И все же просто «отмахнуться» от свойства массовости нельзя. Нужно несколько изменить его трактовку, с тем чтобы устранить указанные выше неудобства.

Какой же смысл следует вкладывать в термин «массовость»? А вот какой. Нужно считать, что для каждого алгоритма существует некоторый класс объектов, шаги этого процесса бывают достаточно простыми, а их число не очень большим. Практически число совершенных шагов связано с количеством затраченного на их выполнение времени, а может быть (да и наверное так!), с расходом ряда других ресурсов.

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

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

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

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

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

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