Code Reuse (повторное использование кода в ООП)

Все разработчики знают, что «Code reuse» — это Билет в Программистский Рай, Где Ничего Не Надо Писать Заново, и вообще ничего не надо писать, потому что всё уже есть. Любую программу в этом раю можно создать, совместив несколько готовых блоков.

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

Повторное использование кода (1) не обязывает к ООП и (2) не всегда ему сопутствует.

1. ООП — не единственный способ писать программы, и не единственный способ писать их хорошо. Изобретатель веб-приложений и байесовых спам-фильтров Пол Грэм утверждает, что повторное использование кода стимулируется программированием «снизу вверх», а «объектная ориентированность» не играет большой роли. Сам он никогда не прибегал к ООП. Хотя, это смотря что считать за ООП: при взгляде с нужной стороны и Lisp покажется более «объектно-ориентированным», чем Java.
2. Множество алгоритмов, реализованных в объектно-ориентированных программах, из года в год переписывается заново. Тому есть множество разнообразных причин. Выходит, что жить по идеологии «Code Reuse» сложно; легче оступиться и потерять вожделенный рай. Создатель XEmacs Ричард Гэбриэл считал трудность повторного использования кода одним из признаков провала парадигмы ООП.

Но сейчас речь идёт об ООП, а именно — о средствах компоновки и расширения классов (и не только) для создания новых классов.

Композиция — это объединение объектов, которые общаются между собой с помощью только внешних интерфейсов (black box reuse). Друг для друга объекты являются «чёрными ящиками».

Гибкость композиции объектов обеспечивает делегирование — передача ответственности за выполнение метода связанному объекту. Есть две разновидности делегирования:

• Методы-заглушки, явно передающие вызов связанному объекту. Они делаются более или менее одинаково во всех языках программирования. При необходимости создать «пачку» заглушек, делегирующих все методы, поддерживаемые связанным объектом, в статических языках не обойтись без автоматической генерации кода. В Smalltalk такую делегацию можно осуществить, перегрузив в объекте стандартную заглушку для несуществующих методов под названием doesNotUnderstand:. Аналогичные механизмы имеются в Python и Ruby. В COM тоже имеется механизм агрегации (aggregation) для автоматического делегирования группы методов.

• Методы-делегаты, передаваемые из связанного объекта в главный. Связанный объект при этом, как правило, не принадлежит главному, а существует сам по себе (с заглушками ситуация обратная). Можно даже сказать, что главный объект является вспомогательным для связанного. К примеру, в библиотеках GUI объекты с помощью делегатов «подписываются» на события оконной среды. В Smalltalk, Ruby и Scala стандартные контейнеры самостоятельно осуществляют процедуры типа перебора элементов; объект, которому нужно перебрать элементы контейнера, передаёт ему делегат.

  Разумеется, при передаче делегата должна сохраняться привязка к свободным переменным в первоначальном контексте метода (в т.ч. переменных-членов его класса), иначе это не делегат, а просто указатель на функцию. По сути, процедура, сохраняющая привязку к свободным переменным в своём лексическом контексте, является замыканием (closure). Подразумевается, что процедура не обязана иметь имени. Замыкания в той или иной форме поддерживаются в почти во всех ОО-языках: в C# с версии 2.0 есть специальная конструкция под названием «анонимный метод» (anonymous method), в языке D тоже есть делегаты, в Java делегатов нет, но есть возможность получить аналогичный эффект с помощью механизма Reflection, или с помощью внутреннего класса (inner class). Последний вариант работает даже в C++, но там класс не может быть анонимным, то есть любой сколь угодно мелкий делегат должен иметь имя.

  Наиболее элегантная запись замыканий имеет место в языках с динамической типизацией — Smalltalk (в нём любой блок кода в [] — замыкание), Lisp (лямбда-выражения), Javascript, Lua, Ruby. Хотя, в статически типизированном языкеScala тоже удобная запись, и в грядущем C# 3.0 будет похожая. Урезанные лямбда-выражения есть в Python, но в будущем они исчезнут; останутся именованные вложенные функции.

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

Наследование (inheritance, white box reuse) — это формирование подкласса, который имеет доступ ко всем данным и методам родительского класса и может перегружать методы. О «чёрном ящике», как при композиции, речи нет.

Наследование часто считают одним из основных принципов ООП (инкапсуляция-полиморфизм-наследование). Это так, но лишь в рамках языка Simula, созданного Кристеном Нигардом в 1960-х годах, идеи которого использовались позже в C++, Java и C#. Невозможно представить эти языки без наследования, но оно в них столь востребовано не от хорошей жизни: из-за синтаксических ограничений этих языков наследование с перегрузкой виртуальных методов широко используется для передачи вызовов, а в C++ и делегатов без наследования не сделать. Иными словами, наследование используется как вспомогательное средство для делегирования.

На более богатой модели Алана Кея (объекты-сообщения), реализованной в Smalltalk в 1970-х годах, очевидно, что наследование — это удобный механизм для повторного использования кода, и ничего более. Инкапсуляция и полиморфизм в этой модели ООП предполагаются абсолютными, а наследование (и даже классы) не обязательны вовсе. Есть группа т.н. прототипных (prototype-based) ОО-языков, в которых нет классов. К этой группе относятся Self, Io, Lua и JavaScript (до выхода ECMAScript 4/JavaScript 2.0).

Наследование, к тому же, (a) нарушает принцип инкапсуляции, т.к. родительский класс открывает свои данные подклассу, и (b) действует без гибкости, «раз и навсегда»: после создания объекта наследованного класса его базовый класс уже не изменить. В известной книге «Банды четырёх» даётся совет предпочитать композицию наследованию. Создатель Java Джеймс Гослинг также признался, что считает наследование не лучшей техникой. (Впрочем, второй из указанных пороков присущ также и всем приёмам, изложенным далее.)

При одиночном наследовании (single inheritance) у класса может быть только один «родитель». Стандартная библиотека классов и вся среда разработки Smalltalk были написаны на Smalltalk с применением только одиночного наследования. Из этого можно сделать вывод, что одиночного наследования (вкупе с делегатами-замыканиями) в принципе достаточно для создания программных комплексов любого размера; ограниченные возможности по повторному использованию кода искупаются простотой объектной модели.

Множественное наследование (multiple inheritance) является плодом естественного стремления «повторно использовать» не один класс, а сразу несколько. Этот вид наследования реализуют языки C++, CLOS (объектная надстройка над Common Lisp) и Python.

На фоне очевидных преимуществ проступает ряд недостатков:

• В перегруженном методе нельзя просто вызвать-метод-суперкласса, потому что суперкласс неоднозначен. В C++ требуется явно прописывать суперкласс, к которому производится обращение, что делает код метода зависимым от названия суперкласса, и, следовательно, от общей иерархии классов. В Python и CLOS можно, не зная имени, обратиться к «ближайшему по порядку» суперклассу. Порядок определяется автоматически по неким правилам. Эти правила опять же делают код уязвимым к иерархии и к порядку перечисления суперклассов при объявлении, что иногда приводит к неожиданным эффектам.
• «Проблема ромба» (diamond problem) возникает, когда у класса D два базовых класса B и C в свою очередь наследуются от одного базового для них класса A. C++ — единственный язык, который в такой ситуации позволит существовать двум объектам класса A. При вызове из D метода, описанного в A, возникнет конфликт методов: непонятно, какому из объектов класса A передать вызов. Конфликт разрешается, как и в предыдущем пункте, явным указанием родительского класса (B или C). В остальных языках (и в C++ при т.н. виртуальном наследовании) объект класса A будет существовать в одном экземпляре. В этом случае возникает конфликт состояний — вещь более серьёзная, чем конфликт методов. Объекты классов B и C «не знают» о том, что объект класса A у них общий; для объекта класса B всё выглядит так, будто данные его суперкласса самопроизвольно меняются. Стандартного решения у этой проблемы нет.

Параметризованные классы — это классы, определение которых содержит неспецифицированные классы. Последние задаются в качестве параметров при непосредственном использовании параметризованного класса. Этот подход называется «обобщённым программированием» (generic programming), и успешно применяется в тандеме с ООП, а именно в C++, D, и Scala. В C# с версии 2.0 и и в Java с версии 1.5 есть т.н. группы (generics), внешне похожие на параметризованные классы. Группы предназначены не для создания новых классов, и вообще не для «code reuse», а для усиления контроля типов. Стандартные коллекции в C# и Java хранят объекты базового класса object. Группы позволяют программисту «убедить» компилятор в том, что в конкретной коллекции хранятся объекты более конкретного класса, чем object.

В динамически типизированных ОО-языках обобщённое программирование теряет смысл: все классы в них и так параметризованы настолько, что никогда не требуют конкретизировать классы используемых объектов на стадии компиляции. Иными словами, параметризованные классы — это издержки контроля типов, целесобразность которого является предметом многолетней «holy war».

Шаблоны C++ и D заслуживают отдельного рассмотрения тем, что дают компилятору возможность сразу выдавать эффективный машинный код. Преждевременная оптимизация (корень всех зол) в C++ дошла до того, что шаблоны являются полным по Тьюрингу «языком в языке», на котором можно написать любую программу, например процедуру вычисления чисел Фибоначчи или игру «Жизнь». В языке D шаблоны также являются отдельным языком, но совпадают с D по синтаксису.

Скомпилированный программный код не содержит шаблонов. Обычные конструкции C++ вроде if() в языке шаблонов недоступны, но в них конечно можно сделать свой if(). При этом шаблоны не могут польностью заместить основной язык, и дело здесь даже не в наличии входных данных, неизвестных компилятору. Тьюринг доказал, что не существует алгоритма, предсказывающего, закончится ли произвольная программа или будет работать вечно. Из этого следует, что возможности компилятора по обнаружению ошибок в коде ограничены. Программы надо запускать, а не только компилировать из шаблонов.

Безотносительно проблем статически типизированных языков, композиция и наследование имеют один принципиальный изъян, состоящий в использовании класса как единицы «code reuse», тогда как класс является в первую очередь генератором объектов. Объекты должны быть большими, а единицы повторно используемого кода — маленькими; чтобы разрешить это противоречие, имеет смысл завести отдельные сущности, предназначенные сугубо для повторного использования.

Примесь (mixin) — как раз такая сущность. Примесь представляет собой набор данных и методов, который можно «подмешать» к какому-либо классу. Сама по себе примесь не может служить генератором объектов; в методах примеси могут использоваться данные и другие методы, отсутствующие в ней (соответственно, они должны присутствовать в классе, к которому добавляется примесь). Использование примесей, как и наследование, нарушает инкапсуляцию.

По аналогии с «абстрактным суперклассом», от которого необходимо наследоваться, примесь можно считать абстрактным подклассом, который необходимо отнаследовать от какого-либо суперкласса. Такой подход позволяет удобно совместить новую концепцию с классическим наследованием. Примеси реализованы в Ruby и Scala. В Python и C++ примеси доступны как частный случай множественного наследования. В CLOS примеси есть, но их отличие от классов чисто условное и состоит в вызове call-next-method при отсутствии суперклассов.

Разумеется, в класс можно добавлять и более одной примеси. Что касается «проблемы ромба» при множественном «подмешивании»: в Ruby, если «подмешиваемые» модули включают другие модули, ромбовидная диаграмма примесей может возникнуть, с последующим конфликтом состояния. В Python и C++ здесь та же ситуация, что и с множественным наследованием, а в Scala ромбовидные иерархии примесей попросту запрещены.

В CLOS в каждом классе древовидная иерархия его суперклассов (и примесей) принудительно раскладывается в линию. Это устраняет «проблему ромба», но создаёт другую, не менее серьёзную: когда в класс добавляется несколько примесей, они идут не все сразу, а по очереди. Каждая следующая примесь наследуется от совокупности класса и предыдущих примесей. Это означает, что:

• Метод, определённый в примеси A, может быть «тихонько» перегружен примесью B. А при другом порядке добавления примесей может быть и наоборот — метод из B перегружен в A. В условиях «повторного использования» примесей во многих классах одновременно легко столкнуться с ситуацией, когда любой порядок «примешивания» вызывает ошибки.
• Из подкласса нельзя получить доступ к методам его суперкласса, которые были перегружены в примесях. Это практически уничтожает возможность аккуратного разрешения конфликтов имён «в последней инстанции», т.е. в подклассе.

Штрих (trait) — это абстрактный подкласс без переменных, то есть примесь, не имеющая состояния, или, по словам авторов, «единица поведения». Штрих имеет доступ к методам класса, но не к его данным. Как и примеси, штрихи могут наследоваться.

Запрет на доступ к данным класса восстанавливает инкапсуляцию, а запрет на состояние убирает разом все проблемы с конфликтами имён переменных и с конфликтами состояний при ромбовидном наследовании. Конфликты имён методов в штрихах обязаны разрешаться явно с помощью (a) переименования методов в наследованном классе или штрихе и (b) явного переопределения конфликтующего метода в наследованном классе или штрихе. Порядок наследования штриховне имеет значения.

Штрихи были впервые реализованы в диалекте Smalltalk под названием Squeak. Они присутствуют в Scala, а в C++ и Python их можно, как и примеси, реализовать через множественное наследование. Вероятно, штрихи появятся как особый элемент языка и в Python 3000.

В завершение — небольшая сводная таблица.

Средство	Время появления	Ограничения	Преимущества	Неудобства	Языки
Композиция	1960-е годы (Simula)	Соблюдается инкапсуляция.	Наибольшая гибкость в процессе выполнения.	Много «промежуточного» кода.	Все.
Одиночное наследование	1960-е годы (Simula)	Одиночное.	Простая объектная модель.		Все, кроме прототипных.
Множественное наследование	1980-е годы (C++)		Наибольшие возможности при проектировании.	Неоднозначность суперкласса; проблема ромба.	CLOS, C++, Python.
Параметризованные классы	1980-е годы (Ada)		Эффективная компиляция.	Синтаксические излишества.	C++, D, Scala.
Примеси	1990	В Scala запрещена ромбовидная иерархия.		Проблема ромба (кроме Scala и CLOS). Очерёдность наследования в CLOS.	CLOS, C++, Python, Ruby, Scala.
Штрихи	2002	Нет состояния; соблюдается инкапсуляция.	Не нужно следить за порядком наследования.		Squeak, C++, Python, Scala.

Теория графов (фрагменты реферата по истории науки)

[в основном по книгам «Handbook of Graph Theory»¹² и «Graph Theory 1736-1936»²⁷]

Теория, выросшая из игр

Годом зарождения теории графов можно считать 1736-й, когда швейцарский математик Леонард Эйлер опубликовал в Санкт-Петербургской Академии наук работу¹, посвящённую семи мостам города Кёнигсберга (нынешний Калининград). Загадка о том, как пройти по всем мостам ровно однажды, была известна горожанам с тех пор, как все семь мостов были построены, т.е. с XVI века; математик же разработал её формализацию и доказал, что она не имеет решения. Путь, проходящий через все рёбра графа по одному разу, в современной литературе называется эйлеровым путём.

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

Как ни странно, до конца XIX века никто не отметил аналогии задачи о мостах Кёнигсберга с чертёжными головоломками. Впервые это сделал британский математик и юрист Вальтер Уильям Рузе Болл в 1892 году⁴.

С зарождением теории графов связана ещё одна древняя задача — о шахматном коне, который должен пройти через все клетки доски, не побывав на ни на одной дважды. Эта задача, строго говоря, старше шахмат: впервые она упомянута в книге «Китаб Аш-Шатрандж» Абу Бакра Мухаммада ас-Сули, знаменитого игрока в шатрандж, жившего в Арабском (Багдадском) халифате в IX веке. Шатрандж — игра, предшествующая шахматам; ход конём в шатрандже был таким же, как в шахматах. В книге ас-Сули приведены два решения этой задачи (вообще же их триллионы).

Первая публикация⁵, излагающая систематический подход к поиску решений задачи о шахматном коне принадлежала перу Эйлера и увидела свет в 1766 году. Автор привёл в ней способы получения новых решений из уже имеющихся, при этом уделив внимание симметрии пути коня.

Французский скрипач, химик и математик Александр-Теофил Вандермонд в 1771 году продолжил⁶ формализацию Эйлера, освободив её от привязки к шахматной доске как геометрическому объекту, то есть перейдя от количественных характеристик (длин и углов) к качественным (относительному расположению объектов). Этот принцип собственно обозначил отделение теории графов от геометрии и позже лёг в основу другой науки — топологии. Её название было введено немецким математиком Иоганном Листингом в работе⁷ 1847 года, посвящённой эйлеровым путям.

Между задачами о мостах Кёнигсберга и шахматном коне есть принципиальное различие: в первой требуется единожды обойти все рёбра графа, тогда как во второй требуется единожды посетить все вершины. Благодаря этому различию, исследования разных аспектов новой теории долгое время протекали независимо друг от друга.

Вариант второй задачи, заключённый в настольной игре «Икосиан» (Icosian Game), увидел свет в 1857 году по воле сэра Вильяма Гамильтона, ирландского математика, физика и астронома. В основе этой игры лежал процесс поиска замкнутого пути, проходящего через каждую вершину додекаэдра ровно один раз. Автор вывел из своей игры новую алгебраическую структуру⁸, а термин «гамильтонов цикл» стал общепринятым в математике для обозначения замкнутого пути, проходящего через все вершины графа по одному разу.

Независимо от Гамильтона исследования на ту же тему вёл британский математик Томас Киркман. Он обозначил класс многогранников, на которых вышеуказанная задача неразрешима⁹.

Гамильтоновым графам (графам, в которых есть гамильтонов цикл) было посвящено немало исследований и в XX веке^{10 11}. Также с гамильтоновыми графами связана знаменитая «задача коммивояжёра» (travelling salesman problem). Первое упоминание о ней, по косвенным данным, относится к 1831 году. Задача коммивояжёра заключается в том, чтобы обойти все города по одному разу, пройдя минимальное расстояние. Иными словами, это задача поиска минимального гамильтонова цикла. В 1930-х годах она была поставлена и изучена австрийским математиком Карлом Менгером, а позже математиками Принстонского университета Хаслером Уитни и Мериллом Флудом¹². Это одна из так называемых NP-трудных задач¹³. На ней часто производят «обкатку» новых подходов к эвристическому сокращению комбинаторного перебора.

Датой окончательным становления теории графов как самостоятельной математической отрасли можно считать 1936 год, когда венгерский математик Денешем Кёниг написал первую в своём роде монографию "Теория конечных и бесконечных графов«¹⁴.

Деревья

Дерево — связный граф без циклов. Исследования деревьев, в отличие от общей теории графов, с самого начала велись в применении к наукам, а не играм.

Термин (вероятнее всего, позаимствованный из сочетания «фамильное древо») и само понятие ввёл в обращение немецкий физик Густав Кирхгоф. Его публикация 1847 года¹⁵, посвящённая электрическим цепям, внесла огромный вклад в теорию. Автор использовал два правила (ныне известные как «правила Кирхгофа») для составления системы уравнений токов и напряжений в цепи. С целью сокращения количества циклов, участвующих в уравнениях, он предложил концепцию остовного дерева, по которым можно определить набор фундаментальных циклов. В той же работе впервые появляется матрица инциденций — один из ключевых объектов в нынешних компьютерных системах, имеющих дело с графами.

Английский математик Джеймс Сильвестр использовал деревья для описания алгебраических дифференциальных операторов в 1854 году. В его работе¹⁶ появилось определение дерева с выделенным корнем, и соответственно ветвей и листьев такого дерева.

Работа Сильвестра привлекла внимание его друга, математика Артура Кейли, и тот занялся задачей определения количества различных деревьев с выделенным корнем и заданным числом вершин. Свой результат он опубликовал в 1857 году¹⁷. В дальнейшем Кейли делал аналогичные подсчёты для отдельных классов деревьев¹⁸.

В начале 1850-х годов химики разных стран независимо друг от друга определили наличие у химических элементов свойство валентности, благодаря которому образуются химические соединения. Шотландский химик Александр Браун в 1864 году первым предложил¹⁹ использовать «графическую» нотацию для рисования молекул, которая быстро получила распространение и является сегодня общепринятой.

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

Большая часть химических соединений, известных в то время, не содержала циклов, т.е. молекулы являлись деревьями. Кейли, вдохновлённый этим фактом, в 1874 году опубликовал работу²⁰ по перечислению всех изомеров с заданной химической формулой. У молекул нет выделенного корня; перейти на анализ деревьев без корня Кейли помогла публикация²¹ французского математика Камиля Жордана 1869-го года, в которой содержалась формализация изоморфизма и автоморфизма деревьев, а также было введено понятие центра дерева.

У деревьев химических соединений есть ещё одна особенность: их вершины не всегда эквивалентны друг другу, т.к. они имеют метки (atom labels), обозначающие химические элементы. Это обстоятельство породило интерес к перечислению помеченных, а не абстрактных, деревьев. Кейли опубликовал соответствующий результат²² в 1889 году. Тот же результат более аккуратно получил немецкий математик Хейнц Прюфер в 1918 году²³.

Методы перебора изомеров, изложенные Кейли, были неудобны на практике и поэтому не получили признания у химиков. Недостатки методов Кейли были устранены в работе венгерско-швейцарско-американского математика Пойа²⁴ 1935 года.

Сильвестр и другой английский математик, Вильям Клиффорд, в 1878 году предприняли попытку разработать «химико-алгебраическую» теорию, сопоставив атомам алгебраические формы^{25 26}. Теория оказалась несостоятельной, но сама по себе попытка рассматривать графы как независимые объекты «на стыке» двух наук, заслуживает одобрения. Кроме того, в работе Сильвестра впервые появилось слово «граф», прижившееся в научном мире. Сильвестр и Клиффорд, осознав ошибки своей теории, позже пытались ненавязчиво «приписать» её изобретение друг другу²⁷.

Проблема четырёх красок

В 1852 году студент Лондонского Университетского Колледжа Фрэнсис Гутри (Francis Guthrie), составляя карту графств Англии, обнаружил, что для раскраски карты таким образом, чтобы соседние графства имели разные цвета, достаточно четырех красок. Он поделился находкой со своим братом Фредериком (Frederick Guthrie), а тот — с профессором математики Огастесом де Морганом (Augustus de Morgan), от которого о новой гипотезе узнал остальной математический мир. Точную формулировку опубликовал Кейли в 1879 году²⁸.

Гипотеза имела непосредственное отношение к планарным графам — графам, которые можно нарисовать на плоскости так, чтобы рёбра не пересекались. Первое доказательство, опубликованное в том же году лондонским математиком Альфредом Кемпе²⁹, содержало ошибку, найденную в 1890 году британским математиком Перси Хивудом³⁰, который, однако, доказал верность гипотезы для пяти красок.

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

В начале XX века родились идеи, составившие основу успешного подхода к доказательству гипотезы: немецкий тополог Вернике в 1904 году составил³¹ список т.н. «неизбежных» фрагментов, один из которых присутствует в любой карте. В 1912 году американский математик Дэвид Биркхоф ввёл³² понятие хроматического полинома — числа возможных раскрасок графа заданным количеством цветов, а в 1913 году начал исследование т.н. «сокращаемых» фрагментов карты, обладающих таким свойством, что ни один из них не может появиться в контрпримере к гипотезе о четырёх красках³³. Работа Биркхофа позволила американскому математику Филипу Франклину в 1922 году доказать гипотезу для карт, содержащих не больше 25 стран³⁴.

В 1976 году окончательное доказательство³⁵ было получено профессорами Университета Иллинойса в Урбанэ-Шампейн (UIUC) Вольфгангом Хакеном и Кеннетом Аппелем. Оно всколыхнуло математический мир: впервые для доказательства теоремы использовался компьютер. Более того, только компьютер мог проверить это доказательство: оно состояло из 50 страниц текста и диаграмм, 85 страниц с почти 2500 дополнительными диаграммами, 400 страниц микрофишей, содержащих еще диаграммы, а также тысяч отдельных проверок утверждений, сделанных в 24 леммах основного текста ³⁶.

Доказательство, не поддающееся проверке — нонсенс; опора на вычислительные машины грозит упразднить математику как таковую, переведя её в раздел экспериментальных наук³⁷. На проверку исчерпывающего набора из 1482 сокращаемых фрагментов, перечисленных в доказательстве, ушло 1200 часов машинного времени.

Предпринимались и до сих пор предпринимаются попытки упростить доказательство настолько, чтобы сделать его доступным человеку. В 1994 году четыре американских математика Робертсон, Сандерс, Сеймур и Томас снизили количество число сокращаемых фрагментов до 633³⁸. Их доказательство заслуживает особого внимания тем, что рассматривает задачу, переформулированную в терминах линейной алгебры. Вообще известно более 20 её формулировок, связанных с задачами алгебры, статистической механики и задачами планирования³⁷. В современной теории графов раздел «раскраски» занимает немалую часть и имеет множество приложений в упомянутых областях. Задача определения хроматического числа графа (минимального числа цветов, в которые граф можно раскрасить) и задача «3-раскрашиваемости» планарных графов являются классическими NP-полными задачами¹³.

Прорыв в смысле «человеческого» доказательства был сделан в 2004 году: Джордж Гонтье из исследовательской лаборатории компании Microsoft в Кембридже и Бенджамин Вернер из французского института INRIA перевели программный код доказательства на язык абстрактной логики "Coq«³⁹, и создали интерактивную программу, «помогающую» человеку строить доказательства логических утверждений. Теорема о четырёх красках была таким образом успешно доказана.

Сети и потоки

Сеть — направленный граф с числовыми характеристиками рёбер (дуг), обозначающими пропускную способность. Теория сетей обязана своим возникновением росту промышленности в XX веке и сопутствующей ему проблемы оптимальной доставки грузов по каналам с ограниченной пропускной способностью. Поток в сети соответствует движению грузов по составленным из дуг маршрутам, от определённой точки-источника к точке стока.

Первая работа, касающаяся этой темы, была опубликована в СССР в 1930 году⁴⁰. Наряду с несколькими подходами к решению задачи, в ней было замечено необходимое условие оптимальности потока: остаточный граф потока не должен содержать циклов отрицательной стоимости; однако, обоснования достаточности этого условия приведено не было. Его опубликовал Леонид Канторович в 1942 году⁴¹.

Советская железнодорожная сеть привлекала внимание США в двух аспектах: до Второй мировой войны как пример для подражания, а после, с началом Холодной войны — как стратегический объект потенциального противника, подлежащий уничтожению в случае конфликта⁴². Задача уничтожения транспортного потока в случае войны требует не меньшей эффективности, чем его функционирование в мирное время. Формализация этой задачи содержит понятие разреза — множества дуг между двумя подмножествами исходного множества вершин.

Решения двух задач совпадают: в 1954 году в американской корпорации RAND математики Лестер Форд и Делберт Фалкерсон доказали⁴³, что значение максимального потока в сети равняется значению минимального разреза. Позднее авторы сослались на засекреченную статью⁴⁴ Гарриса и Росса 1955 года, в которой прямо поднимался вопрос эффективного воздушного удара по железнодорожной сети советского блока.

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

В 1970 году советским учёным Ефимом Диницем был изобретён⁴⁵ более эффективный по времени вариант алгоритма Форда-Фалкерсона. Тот же алгоритм был независимо получен⁴⁶ в 1972 году Джеком Эдмондсом и Ричардом Карпом. Ещё более быстрый алгоритм, получивший название «проталкивания предпотока» (push-relabel) был предложен в 1985 году Голдбергом⁴⁷, и ещё один под названием «поднять-и-в-начало» (relabel-to-front) опубликовали⁴⁸ в 2001 году профессора института MIT Кормен, Лейзерсон и Ривест.

Помимо задачи о максимальном потоке, в теории сетей существуют более сложные, например задача о многопродуктовом потоке, в которой требуется оптимизировать суммарный поток в сети, обладающей рядом пропускных характеристик, заданных в отдельности для каждого продукта. Эта задача в целочисленном варианте является NP-полной⁴⁹.

Литература

[1] Leonhard Euler. Solutio problematis ad geometriam situs pertinentis. Commentarii Academiae Scientiarum Imperialis Petropolitanae. 1736, 8, 128-140.
[2] Simon Antoine Jean Lhuilier. Eléments raisonnés d’algebre. Genève, 1804.
[3] Louis Poinsot. Mémoire sur les polygones et polyedres. J. de l’École Polytechnique. 1810, 9, 16-48.
[4] Walter William Rouse Ball. Mathematical recreations and Problems of Past and Present Times. Macmillan: London, 1892.
[5] Leonhard Euler. Solution d’une question curieuse qui ne paroit soumise a aucune analyse. Mémoires de l’Académie Royale des Sciences et Belles Lettres de Berlin, Anné 1759. 1766, 15, 310-337.
[6] Alexandre-Théophile Vandermonde. Remarques sur des problèmes de situation. Mémoires de l’Académie Royale des Sciences, Paris. 1771, 566-574.
[7] Johann Benedict Listing. Vorstudien zur Topologie. Vandenhoeck und Ruprecht: Göttingen, 1847.
[8] William Rowan Hamilton. Account of the Icosian Calculus. Proceedings of the Royal Irish Academy. 1858, 6, 415-416.
[9] Thomas Penyngton Kirkman. On the Representation of Polyhedra. Proceedings of the Royal Society of London. 1854-1855, 7, 543-544.
[10] Gabriel Andrew Dirac. Some theorems on abstract graphs. Proc. London Math. Soc (3). 1952, 2, 69-81.
[11] Øystein Ore. A Note on Hamiltonian circuits. Amer. Math Monthly. 1960, 67, 55.
[12] Jonathan L. Gross, Jay Yellen. Handbook of Graph Theory. CRC Press, 2004.
[13] Michael R. Garey, David Stifler Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman: San-Francisco, 1979.
[14] Dénes Kőnig. Theorie der endlichen und unendlichen Graphen: Kombinatorische Topologie der Streckenkomplexe. Akad. Verlag M.B.H.: Leipzig, 1936.
[15] Gustav Kirchhoff. Über die Auflösung der Gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanischer Ströme geführt wird. Ann. Phys. Chem. 1847, 72, 497-508.
[16] James Joseph Sylvester. On Differential Transformation and the Reversion of Serieses. Proceedings of the Royal Society of London. 1854-1855, 7, 219-223.
[17] Arthur Cayley. On the theory of the analytical forms called trees. Philosophical Magazine (4). 1857, 13, 172-176.
[18] Arthur Cayley. On the analytical forms called trees — Part II. Philosophical Magazine (4). 1859, 18, 374-378.
[19] Alexander Crum Brown. On the theory of isomeric compounds. Transaction of the Royal Society Edinburgh. 1864, 23, 707-719.
[20] Arthur Cayley. On the mathematical theory of isomers. Philosophical Magazine (4). 1874, 47, 444-446.
[21] Camille Jordan. Sur les assemblages des lignes. J. Reine Angew. Math. 1869, 70, 185-190.
[22] Arthur Cayley. A theorem on trees. Quart. J. Math. 1889, 23, 376-378.
[23] Heinz Prüfer. Neuer Beweis eines Satzes über Permutationen. Arch. Math. Phys. 1918, 27, 742-744.
[24] Pólya György. Un problème combinatoire général sur les groupes de permutations et le calcul du nombre des isomères des composés organiques. Comptes Rendus Hebdomadaires des Séances de l’Académie des sciences. 1935, 201, 1167-1169.
[25] James Joseph Sylvester. On an Application of the New Atomic Theory to the Graphical Representation of the Invariants and Covariants of Binary Quantics, With Three Appendices. American Journal of Mathematics, Vol. 1. 1878, 2, 105-125.
[26] William Kingdon Clifford. Notes on Quantics of Alternate Numbers, used as a means for determining the Invariants and Covariants of Quantics in general. Proc. London. Math. Soc. 1878-1879, 10, 124-129.
[27] Edward Keith Lloyd, Norman Biggs, Robin James Wilson. Graph Theory 1736-1936. Oxford University Press, 1986.
[28] Arthur Cayley. On the Colouring of Maps. Proceedings of the Royal Geographical Society and Monthly Record of Geography (1). 1879, 4, 259-261.
[29] Alfred Bray Kempe. On the Geographical Problem of the Four Colours. American Journal of Mathematics. 1879, 2, 193-200.
[30] Percy John Heawood. Map-colour Theorem. Quarterly Journal of Pure and Applied Mathematics. 1890, 24, 332-338.
[31] Paul August Ludwig Wernicke. Über den kartographischen Vierfarbensatz. Math. Ann. 1904, 58, 413-426.
[32] George David Birkhoff. A determinantal formula for the number of ways of coloring a map. Ann. Math. 1912, 14, 42-46.
[33] George David Birkhoff. The Reducibility of Maps. American Journal of Mathematics (35). 1913, 2, 115-128.
[34] Philip Franklin. The four color problem. American Journal of Mathematics. 1922, 44, 115-128.
[35] Kenneth Appel, Wolfgang Haken. Every Planar Map Is Four Colorable. Illinois J. Math. 1977, 21, 429-567.
[36] Kenneth Appel, Wolfgang Haken. The four color proof suffices. The Mathematical Intelligencer 8. 1986, 1, 11.
[37] Алексей Васильевич Самохин. Проблема четырех красок: неоконченная история доказательства. Соросовский образовательный журнал. 2000, 7, 91-96.
[38] Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas. The four colour theorem. J. Combin. Theory Ser. B. 1997, 70, 2-44.
[39] http://coq.inria.fr
[40] А. Н. Толстой. Методы нахождения наименьшего суммового километража при планировании перевозок в пространстве. Планирование перевозок, Транспечать НКПС. 1930, 1, 23-55.
[41] Леонид Витальевич Канторович. О перемещении масс. Доклады Академии Наук СССР. 1942, 37, 227-230.
[42] Alexander Schrijver. On the history of the transportation and maximum flow problems. Mathematical Programming (91). 2002, 3, 437-445.
[43] Lester Randolph Ford Jr, Delbert Ray Fulkerson. Maximal flow through a network. Research Memorandum RM-1400. The RAND Corporation: Santa Monica, California, 1954.
[44] T.E. Harris, F.S. Ross. Fundamentals of a Method for Evaluating Rail Net Capacities. Research Memorandum RM-1573. The RAND Corporation: Santa Monica, California, 1955.
[45] E. A. Dinic. Algorithm for Solution of a Problem of Maximum Flow in Networks with Power Estimation. Soviet Math. Dokl. 1970, 11, 1277-1280.
[46] Jack Edmonds, Richard Manning Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM (2). 1972, 19, 248-264.
[47] Andrew V. Goldberg. A New Max-Flow Algorithm. Technical Report TM-291. Laboratory for Computer Science, M.I.T, 1985.
[48] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest. Introduction to Algorithms. MIT Press, 1990.
[49] S. Even, A. Itai, A. Shamir. On the Complexity of Timetable and Multicommodity Flow Problems. Society for Industrial and Applied Mathematics (5). 1976, 4, 691-703.