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