"Апология математики" - читать интересную книгу автора (Успенский Владимир)

Глава 6. Массовые задачи и алгоритмы

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

В замечательной одноактной пьесе «Урок» Эжена Ионеско есть такой диалог, который мы приведём с купюрами.

«Учитель. ‹…› Сколько будет, ну, скажем, если три миллиарда семьсот пятьдесят пять миллионов девятьсот девяносто восемь тысяч двести пятьдесят один умножить на пять миллиардов сто шестьдесят два миллиона триста три тысячи пятьсот восемь?

Ученица. Это будет девятнадцать квинтиллионов триста девяносто квадриллионов два триллиона восемьсот сорок четыре миллиарда двести

девятнадцать миллионов сто шестьдесят четыре тысячи пятьсот восемь

‹…›

Учитель (сосчитав в уме, с нарастающим изумлением). Да… Вы правы… ответ, действительно… (невнятно бормочет) квадриллионов… триллионов… миллиардов… миллионов… (разборчиво) сто шестьдесят четыре тысячи пятьсот восемь… (Ошеломленно.) Но каким образом вы это вычислили, если вам недоступны простейшие приемы арифметического мышления?

Ученица. Очень просто. Поскольку я не могу положиться на свое арифметическое мышление, я взяла и выучила наизусть все результаты умножения, какие только возможны».

Всех результатов умножения бесконечно много, так что выучить их наизусть невозможно. Да и не нужно: Ионеско справедливо утверждает, что «математика - заклятый враг зубрёжки». (Кстати, теоретическая невозможность выучить все результаты получила в приведённом диалоге и экспериментальное подтверждение. Дело в том, что Ученица дала неправильный ответ: правильным ответом является число 19 389 602 947 179 164 508, а ею названо число 19 390 002 844 219 164 508. Не берусь судить, получил ли этот факт должное отражение в ионесковедении.)

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

На примере с умножением можно получить представление о понятии массовая задача. Массовая задача образуется путём совместного рассмотрения серии однотипных единичных задач. В случае умножения каждая единичная задача состоит в указании пары конкретных чисел (как, например, тех, которые были названы Ученице Учителем) и требовании найти их произведение. Это произведение является решением предложенной единичной задачи. Массовая же задача состоит здесь в требовании найти некий метод, позволяюший найти произведение для каждой отдельной пары чисел. Другой простой пример. Задача решить квадратное уравнение x² - 13x+ 30 = 0 - это единичная задача, и её решением служит пара чисел 3 и 10. А вот изучаемая в средней школе задача о решении произвольного квадратного уравнения - это массовая задача, и её решением служит всем известная (или долженствующая быть всем известной) формула, дающая решение для любого конкретного квадратного уравнения. Остановим свой взгляд на какой-нибудь массовой задаче и посмотрим, чем отличаются друг от друга составляющие её единичные задачи. Мы видим, что они отличаются своими исходными данными. Для каждой единичной задачи умножения исходным данным служит конкретная пара чисел. А для каждой единичной задачи на решение квадратного уравнения исходное данное - это конкретное квадратное уравнение.

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

Само слово «алгоритм» достаточно интересно: это, возможно, единственный математический термин, имеющий в своей этимологии географическое название. Таким названием служит слово «Хорезм». Великий учёный Мухаммед бен Муса аль-Хорезмби жил в конце VIII - первой половине IX века. Арабское имя «аль-Хорезми» буквально означает ‘из Хорезма’. Аль-Хорезми предложил некоторые методы решения арифметических задач, и на его авторитет ссылались средневековые европейские авторы, писавшие, как это было принято, на латыни. При этом начиная с XII века его имя транслитерировалось как «Algoritmi». Отсюда и пошёл термин «алгоритм». Поиски общего метода для решения массовой задачи велись со времён античности. Однако впервые ясное понимание алгоритма в качестве самостоятельной сущности встречается лишь в 1912 году в трудах великого французского математика Эмиля Бореля.

Понятие алгоритма - одно из центральных в математике. Программа для компьютера есть не что иное, как запись какого-то алгоритма на компьютерном языке. Прорыв в осознании этого важнейшего понятия произошёл в 1936 году, когда независимо друг от друга Алонзо Чёрч в Америке и Алан Тьюринг в Англии предложили математические уточнения понятия алгоритма (каждый своё) и на основе этих уточнений предъявили первые примеры массовых проблем, неразрешимых алгоритмически, в числе которых оказалась и очень знаменитая, стоявшая с 1915 года так называемая «das Entscheidungsproblem» («проблема разрешения»), считавшаяся главной проблемой математической логики. Поясним, что термины «проблема» и «задача» для нас синонимы и что массовая проблема считается алгоритмически неразрешимой, если не существует решающего её алгоритма, то есть такого единого алгоритма, который позволял бы находить решение для каждой из тех единичных проблем, которые и составляют рассматриваемую массовую проблему.

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

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

Средствами игры будут служить пластинки, наподобие тех доминошек, что используются при игре в домино. Как и в домино, каждая пластинка разделена на верхнюю и нижнюю половину. В каждой половине что-то написано. Отличие от домино в том, чтбо именно написано. В случае домино в каждой из половин записывается количество очков, от 0 до 6. А нашем случае в каждой из половин записывается какая-то цепочка из букв икс и зет. Вот примеры таких цепочек. Цепочки длины один: x, z. Цепочки длины два: xx, xz, zx, zz. Цепочки длины три: xxx, xxz, xzx, xzz, zxx, zxz, zzx, zzz. Возможна и цепочка длины ноль, в этом случае не записано ничего. А вот одна из 128 цепочек длины семь: zxzxxxz. Проиллюстрируем сказанное примерами возможных пластинок:

Перечисленные 4 пластинки, в том порядке, как они указаны, обозначим - для дальнейших ссылок - буквами A, B, C, D. Если приложить одну пластинку к другой, но не торцами, как при игре в домино, а боками, то в результате получим две строчки букв: одну сверху, другую снизу. Так, прикладывая A к D (слева D, справа A), получаем zzzx сверху и zzx снизу. Если приложить в другом порядке, получим xzzz сверху, zxz снизу. Аналогично можно прикладывать друг к другу несколько пластинок и считывать верхнюю и нижнюю строчки букв. Более того. Каждую пластинку разрешается воспроизводить в неограниченном количестве и создавать сочетания из повторяющихся пластинок - такие, например, как AACA. В этом примере верхней строчкой будет xxxzx, а нижней - zxzxzzzx. Прошу у читателя прощение за затянувшееся предварение к игре, но хотелось бы, чтобы всё было предельно ясно.

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

Поясним сказанное на примерах. Пусть объявленный набор содержит всего только одну пластинку A из приведённого выше перечня. Ясно, что решение невозможно, поскольку, сколько раз ни прикладывай пластинку A саму к себе, нижняя строка всегда окажется длиннее верхней. По сходной причине решения не существует, если объявленный набор состоит из одной только пластинки D, только тут длиннее будет верхняя строка. Желающие могут попытаться доказать, что решения не существует и в том случае, когда объявленный набор состоит из двух пластинок, A и D. А вот если объявить набор из всех наших четырёх пластинок A, D, C и D, то решение существует. Действительно, если сложить пластинки в таком порядке: DBCDA, то и верхняя, и нижняя строка окажутся одинаковы: zzzxxzzzzx.

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