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

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

Хотя в этой главе собраны процедурные задачи занимательного характера, они позволят вам легко и приятно познакомиться со многими глубокими математическими понятиями. Например, первая задача позволит вам составить весьма ясное представление о том, что имеют ввиду математики, когда толкуют об изоморфизме двух, казалось бы, не связанных между собой задач: игра в 15, в которой так силен мистер Ярмар, оказывается структурно-изоморфной знаменитой игре в «крестики-нолики». В свою очередь эта весьма популярная игра изоморфна хитроумной игре в слова, изобретенной канадским математиком Лео Мозером, и еще одной игре на «дорожной сети». Все эти игры обладают стратегиями, основанными на использовании одного из наиболее древних комбинаторных курьезов — магического квадрата 3×3.

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

Теория графов занимается изучением различных множеств точек (вершин), соединенных линиями (ребрами). Многие практические задачи исследования операций допускают моделирование на графах. Некоторые из таких задач допускают изящные решения, например задача о построении минимального дерева, решаемая при помощи алгоритма Крускала. С задачей о минимальном дереве тесно связана еще одна задача — так называемая задача о дереве Штейнера. Общее решение ее пока не известно. Деревья Штейнера находят многочисленные приложения, поэтому специалисты по теории графов ведут весьма интенсивный поиск эффективных алгоритмов построения таких деревьев на ЭВМ.

Задача Штейнера принадлежит к числу так называемых NP-полных задач. Эти задачи неразрешимы в том смысле, что эффективные алгоритмы их решений не известны и, возможно, не существуют. Например, даже при использовании лучшего из известных алгоритмов построения дерева Штейнера для n точек время, затрачиваемое на решение, с увеличением n возрастает экспоненциально. Даже при сравнительно небольшом числе точек (порядка нескольких сотен) на построение дерева Штейнера лучшее решение может быть найдено… через несколько миллионов лет! Вот что значит экспоненциальный рост.

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

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