Глава 1

АЛГОРИТМЫ В ИНТУИТИВНОМ СМЫСЛЕ

§ 1. «Алгоритмические джунгли»

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

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

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

Разъясним понятие алгоритма в интуитивном смысле на ряде примеров (слова «в интуитивном смысле», когда это не ведет к недоразумениям, будем опускать). К числу алгоритмов не относятся правила, что-либо запрещающие, например: «Вход посторонним запрещен», «Не курить», «Въезд запрещен» (изображается известным каждому во­дителю автомобиля знаком «кирпич»). Не относятся к ним и правила, что-либо разрешающие, такие как «Раз­решена стоянка автотранспорта», «Вход», «Место для курения». А вот — «Уходя, гасите свет», «Идти слева, стоять справа» (на эскалаторе в метрополитене) — это уже алгоритмы, хотя и очень примитивные. Нужно отме­тить одну особенность алгоритма: дискретный характер процесса, определяемого самим алгоритмом. Правило «Во время движения по тротуару придерживайся правой стороны», хотя и является предписанием, но имеет непре­рывный характер и потому не относится к числу алгорит­мов. От него резко отличается текст, который можно встре­тить на некоторых телефонах-автоматах: «Приготовив двухкопеечную монету,

1) опустите ее в приемное отверстие;

2) снимите трубку и ожидайте звуковой сигнал;

3) услышав длинный непрерывный гудок, наберите требуемый номер и ожидайте ответный сигнал;

4) услышав длинные гудки, ждите ответа абонента;

5) "услышав короткие частые гудки, повесьте трубку и получите монету обратно: нужный вам абонент занят».

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

«Перед кормлением ребенка в бутылочку с кефиром влить пастеризованный охлажденный отвар из риса или другой крупы и сахарный сироп; полученную смесь хо­рошо встряхнуть и подогреть.

Кефир — 5 г, отвар — 45 г, сахарный сироп — 5 г.

Смесь применяется по назначению врача как докорм полутора — двухмесячного ребенка.»¹

Не думайте, что алгоритмы играют роль только в жизни людей. Вот еще алгоритм.

«Каждого щенка следует кормить отдельно от других, иначе более сильные и активные будут съедать большую порцию.

Подкармливают 3—4 раза в день после того, как щенки пососут мать, равными небольшими порциями, начиная с полстакана молока»²

В последнем правиле фраза «...иначе более сильные и активные будут съедать большую порцию» к самому пра­вилу не относится. Такие фразы называют комментари­ями. Их отбрасывание на смысл правила не влияет.

Любая женщина (да, и многие мужчины) нередко об­ращаются к поваренной книге и там опять находят алго­ритмы. Приведем и оттуда пример:

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

Лимонный сок — 8, сахар — 14, желатин — 3, кислота лимонная — 0,1».³

Садоводы, и профессионалы и любители, занимающиеся разведением цветов, вероятно, знакомы со следующим алгоритмом:

«Перед посевом на выровненной поверхности маркером или колышком под шнур проводят бороздки глубиной от 0,5 до 1 см на расстоянии 30—35 см друг от друга. В бо­роздки распределяют семена гнездами (по 8—10 зерен в гнездо). Расстояние между гнездами 15—20—25 см в за­висимости от культуры. Заделывают семена перегноем, посыпая его сверху слоем не толще 0,5—1 см».⁴

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

«Rp. Arpenali 0,05 D. t. d. N 20 in tabul S. По 1 таблетке З раза в день».⁵

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

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

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

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

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

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

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

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

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

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

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