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

Н. А. КРИНИЦКИЙ
АЛГОРИТМЫ ВОКРУГ НАС
Издание второе
ВВЕДЕНИЕ
Двадцатый век в области науки и техники принес че­ловечеству много крупных достижений: радио, звуковое кино, телевидение, атомная энергия, космические полеты, электронные вычислительные машины — вот только глав­нейшие вехи, известные каждому. Наверное, не менее известны  кибернетика,  вирусология,   генетика.
Но не всем известно, что крупнейшим достижением на­уки XXв. является теория алгоритмов — новая математи­ческая дисциплина. Теория электронных вычислительных машин, теория и практика программирования не могут обойтись без нее. Математическая логика и кибернетика предъявляют на нее свои права. Однако она является самостоятельной наукой, которая готова служить всем наукам, и имеет свое лицо, свой предмет.
Само название — теория алгоритмов — говорит о том, что ее предмет — алгоритмы. Что это такое? Понятие ал­горитма является и очень простым и очень сложным. Его простота — в многочисленности алгоритмов, с которыми мы имеем дело, в их обыденности. Но эти же обстоятель­ства делают его туманным, расплывчатым, трудно поддаю­щимся строгому научному определению.
Слово «алгоритм» происходит от имени узбекского ма­тематика Хорезми (по-арабски ал-Хорезми), который в IXв. н. э. разработал правила четырех арифметических действий над числами в десятичной системе счисления. Совокупность этих правил в Европе стали называть «ал-горизм». Впоследствии это слово переродилось в «алго­ритм» и сделалось собирательным названием отдельных правил определенного вида (и не только правил арифме­тических действий). В течение длительного времени его употребляли только математики, обозначая правила ре­шения различных задач.
В 30-х годах XXв. понятие алгоритма стало объектом математического изучения (прежде им только пользова­лись),  а с появлением электронных вычислительных машин получило широкую известность. Развитие электрон­ной вычислительной техники и методов программирования способствовало уяснению того факта, что разработка ал­горитмов является необходимым этапом автоматизации. То, что сегодня записано в виде алгоритма, завтра будет выполняться роботами. В настоящее время слово «алго­ритм» вышло за пределы хматематики. Его стали приме­нять в самых различных областях, понимая под ним точ­но сформулированное правило, назначение которого — быть руководством для достижения необходимого ре­зультата.
Формирование научного понятия алгоритма, ставшее важной проблемой, не закончено и в настоящее время. И хотя теория алгоритмов является математической дисциплиной, она еще не очень похожа на такие широко известные науки, как геометрия или теория чисел. Она еще только зарождается, причем тем исходным материалом, на основании которого должно быть построено широкое на­учное понятие алгоритма, является интуитивное понятие, тоже очень широкое,  но недостаточно ясное.
Описывая зарождение теории алгоритмов, мы не пой­дем путем, которым шла история этой науки (хотя о ней и расскажем), а сразу познакомим читателя с современ­ным интуитивным понятием алгоритма. Затем это понятие уточним настолько, чтобы стали возможными изложение традиционных теорий алгоритмов, дальнейшее уточнение понятия алгоритма и, наконец, широкое формальное оп­ределение.
В реальной жизни выполнение всяких действий связано с расходом различных ресурсов: материалов, энергии и времени. Даже производя какие-либо записи, мы расходу­ем ресурсы (например, бумагу, чернила и время). Еще недавно некоторые задачи нельзя было решить из-за слиш­ком большого числа необходимых для этого операций и слишком малой скорости их выполнения. Появление элект­ронных вычислительных машин сделало такие задачи разрешимыми. Это значит, что «математизируя» понятие алгоритма, нужно абстрагироваться, отвлечься от ограни­ченности ресурсов, требуя только их конечности, иначе теория алгоритмов устареет, как только развитие науки и техники позволит переступить через существующие гра­ницы ресурсов.
Алгоритму в интуитивном смысле в книге противопо­ставляется алгоритм в математическом, или формальном смысле.  В  последнем  случае считается,  что понятие оп-
ределено методами, принятыми в математике, и основы­вается либо на других понятиях, имеющих математиче­ское определение, либо на первоначальных, описанных настолько четко, что их свойства могут быть приняты за аксиомы новой теории.
Теорию алгоритмов, которой посвящена эта книга, мы называем содержательной в том смысле, что именно ал­горитмы как таковые во всем их разнообразии являются ее предметом. В этом отношении она является противополож: ностью традиционных теорий, которые изучали вопросы существования и несуществования алгоритмов путем све­дения вопросов к исследованию какого-либо одного узкого класса алгоритмов и потому очень многие важнейшие проблемы оставляли вне своего поля зрения. В последнее время традиционные теории алгоритмов нередко объеди­няют названием логические, а вышеупомянутую содержа­тельную теорию стали называть аналитической.
Для понимания книги не нужна специальная подго­товка, но порою требуется большая внимательность, на­пример, при чтении главы 4, в которой коротко изложены логические теории алгоритмов. Об электронных вычисли­тельных машинах и программировании в этой книге ска­зано очень мало. Лишь столько, сколько нужно для того, чтобы стала ясной связь теории алгоритмов и этой области, которая не только нуждается в результатах теории алго­ритмов, но и порождает многие идеи этой теории.
В заключение автор пользуется случаем выразить глубокую признательность Н. М. Нагорному, оказавшему при подготовке 2-го издания большую помощь.

Глава 1
АЛГОРИТМЫ В ИНТУИТИВНОМ СМЫСЛЕ
§ 1. «Алгоритмические джунгли»
Среди разнообразных правил, с которыми приходится сталкиваться ежедневно и ежечасно, особую роль играют правила, предписывающие последовательность действий, ведущих к достижению некоторого необходимого резуль­тата. Нередко их называют алгоритмами. С научной точки зрения к этому названию нужно добавить слова «в инту­итивном смысле».
Интуицией называют знание, приобретенное в резуль­тате обширного опыта, но еще не подвергнутое научному анализу и потому недостаточно четкое и строгое. По мере накопления опыта это знание обогащается, и потому наши интуитивные представления о чем-нибудь могут посте­пенно изменяться.
Знания, облеченные в научную, в частности матема­тическую форму, не обладают такой изменчивостью, ха­рактеризуются большой точностью и служат основанием для научных выводов. В тех случаях, когда формализо­ванные знания перестают соответствовать интуитивным представлениям, научные формулировки заменяют новыми.
Разъясним понятие алгоритма в интуитивном смысле на ряде примеров (слова «в интуитивном смысле», когда это не ведет к недоразумениям, будем опускать). К числу алгоритмов не относятся правила, что-либо запрещающие, например: «Вход посторонним запрещен», «Не курить», «Въезд запрещен» (изображается известным каждому во­дителю автомобиля знаком «кирпич»). Не относятся к ним и правила, что-либо разрешающие, такие как «Раз­решена стоянка автотранспорта», «Вход», «Место для курения». А вот — «Уходя, гасите свет», «Идти слева, стоять справа» (на эскалаторе в метрополитене) — это уже алгоритмы, хотя и очень примитивные. Нужно отме­тить одну особенность алгоритма: дискретный характер процесса, определяемого самим алгоритмом. Правило «Во время движения по тротуару придерживайся правой стороны», хотя и является предписанием, но имеет непре­рывный характер и потому не относится к числу алгорит­мов. От него резко отличается текст, который можно встре­тить на некоторых телефонах-автоматах: «Приготовив двухкопеечную монету,
1) опустите ее в приемное отверстие;
2) снимите трубку и ожидайте звуковой сигнал;
3) услышав длинный непрерывный гудок, наберите требуемый номер и ожидайте ответный сигнал;
4) услышав длинные гудки, ждите ответа абонента;
5) «услышав короткие частые гудки, повесьте трубку и получите монету обратно: нужный вам абонент занят».
Подобные правила очень многочисленны и нередко имеют большое значение в нашей жизни. Рождаясь, чело­век сразу попадает в «гущу» алгоритмов.
«Перед кормлением ребенка в бутылочку с кефиром влить пастеризованный охлажденный отвар из риса или другой крупы и сахарный сироп; полученную смесь хо­рошо встряхнуть и подогреть.
Кефир — 5 г, отвар — 45 г, сахарный сироп — 5 г.
Смесь применяется по назначению врача как докорм полутора — двухмесячного   ребенка.»[1]
Не думайте, что алгоритмы играют роль только в жизни людей. Вот еще алгоритм.
«Каждого щенка следует кормить отдельно от других, иначе более сильные и активные будут съедать большую порцию.
Подкармливают 3—4 раза в день после того, как щенки пососут мать, равными небольшими порциями, начиная с полстакана молока»[2]
В последнем правиле фраза «… иначе более сильные и активные будут съедать большую порцию» к самому пра­вилу не относится. Такие фразы называют комментари­ями. Их отбрасывание на смысл правила не влияет.
Любая женщина (да, и многие мужчины) нередко об­ращаются к поваренной книге и там опять находят алго­ритмы. Приведем и оттуда пример:
«Лимон очистить от кожицы, полученную цедру на­шинковать и ввести в горячий сахарный сироп одновре­менно с желатином.  При  непрерывном  помешивании сироп нагреть до кипения, потом отжать в сироп лимонный сок, добавить лимонную кислоту, профильтровать и охла­дить.
Лимонный сок — 8, сахар — 14, желатин — 3, кислота лимонная — 0,1».[3]
Садоводы, и профессионалы и любители, занимающиеся разведением цветов, вероятно, знакомы со следующим алгоритмом:
«Перед посевом на выровненной поверхности маркером или колышком под шнур проводят бороздки глубиной от 0,5 до 1 см на расстоянии 30—35 см друг от друга. В бо­роздки распределяют семена гнездами (по 8—10 зерен в гнездо). Расстояние между гнездами 15—20—25 см в за­висимости от культуры. Заделывают семена перегноем, посыпая его сверху слоем не толще 0,5—1 см».[4]
Интересные примеры алгоритмов представляют ши­роко известные рецепты, по которым в аптеках приготов­ляют и выдают лекарства. Лишь очень опытные врачи со­ставляют каждый раз индивидуальный рецепт, в большин­стве же случаев его выписывают из специального спра­вочника:
«Rp. Arpenali0,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, которые тоже представляют собой допустимые исходные данные. Для них получится такой процесс:
/>
Сколько бы ни продолжался процесс, он не заканчива­ется и не встречает препятствий. Оказывается, что нельзя получить для исходных данных 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 — деление невозможно. Процесс на­толкнулся   на   препятствие   и  безрезультатно  оборвался.
Подчеркнем еще раз, что на практике всегда требуется реальная выполнимость алгоритма, мы же требуем лишь потенциальной выполнимости. Это связано с определен­ной абстракцией.
§ 4. Понятность алгоритма
Анализируя интуитивное понятие алгоритма, мы за­мечаем еще одну особенность. Предполагается, что испол­нитель правила всегда знает, как его выполнять. Говорят, что алгоритм понятен для исполнителя. В первых книгах по теории алгоритмов говорится даже об их общепонятно­сти. С таким утверждением согласиться нельзя. Даже свой­ство понятности не так просто, как кажется на первый взгляд.
Представим себе, что нами получен некоторый письмен­ный текст. Можно ли утверждать, что он понятен и в ка­ких случаях? Если алфавит, буквы которого использо­ваны в тексте, нам незнаком, то ответ будет один: текст непонятен. Но если все буквы принадлежат знакомому алфавиту, может оказаться, что составляющие его слова нам незнакомы. В этом случае текст тоже непонятен. А если все слова знакомы? Тогда возникает вопрос о способе их со­единения в предложения. Если он противоречит граммати­ческим правилам, опять текст непонятен. А если все грам­матические правила соблюдены? В этом случае неизвестно, понятен текст или нет. Ведь может оказаться, что он явля­ется кодом какого-то другого текста и его скрытый истин­ный смысл не совпадает с его непосредственным смыслом. Если о тексте (кроме него самого) ничего не известно, то назвать его понятным нельзя. Если известно, что текст представляет собой алгоритм, то неопределенность его уменьшается, но незначительно. Полная ясность будет лишь тогда, когда будет известно, что надо делать для того, чтобы этот алгоритм выполнить.
Свойство понятности можно, таким образом, истолко­вать как наличие алгоритма, определяющего процесс вы­полнения алгоритма, заданного в виде текста. Такое объ­яснение «понятности» позволяет предположить, что не только люди, но и животные и некоторые машины могут быть исполнителями алгоритмов.
Итак, каждому исполнителю известен алгоритм, кото­рым нужно руководствоваться для выполнения других алгоритмов, адресованных исполнителям его класса. Ис­полнитель может этот алгоритм знать, например, если он человек, или может быть так дрессирован, чтобы его вы­полнять, если он животное, или может быть так устроен, чтобы его выполнять, если он машина.
В дальнейшем (гл. 9, § 4) читатель узнает, что про некоторые   машины   (ЭВМ)   по   отношению   к   некоторым алгоритмам выполнения алгоритмов (операционным систе­мам) так и напрашивается антропоморфическое выражение «она' его знает». И все же даже у этих машин механизм понимания алгоритмов не тот, что у людей.
Может показаться, что, разъясняя понятие алгоритма, мы апеллировали к этому же понятию и допустили некор­ректное рассуждение, называемое порочным кругом. В дан­ном случае это не так (см. § 5).
§ 5. Рекурсивные определения
Если хотят ввести новое понятие, то, как говорят мате­матики, ему дают определение.
Читатель, безусловно, знаком с так называемыми пря­мыми определениями. В них новое понятие выражается через одно или несколько уже известных. Например, если нам уже известно, что такое отрезок прямой, замкнутая ломаная и три, то мы можем определить понятие треу­гольника словами «треугольник — это замкнутая ломаная, состоящая из трех прямых отрезков».
Возможно, читатель слышал и о так называемых по­рочных кругах. Порочный круг — это определение, в кото­ром новое понятие выводится либо из самого себя, либо из другого понятия, которое было из него выведено. В ма­тематике порочные круги не употребляются и поэтому по­яснить их определением, взятым из области математики, нельзя. Но неверно было бы утверждать, что порочные круги не могут быть применены с пользой. Так называ