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

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

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

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

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

Глава 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смесь применяется по назначению врача как докорм полутора -- двухмесячного ребенка.» Детское питание.-- М.: Госторгиздат, 1963, с. 107.

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

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

Подкармливают 3--4 раза в день после того, как щенки пососут мать, равными небольшими порциями, начиная с полстакана молока» Заводчиков П. А. и др. Справочная книга по собаковод-ству.-- М.: Сельхозиздат, 1960, с. 152.

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

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

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

Лимонный сок -- 8, сахар -- 14, желатин -- 3, кислота лимонная -- 0,1». Кулинария,-- М.: Госторгиздат, 1955, с. 626.

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

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

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

«Rp. Arpenali 0,05 D. t. d. N 20 in tabul S. По 1 таблетке З раза в день». Машковский М. Д. Лекарственные средства, т. 1,-- М.: Медицина, 1972, с. 200.

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

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

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

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

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

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

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5, 6