Традиционные задачи по комбинаторике всегда выглядели немного несерьезно, как будто из книжки «Математики шутят». Еще несколько десятилетий назад никто бы не поверил, что решения этих смешных задачек заложат основы информатики и сделаются совершенно прикладными. О некоторых удивительных фактах, связанных с историей комбинаторики, рассказывает директор Физтех-школы прикладной математики и информатики МФТИ Андрей Райгородский.
В МФТИ сейчас работают две лаборатории по комбинаторике. Одну из них я имею честь возглавлять. Мы работаем в основном в области экстремальной комбинаторики, но занимаемся и другими направлениями: случайные графы, случайные гиперграфы, дискретная геометрия, комбинаторная геометрия, комбинаторика слов. Представлены у нас алгебраическая комбинаторика, аналитическая комбинаторика, — словом, практически все области, которые сейчас актуальны в этой науке. В нашей лаборатории работают одни из лучших в мире специалистов в этих областях, а также постоянно приезжающие к нам иностранные корифеи.
Вставайте, граф
Сегодня комбинаторика — одна из самых бурно развивающихся дисциплин в мировой науке. Хотя всего полсотни лет назад ее считали, в основном, забавой для математически продвинутых школьников. Но с наступлением компьютерной эры вдруг выяснилось, что в информатике, теории алгоритмов, прикладном программировании нет ничего важнее комбинаторики. В частности, комбинаторные задачи играют огромную роль при оптимизации многих базовых алгоритмов.
Вот, например, хорошо известно, что при моделировании работы самых разнообразных систем огромную помощь оказывают известные любому студенту графы. Самым интересным, на мой взгляд, примером этого может служить то, чем я занимался еще в Яндексе и продолжаю на Физтехе, — описание с помощью графов различных моделей, которые позволяют работать с реальными объектами. Например, такую сущность, как интернет можно запросто интерпретировать как граф.
Вообще, что такое граф? Это некая структура, у которой есть вершины и ребра. Вершины — это объекты, которые нас интересуют, а ребра — это связи между парами объектов. В интернете все совершенно понятно: есть сайты-вершины и гиперссылки-ребра. Если с одного сайта на другой ведет гиперссылка, то вот вам ребро, причем со стрелочкой. Потому что мы понимаем, в какую сторону мы поставили ссылку: что это именно Яндекс цитирует кафедру дискретной математики, а не наоборот. Если цитаты идут в обе стороны, значит, и стрелки пойдут в обе стороны. Получается конструкция, в которой мы можем интерпретировать сайты как некие точки или шарики, а гиперссылки — как перемычки, причем перемычек может быть несколько между двумя точками, если гиперссылок несколько. Такая структура и называется графом.
[columns size=»2/3″ last=»false»]Исследование этой структуры и ее свойств помогает решить самые разные задачи. Например, построение алгоритмов поиска в интернете каких-то неожиданных объектов: страниц, на которые ведет необычно много ссылок. Как правило, это либо спам, либо срочные новости. [/columns]
[columns size=»1/3″ last=»true»]
[/columns]
Мы с коллегами изучали веб-графы в Яндексе: строили вероятностные комбинаторные модели для описания того, как с течением времени растет и меняется интернет, интерпретируемый именно как такой веб-граф. И больше всего своим ученикам я люблю рассказывать, что у веб-графа с течением времени обнаруживаются некоторые свойства, не подверженные изменениям. То есть время идет, а свойства сохраняются. Например, количество гиперссылок с течением времени сохраняет пропорциональность количеству сайтов примерно с одним и тем же коэффициентом: рост числа вершин линейный. Изучая такой граф, можно обнаружить интереснейшие особенности и даже предсказать поведение этой структуры.
Но отнюдь не только интернет можно так описывать. Аналогичные модели применимы в экономике, в поиске мошенников в банковских сетях, в биологии, в энергетике и многих других отраслях современного знания. Даже модели распространения эпидемий на этом основаны! В предыдущем номере журнала «За науку» была статья о прогнозах пандемии, в которой как раз про это.
Поймать экстрим
Очень интересное направление — экстремальная комбинаторика, которой в основном и занимаются в лабораториях МФТИ. Многие ее задачи по традиции можно сформулировать в виде шутки. На своих семинарах я люблю развлекать учеников такой, например, формулировкой: имеется тридцать пьяниц, которые каждый вечер соображают на троих, причем делают это так: приходят втроем в кабак, напиваются и бьют друг другу морду. После того, как они друг другу морду набили, они становятся врагами навек и никогда больше вместе не собираются. Но на следующий день каждый из них может встретиться с другими участниками из тридцати имеющихся. Спрашивается: как долго может продолжаться это безобразие, если правильно построить весь алгоритм выбора троек тех, кто будет «соображать» в следующий вечер?
[columns size=»2/3″ last=»false»]Между прочим, это очень важная, глубокая задача, которая решает проблему передачи сигнала по каналу с некоторым количеством ошибок, приходящихся на каждое сообщение. Она относится к теории кодирования. И она же — задача экстремальной комбинаторики.[/columns]
[columns size=»1/3″ last=»true»]
[/columns]
Экстремальной ее называют не потому, что занятия ею представляют риск для жизни, а потому, что в ее задачах требуется найти экстремум — максимум или минимум. Например, в описанной задаче нас интересует максимальное количество трехэлементных подмножеств тридцатиэлементного множества, каждые два из которых пересекаются не больше чем по одному элементу.
Это модельный пример современной теории кодирования. В ней имеется масса глубоких задач, решаемых комбинаторными методами. Подобные решения имеют практическое применение во множестве технологий.
Например, интернет или сотовая связь. Допустим, имеется канал связи, по которому передаются непрерывно сообщения в виде нулей и единиц. Мы знаем заранее, что канал немного зашумлен, и нам необходимо разработать на аппаратном уровне программу, которая скомпенсирует помехи. Например, мы в курсе, что на одно сообщение приходится не более пяти ошибок в символах. Пусть одно сообщение — это сто символов, сто нулей и единиц. И при передаче этих ста нулей и единиц не более чем пять из них могут перейти в противоположные значения: передавали единичку, а она превратилась в ноль, или наоборот. Комбинаторика отвечает на вопрос, как построить кодирование, при котором мы сможем полностью восстановить информацию на входе. Иными словами, нам приходит сообщение, и мы знаем, что оно может быть зашумленным, но тем не менее можем восстановить все переданные символы.
[columns size=»1/2″ last=»false»]Это вещь совершенно практическая, и примеров ее применения довольно много. В наших лабораториях в МФТИ ученые занимаются множеством таких вопросов.[/columns]
[columns size=»1/2″ last=»true»]
[/columns]
Во-первых, это красиво
А вот еще пример. Существует в теории графов такое понятие — «хроматическое число». Оно появилось в XIX веке в рамках следующей задачи.
Имеется карта мира. Требуется найти минимальное количество цветов, в которые можно покрасить страны на этой карте так, чтобы граничащие между собой страны оказались покрашены в разные цвета.
Задача эта стала знаменитой проблемой, которую решили с помощью компьютера только примерно через 150 лет после ее постановки, в 1976 году. Ее назвали «Проблема четырех красок». Достаточно четырех цветов для любой карты определенного типа (скажем, страны должны быть связными и не содержать анклавов).
Пока решали задачу, было придумано огромное количество новых понятий, в том числе и хроматическое число графа. Что это такое? Это минимальное число цветов, в которые можно так покрасить вершины графа, чтобы концы каждого ребра были разного цвета. Если в проблеме четырех красок у каждой страны выделить столицу и назвать ее вершиной графа, а две столицы соединить ребром-дорогой, если страны граничат, то утверждение проблемы четырех красок состоит как раз в том, что хроматическое число любого такого графа не больше четырех.
Оказалось, что понятия раскраски графа и хроматического числа играют принципиальную роль в оптимизации компьютерных алгоритмов.
Представьте себе большое производство, где есть компьютер, решающий множество непрерывно поступающих задач. Но заранее известно, что какие-то пары задач он не может решать одновременно. Соответственно, строится граф: его вершины — это задачи, которые должны поступить на вход компьютеру, а ребра — пары задач, которые нельзя задавать компьютеру одновременно, иначе он сломается. Хроматическое число этого графа равно минимальному числу «порций» задач, которые можно последовательно «скармливать» компьютеру, чтобы обеспечить работу производства и осуществить ее в кратчайшие сроки.
Такая задача выглядит содержательнее, чем, казалось бы, развлекательная задача раскраски карты. Но вся суть и прелесть нашей науки как раз в том, что сначала придумали красивейшую задачку, а потом вдруг оказалось, что она еще и очень прикладная!
В комбинаторике такое случается постоянно.
