Н. А. КРИНИЦКИЙ

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

Издание второе

ВВЕДЕНИЕ

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

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

Само название — теория алгоритмов — говорит о том, что ее предмет — алгоритмы. Что это такое? Понятие алгоритма является и очень простым и очень сложным. Его простота — в многочисленности алгоритмов, с которыми мы имеем дело, в их обыденности. Но эти же обстоятельства делают его туманным, расплывчатым, трудно поддающимся строгому научному определению.

Слово «алгоритм» происходит от имени узбекского математика Хорезми (по-арабски ал-Хорезми), который в IX в. н. э. разработал правила четырех арифметических действий над числами в десятичной системе счисления. Совокупность этих правил в Европе стали называть «ал-горизм». Впоследствии это слово переродилось в «алгоритм» и сделалось собирательным названием отдельных правил определенного вида (и не только правил арифметических действий). В течение длительного времени его употребляли только математики, обозначая правила решения различных задач.

В 30-х годах XX в. понятие алгоритма стало объектом математического изучения (прежде им только пользовались), а с появлением электронных вычислительных машин получило широкую известность. Развитие электронной вычислительной техники и методов программирования способствовало уяснению того факта, что разработка алгоритмов является необходимым этапом автоматизации. То, что сегодня записано в виде алгоритма, завтра будет выполняться роботами. В настоящее время слово «алгоритм» вышло за пределы математики. Его стали применять в самых различных областях, понимая под ним точно сформулированное правило, назначение которого — быть руководством для достижения необходимого результата.

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

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

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

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

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

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

В заключение автор пользуется случаем выразить глубокую признательность Н.М. Нагорному, оказавшему при подготовке 2-го издания большую помощь.

Глава 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 мл. Раствор профильтровать»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Проиллюстрируем оба эти случая. Приведем пример бесконечного алгоритмического процесса. Всем известен алгоритм деления десятичных дробей. Числа 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. Рекурсивные определения

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Определенность алгоритма, его механический характер снова наводят нас на мысль о том, что исполнителями алгоритмов могут быть не только люди, но и животные, а также особые машины-автоматы. Этим подтверждается аналогичный вывод, сделанный нами в § 4; в гл. 9 это будет доказано.

§ 6. Выводы

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

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

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

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

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

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

Глава 2

СОЗДАНИЕ АЛГОРИТМОВ

§ 1. Роль алгоритмов в науке и технике

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

Особое значение имеют алгоритмы, накопленные в математике, потому что математика пронизывает другие науки и ее богатство является богатством всех наук. Уже довольно давно ученые и инженеры заметили, что если удалось получить алгоритм решения какой-нибудь задачи, то можно создать машину, которая решала бы эту задачу, т. е. можно автоматизировать ее решение. Практика упрямо подтверждала этот факт. Наука его объяснила полностью только недавно. Читатель познакомится с этим в § 3 гл. 6.

Алгоритмы являются: 1) формой изложения научных результатов; 2) руководством к действию при решении уже изученных проблем и, как следствие: 3) средством, позволяющим экономить умственный труд; 4) необходимым этапом при автоматизации решения задач; 5) сред-ством (инструментом), используемым при исследовании и решении новых проблем (особенно это касается математических алгоритмов); 6) одним из средств обоснования математики (см. гл. 4); 7) одним из средств описания сложных процессов (см. гл. 9, 10).

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

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

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

§ 2. Как возникают алгоритмы

Одним из источников алгоритмов является практика, которая предоставляет нам две основные возможности: наблюдение и эксперимент (а также любые их комбинации).

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

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

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

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

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

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

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

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

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

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

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

Перечислим наиболее часто применяемые приемы.

1) Конструирование алгоритмов. Этот прием заключается в том, что новый алгоритм получают комбинированием уже известных алгоритмов как составных частей.

2) Эквивалентные преобразования алгоритмов. Два алгоритма называют эквивалентными, если: а) всякий вариант исходного данного, допустимый для одного из них, допустим и для другого; б) применимость одного алгоритма к какому-либо исходному данному гарантирует, что и другой алгоритм применим к этому исходному данному; в) результаты, даваемые этими алгоритмами для одного и того же исходного данного, между собой одинаковы. Замечу, что совершенно неправильно эквивалентные алгоритмы называть различными формами одного и того же алгоритма.

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

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

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

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

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

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

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

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

§ 3. Задачи на построение алгоритмов

Можно было бы продолжить изложение и обоснование различных алгоритмов, накопленных в математике. Взамен этого мы лишь перечислим некоторые из них, для того чтобы создать у читателя правильное впечатление об их разнообразии и многочисленности. Алгоритмами являются правила для решения систем алгебраических линейных уравнений (существует большое число таких правил), правила дифференцирования функций и правила интегрирования, изучаемые в курсе математического анализа, правило Штурма — Лиувилля нахождения приближенного значения корня произвольного уравнения f(х)=0. Алгоритмами являются также и многие другие правила для решения различных задач с помощью циркуля и линейки, известные читателю из школьного курса. Если бы мы вздумали приводить здесь все эти алгоритмы и обосновывать их корректность, то, безусловно, не довели бы эту работу до конца из-за ее большого объема.

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

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

В 1742 г. математик X. Гольдбах, петербургский академик, в письме к Л. Эйлеру выдвинул проблему: доказать, что каждое целое число, которое больше или равно шести, может быть представлено в виде суммы трех простых чисел.

Этой проблеме можно придать следующий вид. Найти алгоритм, который позволил бы для любого целого числа, большего, чем 6, найти хотя бы одно разложение на три простых слагаемых. В ответном письме Л. Эйлер заметил, что для четных чисел эта проблема эквивалентна проблеме разложения числа на два простых слагаемых. В 1937 г. И. М. Виноградов доказал, что всякое достаточно большое нечетное число представляется суммой трех простых чисел; впоследствии была указана и нижняя граница, предполагаемая в доказательстве И. М. Виноградова, так что для нечетных чисел проблема Гольдбаха уже решена, но для четных чисел она не решена и до настоящего времени.

Заметим, что алгоритм ее решения был бы очень несложен: если задано четное N, нужно было бы (с помощью алгоритма Эратосфена) найти все не превосходящие его простые числа, далее последовательно отнимать каждое из них от заданного N и смотреть, не содержится ли разность среди уже полученных простых чисел. Беда в том, что до сих пор не удалось доказать корректность этого алгоритма, и потому нельзя его считать алгоритмом разложения любого четного числа на два простых слагаемых.

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

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

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

Наконец, задача удвоения куба гласит: требуется найти алгоритм, позволяющий по стороне любого куба с помощью циркуля и линейки построить сторону куба, объем которого вдвое больше объема заданного.

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

Нужно подчеркнуть, что алгоритмы для квадратуры круга, трисекции угла и удвоения куба невозможны, если допускать только операции, выполнимые с помощью циркуля и линейки, причем линейка используется только для проведения прямых через пары точек и никак иначе. Уже Архимед предложил метод трисекции угла, в котором допускалась операция, состоящая из двух действий: 1) нанесения на линейке двух точек, копирующих две данные точки чертежа, 2) такого перемещения линейки, чтобы одна из отмеченных на ней точек скользила по прямой, а другая по окружности.

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

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

§ 4. Антиномии

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

Парадокс Рассела (открыт в 1902 г.). Если парадокс Кантора возникает для множества, которое содержит себя в качестве своего элемента, то парадокс Рассела связан с множествами, не содержащими себя в качестве своих элементов. Для удобства будем множество, не содержащее себя в качестве элемента, называть обычным, а множество, содержащее себя в качестве элемента,— необычным.

Парадоксальным является множество всех обычных и только обычных множеств. Чтобы в этом убедиться, проверим, является ли оно само обычным или необычным. Сперва предположим, что оно обычное. Но тогда, будучи множеством всех обычных множеств, оно содержит и себя. Стало быть, оно необычное. Предположив, что оно обычное, мы получили противоречие.

Но, может быть, оно необычное, и дело с концом? Проверим. Если оно необычное, то, будучи множеством только обычных, оно себя в качестве элемента не содержит, а значит, является обычным. Опять противоречие.

Интересно, что парадокс Рассела может возникнуть и для каталогов, которыми мы уже пользовались для построения парадокса Кантора.

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

Парадокс брадобрея. Парадокс Рассела можно сформулировать без привлечения понятия множества. Представим себе, что один из солдат оказался по профессии парикмахером. Узнав об этом, командир полка приказал ему брить всех тех и только тех, кто сам себя не бреет. Все было хорошо, пока не пришло время побрить самого себя. Оказалось, что побрить себя нельзя, так как приказано брить только тех, кто себя не бреет; не брить себя тоже нельзя, потому что приказано брить всех, кто себя не бреет.

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

§ 5. Выводы из антиномий

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

Нужно сказать, что математики реагировали на землетрясение по-разному. Одни стали во всем сомневаться. Известный математик Ю. Дедекинд после опубликования антиномии Рассела на некоторое время прекратил публикацию своих работ. Математик Г. Фреге кончал в это время издание своего большого труда, подготовке которого он посвятил десять лет жизни. В первой же фразе послесловия он говорит, что фундамент построенного им здания поколеблен парадоксом Рассела. А. Пуанкаре, о котором мы уже говорили, изменил свое отношение к теории множеств. Были, конечно, и такие математики, которые на открытие антиномий никак не реагировали и бездумно продолжали применять теорию множеств, правда, в той ее части, в которой не обнаружено антиномий. Этих математиков обычно называют последователями классицизма. Но многие математики стали искать пути устранения противоречий.

Некоторые полагали, что противоречия возникают благодаря дефектам самой логики и стали пересматривать именно ее.

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

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

Четвертые усмотрели причину кризиса математики в том, что ряд математических объектов и методов являются неконструктивными. Разъясним последнюю точку зрения.

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

§ 1. Может ли машина мыслить?

Может ли человек решить алгоритмически

неразрешимую проблему?

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

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

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

Действительно, они считают, что человек может мыслить, машина — не человек; значит, она не может мыслить. Это неверное рассуждение. Оно не опровергает того, что машины могут мыслить. Прошу читателя не делать из этих слов вывода о том, будто автор считает, что машины могут мыслить.

Чтобы ответить на такой сложный вопрос, нужно прежде всего решить, по каким признакам можно распознать способность к мышлению. Даже среди людей есть индивидуумы, которые не могут мыслить.

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

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

§ 2. Детерминированность машин. Самообучение

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

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

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

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

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

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

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

§ 3. Сознание машин. Алгоритмическое моделирование

Если Вы, уважаемый читатель, дошли до этих строк, то автор может считать, что не зря трудился. Автор надеется, что ему удалось показать, какую роль в нашей жизни и науке играют алгоритмы. Мы их встречаем везде и всегда, даже в музыке (здесь ноты — это алгоритмы).

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

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

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

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

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

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

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

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

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

Из широкого формального определения алгоритма вытекает, что алгоритм не только может, решая задачу, перерабатывать свою запись, но может перерабатывать и запись своего алгоритма выполнения. Для этого нужно более отчетливо вспомнить его «папу» (алгоритм выполнения), который тоже алгоритм и имеет своего «папу», приходящегося нашему алгоритму «дедушкой». Это значит, что, работая, алгоритм выполнения может перерабатывать и себя. Обозначая исходное данное через s_it j, алгоритм— через t_t, а результат—через р_г__}, можем составить формулу из которой указанная возможность и вытекает.

Применяя это соображение к ЭВМ, в 1977 г. (в 1-м издании данной книги) мы пришли к выводу о возможности машины, которая обладала бы «способностью» перестраиваться, если этого требует программа. Появление таких машин теперь — свершившийся факт.

В § 1 данной главы мы почти допустили возможность мышления машин. Но наша книга посвящена не машинам, а алгоритмам. Сформулируем же упомянутую проблему в терминах теории алгоритмов. Очевидно, вопрос ставится не о том, чтобы любая машина мыслила, а о возможности создания такой машины, для которой можно составить программу мышления. Если отвлечься от ограниченности ресурсов времени и ЗУ, вопрос упрощается: достаточно, чтобы машина была универсальной (типа ЭВМ).

Мы знаем, что ЭВМ являются физическими моделями коллективов алгоритмов. Теперь представим себе условия, в которых обычно находится мыслящий человек. Он располагает некоторыми сведениями, хранящимися у него в мозге; оперируя ими, он по мере надобности обращается к внешним источникам — книгам, справочникам, задает вопросы другим людям; кроме того, он, может быть, получает сведения путем экспериментов. В конце концов он создает некоторый результат своего мышления. Для упрощения можно считать, что мышление производится без привлечения экспериментов. Правда, с самого начала мы приняли еще одно упрощение: ограничились случаем, когда мышление протекает «в тиши кабинета», тогда как нередко человек мыслит, находясь во взаимодействии с изменяющимся реальным миром. Между мыслящим человеком и коллективом алгоритмов напрашивается чисто внешняя аналогия. То, что хранится у человека в мозге (его знания),— подобно основному операнду; сведения, получаемые извне по мере надобности, подобны потокам частных операндов(см. конец § 10 гл. 8); действия, совершаемые мозгом, напоминают нам процесс выполнения открытого коллектива алгоритмов. Очень упрощая картину, можно предположить, что дополнительные сведения собраны заранее в некоторой информационной системе (см. § 2 гл. 10) без обновления, присоединяя которую к открытому коллективу алгоритмов, мы превращаем его в закрытый. В аналитической теории алгоритмов доказано, что каждый закрытый коллектив алгоритмов эквивалентен некоторому одиночному алгоритму.

Таким образом, в самом простом случае проблема возможности мышления машин сводится к вопросу возможности разработки алгоритма, эквивалентно моделирующего работу мозга. Мозг (и даже мозг всех людей) хранит конечный объем сведений и существует конечное время. Не будет грубой ошибкой, если мы посчитаем, что сведения хранятся в мозге в форме символьной конструкции (реализованной физически или, если хотите,— биологически). Существует только конечное число символьных конструкций, которые могут быть размещены в ЗУ конечного размера (т. е. в мозге и в информационной системе). Таким образом, перед нами задача о построении алгоритма, входной язык операндов которого конечен. Такая задача алгоритмически разрешима, но только потенциально. Реально ее разрешить методом алгоритмизации нельзя из-за ее большой трудоемкости.

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

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

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

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

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

Наконец поняли, что самое математическое описание прототипа можно считать его моделью (математической). Эта простая мысль явилась результатом длительных исследований и размышлений. Сейчас ее справедливость не вызывает сомнений! Математическую теорию моделей можно найти в книгах по абстрактной алгебре и в книгах по математической логике. Абстрактная алгебра утверждает, что модель — это множество, на котором задана некоторая совокупность отношений. Логика рассматривает модели систем аксиом — множества, элементы которых таковы, что свойства этих элементов удовлетворяют указанным аксиомам и следствиям из них. Мы видим уже три различных определения математической модели. Два последних являются частными случаями первого. Повторим его: математической моделью прототипа называется некоторое его математическое описание. Это математическое описание может быть произведено различными математическими средствами. В частности, описание прототипа может быть алгоритмическим, а если оно рассчитано на применение ЭВМ, то — программным.

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

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

Имитационное моделирование применяется для исследования различных процессов путем их условного воспроизведения, при котором каждый шаг процесса-прототипа заменяется одним или несколькими шагами моделирующего алгоритма. Алгоритмическое описание процессов (см. § 3 гл. 10) является частным случаем имитационного моделирования. Большой интерес представляет так называемое статистическое моделирование, при котором имитация процесса сводится к вычислению какого-либо параметра или ряда параметров, изменяющихся при функционировании прототипа и записи получаемых значений. После того как произведено большое число имитаций при соответствующих изменениях имитации, полученные результаты подвергаются статистической обработке точно так же, как обычно обрабатывают результаты эксперимента. Статистическое имитационное моделирование иногда позволяет обойтись без дорогостоящих опытов. § 4. Последние замечания

В заключение данной книги скажем несколько слов о вопросах, относящихся к области мировоззрения и являющихся по отношению к аналитической теории алгоритмов предварительными. Эти вопросы уже были очень коротко затронуты в § 5 гл. 3 и в § 3 гл. 5. Там упоминалось, что теория алгоритмов является основой конструктивного направления в обосновании математики. Сразу отметим, что конструктивные идеи в математике не сводятся к теории алгоритмов, которая лишь наиболее последовательна в этом отношении. Ограничимся только теорией алгоритмов.. В теории алгоритмов основой для получения всевозможных конструктивных объектов являются некоторые первоначальные объекты. Математического обоснования их конструктивности нет. С таким же правом их можно считать и неконструктивными. Доматематическое их обоснование заключается в том, что их практическое существование или (если это операции) практическая возможность их выполнения ни у кого не вызывают сомнения. В логических теориях алгоритмов первоначальными являются буквы, слова и некоторые операции (например, в теории нормальных алгоритмов — марковские подстановки); первоначальной является также способность преобразовывать любую символьную конструкцию в слово. Вопрос о том, откуда берутся слова-операнды ни явно, ни неявно не затрагивается. В аналитической теории алгоритмов первоначальными являются буквы, связи, и натуральные операции. Символьные конструкции из букв и связей получаются уже средствами теории (поэтому в состав теории алгоритмов входит раздел о формальных языках). Понятие актуальной бесконечности ни явно, ни неявно не привлекается. Разночтения символьных конструкций тоже нет. Доматематическим их обоснованием является признание существования реального мира, абстрактными образами объектов и процессов которого являются символьные конструкции и алгоритмы. Применяемые языки поэтому наделены смыслом. Способность преобразовывать любую символьную конструкцию в слово не считается первоначальной и обеспечивается возможностью ограниченного применения произвольного выбора из конечного числа элементов (в процессе произвольной нумерации с последующим получением результатов всех возможных нумераций и выбора из них одного, лексикографически не старше всех других).

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