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

Да и говоря о наших современниках, таких как Билл Гейтс или Питер Нортон, вряд ли можно назвать их людьми, незнающими математики.

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

Давайте разработаем такой алгоритм, который будет лучше других, аналогичных по временным характеристикам. Давайте закодируем его так и на таком языке, чтобы он отбирал минимум ресурсов у системы (и не важно, какая это система: многопользовательский Unix или примитивный MSX-DOS образца 83-го года). Еще один бич программистов и пользователей – это не документированные или не устраненные ошибки. Имеет ли программист право сказать, что программа верна, после прогона всех тестов? Конечно, нет! Ошибки надо не отлаживать, а доказывать их отсутствие математически строго!

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

Книга, которую я держу в руках, была издана у нас в 1982 году, а написана Чарльзом Уэзереллом, сотрудником Калифорнийского университета, и того раньше – в 1978-м. Почти двадцать лет назад. Книга является библиографической редкостью: последний раз я видел ее в «Букинисте», что в Столешниковом переулке, пару лет назад. На ценнике стояло такое количество нулей, что желание купить книгу сразу пропало. Подумаешь, какие-то «Этюды для программиста». Но эта книга стоит тех нулей на ценнике, она стоит даже больше!

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

Я открываю книгу Уэзерелла...

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

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

Вообще, под графом в математике понимают упорядоченную пару <V, G>, где V – множество вершин, a G – множество дуг, их соединяющих. Множество дуг может быть пусто, а вот множество вершин должно содержать хотя бы один элемент. Если дуги у графа имеют направления, заданные стрелочками, то граф называют ориентированным, или орграфом. Если считать, что границы стран на нашей карте открыты в обе стороны, то ориентация (то есть направление обхода вершин) нам не понадобится.

Еще одно определение. Граф называется пленарным, если его можно расположить на плоскости так, чтобы его дуги не пересекались. С графами становится удобно работать, когда они представлены в виде матриц. Удобно это и с точки зрения математики (алгебра матриц хорошо известна любому студенту первого курса), и сточки зрения программирования. Для решения нашей задачи воспользуемся матрицей смежности. Матрица смежности для графа G -это квадратная матрица с числом строк (i) и столбцов (J), равным числу вершин графа. Элементы матрицы равны единице, если существует дуга, соединяющая вершины i и j, и равны нулю в противном случае. (В наших терминах наличие дуги означает наличие границы.)

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

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

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

Интерес к проблеме вызвал появление большого числа задач и формулировок, посредством которых многие математики, как профессионалы, так и любители, пытаются доказать гипотезу четырех красок. В начале 70-х годов нашего века удается доказать проблему для графа с 96 вершинами, чуть позже – и для большего числа вершин. В 1976 году коллективу математиков и программистов под руководством К. Аппеля и В.Хейкена удается доказать гипотезу Кэли, затратив на это около 2000 часов машинного времени. Однако в силу «нематематичности» доказательства и сложности чистых математических выкладок далеко не все специалисты теории графов считают гипотезу доказанной.

Простейший алгоритм правильной раскраски графов – следующий:

1. Произвольной вершине V, графа G припишем цвет 1.

2. Если вершины V,, V₂,..., V. раскрашены k цветами 1, 2.....k, где k < i+1, то новой произвольной вершине V._H припишем минимальный цвет, не использованный при раскраске вершин из ее окружения.

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

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

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

Программа требует тщательного обдумывания алгоритма, поскольку очень быстро, уже при 8-9 вершинах графа, происходит переполнение памяти. Для экономии памяти разумно использовать свойство симметричности матрицы смежности, что позволяет хранить не всю матрицу, а только ее часть. Можно предусмотреть случай, когда матрица смежности – разреженная, то есть число нулевых элементов в ней превышает число не нулевых (единиц) более чем в три раза. Обработка разреженных матриц требует написания специальных процедур, но в ряде случаев память и время расчета экономятся весьма существенно. А само дерево решений, которое получается при переборе, целиком размещать в памяти необязательно, достаточно хранить лишь обрабатываемую в данный момент ветвь. Проблема памяти возникает потому, что задача о раскраске графа – вообще говоря – экспоненциальной сложности, и время на счет (равно как и затраты памяти) при «честном» построении дерева перебора растет пропорционально показательной функции ЕХР(n).

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