Кому нужна математика? Понятная книга о том, как устроен цифровой мир

Райгородский Андрей Михайлович

Литвак Нелли

Если вы хотите найти ответ на вопрос «Зачем мне математика?», эта книга для вас. В ней рассказывается о современных приложениях математики, без которых невозможно существование авиации, страхования, железных дорог, медицины, интернета, экономики… Список можно продолжать долго, но проще будет сказать – невозможно существование современного мира, каким мы его знаем.

Эта книга будет полезна широкому кругу читателей, но для наиболее заинтересованных и подготовленных читателей авторы добавили дополнительные сведения, объединив их в специальном приложении.

 

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

© Н. Литвак, А. Райгородский, 2016

© Издание, оформление. ООО «Манн, Иванов и Фербер», 2017

* * *

 

Введение

 

О чем эта книга

В этой книге мы расскажем о некоторых современных приложениях математики. Мы выбрали семь тем, по одной на каждую главу:

1) задачи планирования и составление расписаний (глава );

2) кодирование текстов для хранения и передачи в цифровом виде (глава );

3) структура соединения серверов каналами связи в интернете (глава );

4) балансирование нагрузки в телекоммуникациях (глава );

5) шифрование конфиденциальных сообщений (глава );

6) операции подсчета при анализе больших данных (глава );

7) распределение рекламных мест в поисковых системах, таких как Google и «Яндекс» (глава ).

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

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

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

Мы очень хотим разделить с вами если не наше увлечение, то хотя бы наше восхищение математикой – точной и красивой, древней и всегда современной и, безусловно, невероятно полезной!

 

Для кого эта книга

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

Основной текст. Основной текст книги не требует абсолютно никакой математической подготовки. Мы постарались писать его так, чтобы он был интересен и понятен каждому читателю. В каком-то смысле наш рассказ можно сравнить с научно-популярными телевизионными программами.

Дополнительные объяснения. Иногда для интересующегося читателя мы объясняем основные идеи чуть более подробно. Этот текст мы приводим во врезках. В основном он не требует математической подготовки. Но при желании его можно пропустить без ущерба для понимания остального содержания главы.

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

 

Глава 1

«Кому-то еще нужна математика?»

 

Нелли

После долгого перелета и полуторачасового стояния в очереди я наконец предъявляю паспорт и кладу указательный палец на маленький сканер в аэропорту Атланты. Унесенные ветром…

– С какой целью вы приехали в США? – в голосе пограничника нет ни капли интереса.

– Я приехала на конференцию.

– Какую?

– По математике.

Со мной все ясно, пограничник ухмыляется и берется за печать:

– И что, кому-то еще нужна математика?

Нет, вы только подумайте! Он сидит в аэропорту Атланты, где буквально каждые десять минут приземляется самолет, сканирует мой паспорт, компьютер в долю секунды находит мои отпечатки пальцев среди миллионов других отпечатков и сравнивает мой файл с сотнями тоненьких линий на маленьком сканере. Каким образом, хотелось бы знать, было решено, во сколько, куда и какой самолет должен садиться? Как сохранить отпечатки пальцев в компьютере, который хоть и показывает на экране всякие картинки, на самом деле не умеет хранить ничего, кроме нулей и единиц? Как быстро найти нужную запись среди миллионов других? И как компьютер – кучка пластмассы и железа – может решить, совпадают ли две картинки, отфильтровав при этом неизбежные помехи и неточности?

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

Я беру свой паспорт и улыбаюсь пограничнику:

– Конечно нужна!

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

Недавно я обсуждала эту ситуацию на занятии со студентами-математиками. Вас спрашивают: где вы учитесь? Вы отвечаете: на прикладной математике. Вас спрашивают: и зачем это нужно? В аудитории смущенные понимающие улыбки. Каждый не раз слышал этот вопрос.

Я считаю, что математика должна быть либо красивой, либо полезной. А лучше – как это часто бывает в настоящей науке – и то и другое! Наверное, без специальной подготовки красоту математики понять довольно сложно. Но мне кажется удивительным, что в эпоху цифровых технологий широкой публике так мало известно о невероятной полезности математики. Скептицизм американского пограничника – скорее правило, чем исключение. В этой книге мне хотелось понятно и интересно рассказать именно о пользе математики. Ну и о красоте, конечно, тоже. Надеемся, читатель сможет ее увидеть и оценить.

Андрей

В моей семье многие имели отношение к математике. Мама с папой, например, познакомились в МИИТе, где мама училась на факультете прикладной математики, а папа – на автоматизации систем управления (так тогда называли программистские факультеты). Папа в свое время учился в знаменитой 2-й школе. А мамин папа, мой дедушка, перед самой войной окончил мехмат МГУ и потом всю жизнь работал над расчетами траекторий космических аппаратов (скажем, тех же первых луноходов) сначала у Королева в Подлипках, потом у Лавочкина в Химках. Он, пожалуй, и оказал на меня наибольшее влияние. Я тоже учился на мехмате МГУ. Там на мой выбор математики в качестве профессии радикально повлиял мой научный руководитель – Николай Германович Мощевитин.

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

Я не считаю, что математика – это естественная наука, как физика, химия или биология. Это некий вид искусства. Знаменитый математик Эрдеш говорил, что у Бога есть книга, в которой содержатся идеальные математические доказательства, «доказательства из книги». Я тоже думаю, что математика открывает истины, содержащиеся в идеальном мире, и только потому она и имеет приложения, что видит «высшую реальность», проекцией которой служит этот мир. Иными словами, не математику оправдывают ее приложения (она прекрасна сама по себе), они возникают за счет того, что так устроен мир, и математика как раз об этом, об устройстве мира.

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

 

Лучший ответ на вопрос «Кому нужна математика?»

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

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

– Уважаемые господа! Я не буду утомлять вас длинной речью, а просто приведу пример. Недавно мы получили заказ от большой страховой компании, планирующей создать автосервис для своих клиентов. Идея очень проста: если у клиента в дороге сломалась машина, он может позвонить по телефону и к нему тут же приедет аварийная служба. Вопрос в том, как правильно организовать такой сервис. В принципе, задачу можно решить довольно просто – например, приставить к каждому клиенту личную аварийную машину с механиком. Тогда клиент в любой момент немедленно получит помощь. Но это очень дорого! Другой вариант – вообще не связываться с аварийным сервисом. Клиенты могут ждать до бесконечности, зато это не будет стоить им ни цента. Так вот. Если вас эти решения не устраивают, то я должен вам сообщить, что для любых других вариантов понадобится математика! Спасибо за внимание.

Нужно ли говорить, что математика получила колоссальные правительственные субсидии. Результаты этих инвестиций во всех областях, от транспорта до медицины, абсолютно потрясающие!

Кстати, среди студентов Нелли приз за лучший ответ получила Клара, которая сказала, что без математики невозможно было бы составить расписание поездов и они все время сталкивались бы друг с другом. О расписаниях поездов мы подробнее расскажем в , а пока немножко поговорим о том, чем занимаются профессиональные математики, от выпускников вуза в компаниях до ведущих ученых-теоретиков.

 

Математика на каждый день

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

Сфера деятельности математиков очень широкая: логистика, планирование, высокотехнологичное производство, биомедицинские технологии, финансы.

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

Среди ученых-математиков есть те, кто напрямую работает с приложениями. Мор Харкол-Балтер из университета Карнеги – Меллон говорит, что все ее исследования основаны на приложениях. Например, в 2011 году она сотрудничала с «Фейсбуком». По оценкам Мор, «Фейсбук» задействовал свои включенные серверы не более чем наполовину, а остальное время они простаивали. Включенный и незадействованный сервер тратит примерно две трети энергии работающего сервера. Но компании боятся выключать серверы, потому что чем их больше, тем быстрее они справляются с запросами пользователей. При этом на включение сервера уйдет 4–5 минут, а «Фейсбук» хочет выполнять запрос за полсекунды! Однако Мор не сомневалась, что серверы можно спокойно отключать. Из математической теории – теории массового обслуживания – ясно следовало, что если серверов много (а у «Фейсбука» их очень много!), то время, затраченное на включение, не оказывает никакого влияния. Мор и ее ученики разработали метод, при котором серверы включались и выключались без какого-либо ущерба для пользователей. «Фейсбук» последовал рекомендациям и, по утверждению компании, теперь экономит 10–15 % энергии.

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

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

 

Новые теории для современной практики

В 2008 году международное статистическое сообщество отпраздновало столетие со дня появления распределения Стьюдента. Стьюдент – это псевдоним очень талантливого математика по имени Вилльям Госсет. Госсет работал на пивоваренном заводе «Гиннесс» в Дублине. Его исследования в области статистики имели чисто коммерческие цели: они применялись при тестировании качества сырьевых продуктов, из которых делали пиво. Госсету не разрешалось публиковать труды по статистике под собственным именем, поэтому он публиковался под псевдонимом Стьюдент. Госсет вывел новое распределение вероятностей (распределение Стьюдента) и на его основе разработал теперь уже классическую статистическую процедуру, знаменитый t-тест.

t-тест обычно используется при необходимости сравнить случайную выборку с какой-то нормой или две случайные выборки между собой. Например, вы выпускаете шурупы и хотите проверить, соответствуют ли они норме по длине. Или вам нужно сравнить урожайность при использовании двух разных видов удобрений. Такие тесты широко применяются на практике, для них разработано стандартное программное обеспечение, t-тест не проходят разве что на филфаке.

За 100 лет статистика ушла далеко вперед. Сара ван де Гейр, профессор Швейцарской высшей технической школы Цюриха, работает над тестами с многомерными данными. Задача, так же как и задача Госсета, пришла из практики. Компания DSM в Швейцарии выпускает витамины и пищевые добавки. Витамин В2 производится с помощью бациллы сенной палочки. Компания хочет увеличить выпуск витамина благодаря генной инженерии. Имеются измерения производительности 115 бактерий, генный состав которых включает 4088 возможных генов. Спрашивается, какие гены способствуют росту производства витамина В2?

Это очень сложная задача, учитывая, что данных мало, а параметров много, причем все они взаимосвязаны. Существующие теории для этого случая не подходят, поэтому Сара и ее сотрудники сосредоточились на создании новых теорий. Это очень сложная математика, доступная только специалистам. Но то же самое сто лет назад можно было сказать и о работе Госсета! И мы совершенно не удивимся, если статистические процедуры, разработанные Сарой, через пару десятков лет займут свое место в университетских учебниках по статистике и задачка про сенную палочку будет предложена студентам-биологам на экзамене. Когда мы поделились этими мыслями с Сарой, она абсолютно серьезно сказала: «Конечно, очень скоро это будет стандартная статистика».

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

 

Математика неизвестного будущего

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

Никто не предрек появления интернета. Наоборот, Нобелевский лауреат Деннис Габор, изобретатель голографии, в 1962 году заявил, что передача документов по телефону хоть и возможна в принципе, но требует таких огромных расходов, что эта идея никогда не найдет практического воплощения. При этом первый успешный модем был представлен в том же году! А Кен Олсен, один из создателей Digital Equipment Corporation (DEC), в 1977 году сказал, что вряд ли найдется человек, которому может дома понадобиться компьютер. Через сколько лет после этого компьютер появился в вашем доме?

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

Наконец, нам трудно удержаться от еще одного варианта ответа на вопрос, зачем нужны новые сложные теории. Да просто ради красоты этих теорий! Красивая математика имеет полное право на существование. В научном мире должно оставаться что-то от Касталии Германа Гессе, где ученым разрешено заниматься чем угодно, где целью жизни может стать «игра в бисер» – «самая блистательная и самая бесполезная». Почему? Потому что нельзя поставить науку полностью на службу материальным нуждам общества. Наука выполняет функцию просветительства. Это единственная сфера деятельности, в которой человек может работать, движимый исключительно непрактическим любопытством. Грубо говоря, наука делает мир умнее и нужна человечеству так же, как и искусство, которое делает мир более духовным.

 

Глава 2

Менеджмент и многогранники

 

Компьютерные будни логистики

На специальности «Прикладная математика» в основном обучают математике. Доля программирования не так уж велика по сравнению с бесконечным матанализом, алгеброй и матфизикой. При этом выпускники часто становятся программистами.

– Интересно, насколько тебе нужна вся эта математика? – спросила Нелли у друга и бывшего однокурсника, а сегодня системного администратора в международной компании. Тот не задумался ни на секунду:

– Конечно нужна! Вот недавно клиенты заказали программу для распределения товаров по вагонам. Мы сразу поняли, что такую задачу ежедневно решают все поставщики всех товаров. Значит, она известная. Через полчаса мы уже знали, что это «задача об упаковке», и могли предложить несколько решений. Кстати, клиентам пришлось объяснять, что задача NP-трудная, то есть мы не можем гарантировать самое лучшее из всех возможных решений. И они согласились. А что им оставалось?

Вся современная логистика основана на математических методах. Где расположить склады и сервисные пункты? Как распределить товары по вагонам и грузовикам и какими маршрутами все это отправить? Сколько товара держать на складе и как часто его пополнять? Как составить расписание поездов, самолетов, большого производства и даже спортивных соревнований?

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

Исследование операций начало развиваться относительно недавно, после Второй мировой войны. И далеко не сразу научные результаты нашли практическое применение. В 2002 году в специальном юбилейном выпуске в честь 50-летия журнала «Исследование операций» Чарльз Холт делится своими воспоминаниями о том, как он и его коллеги Франко Модильяни, Джон Муф и Герберт Симон разрабатывали и внедряли научные методы планирования производства:

Мы взяли интервью у менеджеров пятнадцати компаний. Поначалу менеджеры отрицали наличие каких-либо проблем. По крайней мере таких, с которыми коллеги-профессора могли хоть как-то помочь. Но когда мы расспрашивали более подробно, возникали картины наподобие телеги на разваливающихся колесах – системы, катящиеся без всякого контроля от одного кризиса к другому {1} .

В процессе работы все менеджеры постепенно переключились на систему «коллег-профессоров». Команда написала книгу «Планирование производства, инвентаря и трудовых ресурсов». Модильяни и Симон получили Нобелевские премии по экономике, а работы Муфа легли в основу исследований Роберта Лукаса, тоже впоследствии лауреата Нобелевской премии.

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

В этой главе мы расскажем о задачах оптимизации, которые, в частности, возникают при планировании и составлении расписаний.

 

Проклятие размерности

Сложность задач оптимизации заключается в невообразимом множестве возможных решений. Чтобы продемонстрировать масштаб проблемы, давайте посмотрим на самый простой вариант расписания.

У нас есть один прибор, на котором нужно выполнить 25 заданий. Спрашивается: в каком порядке выгоднее всего это делать? «Выгода» может зависеть от срока выполнения, времени, проведенного в очереди, и других факторов.

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

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

На первое место можно поставить любое из 25 заданий. Для каждого из 25 вариантов для первого места у нас есть 24 варианта для второго места. Получается, что первые два места можно заполнить

25 × 24 = 600

способами. Продолжаем: 23 варианта для третьего места, 22 – для четвертого и так далее. Всего у нас получается

25 × 24 × 23 × 22 × 21 × 20 × 19 × 18 × 17 × 16 × 15 × 14 × 13 × 12 × 11 × 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 15511210043330985984000000

способов.

Это число называется двадцать пять факториал и обозначается «25!». Насколько оно велико? Если взять современный процессор с тактовой частотой 2 ГГц (2 млрд операций в секунду), то для выполнения такого количества операций ему понадобится 245 млн лет! А на то, чтобы просчитать все варианты, с прибылью и убытками, да еще и перемещать информацию в памяти компьютера, – и того больше. А ведь задачка казалась совсем простой, всего один прибор, всего 25 заданий. Не сравнить с серьезным современным производством.

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

Для некоторых задач удается найти гарантированно лучший ответ относительно быстро. Но для целого разряда так называемых NP-трудных задач, как, например, упомянутая выше задача об упаковке, сложно придумать метод, который работал бы намного быстрее, чем тривиальный полный перебор всех вариантов. Удастся ли когда-нибудь? Это открытый вопрос, но большинство ученых считают, что нет, потому что таких методов просто не существует. Многие практические задачи NP-трудные. В этом случае математики стремятся к быстрым и «почти» оптимальным решениям. А на практике приходится мириться с тем, что ответ достаточно хороший, но не всегда самый выгодный из возможных.

Разных методик для разных задач придумано множество. Мы расскажем о линейном программировании. Это мощная и уже ставшая классической теория, которая невероятно успешно применяется на практике.

 

Линейное программирование

Как возникают задачи линейного программирования, мы объясним на еще одном простом примере.

Допустим, у нас есть два склада: на северном и на южном конце города. В офис поступили заказы от двух клиентов. Клиент А заказал 60 листов железа, а клиент Б – 40 листов. На южном складе у нас в наличии 70 листов железа, а на северном – 35, то есть общего запаса хватает. Но мы хотим свести расходы на доставку к минимуму. Цены доставки приведены в табл. 2.1.

Таблица 2.1. Пример цен доставки

Спрашивается: сколько листов отправить клиентам А и Б с южного склада, а сколько – с северного?

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

Как же его найти? В нашем конкретном примере, в принципе, можно пойти путем перебора всех вариантов. Но если количество клиентов и складов увеличится, решить задачу вручную не удастся. Поэтому давайте посмотрим, как это сделать с помощью математики. Для начала, как учили в средней школе, введем переменные.

Клиенту А с южного склада доставлено АЮ листов железа. Тогда с северного склада клиенту А доставлено (60 – АЮ) листов. Аналогично клиенту Б с южного склада доставлено БЮ листов железа, а с северного – (40 – БЮ) листов. Теперь по табл. 2.1 можно рассчитать общую стоимость доставки:

5 × АЮ + 7 × (60 − АЮ) + 10 × БЮ + 15 × (40 − БЮ) (рублей)

Если раскрыть скобки, то получается:

общая стоимость доставки = 1020 − 2 × АЮ − 5 × БЮ (рублей) (2.1)

Нам нужно выбрать АЮ и БЮ так, чтобы стоимость была как можно меньше.

Но это еще не все. АЮ и БЮ нельзя выбрать просто так. В задаче есть существенные ограничения. Во-первых, мы не будем отправлять клиентам больше листов, чем они просили. Клиент А заказал 60 листов, а клиент Б – 40 листов. Поэтому в любом случае

АЮ ≤ 60, (2.2)

БЮ ≤ 40. (2.3)

Во-вторых, нужно учесть, что запас на каждом складе ограниченный. С южного склада мы отправляем АЮ + БЮ листов, а всего на этом складе 70 листов. Поэтому АЮ + БЮ не больше 70:

АЮ + БЮ ≤ 70. (2.4)

Аналогично с северного склада мы не можем отправить больше 35 листов:

(40 – АЮ) + (60 – БЮ) ≤ 35.

Раскрыв скобки в этом выражении, получаем:

АЮ + БЮ ≥ 65. (2.5)

Это ограничение можно интерпретировать еще и так: поскольку на северном складе 35 листов, а нам в совокупности необходимо доставить 100 листов, то как минимум 65 листов должны быть доставлены с южного склада.

Вот теперь все! Это и есть задача линейного программирования: нам нужно минимизировать стоимость, которая задана выражением (2.1), и при этом соблюсти ограничения (2.2) (2.5). Внизу, во врезке, задача приведена в окончательном варианте.

Задача линейного программирования

Выбрать АЮ и БЮ так, чтобы минимизировать:

1020 − 2 × АЮ − 5 × БЮ,

при ограничениях:

0 ≤ АЮ ≤ 60,

0 ≤ БЮ ≤ 40,

АЮ + БЮ ≤ 70,

АЮ + БЮ ≥ 65.

Мы добавили, что АЮ и БЮ либо ноль, либо больше нуля, потому что доставить клиенту отрицательное количество листов железа невозможно.

Программирование в данном контексте скорее «оптимизация», а не программирование на компьютере. Слово линейное употребляется потому, что используются исключительно линейные выражения, то есть переменные можно умножать на число, а также вычитать и складывать. И все. Никакие другие операции не применяются. Например, у нас нет выражений типа АЮ × БЮ или АЮ². Оказывается, в такой линейной формулировке можно представить очень многие задачи оптимизации.

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

 

Теория для практики

Пионер и основатель теории линейного программирования – советский ученый Леонид Витальевич Канторович. Над подобными проблемами он работал в конце 1930-х годов. В 1940-м вышла его фундаментальная статья «Об одном эффективном методе решения некоторых классов экстремальных проблем». В ней Канторович заложил математические основы линейного программирования (правда, тогда оно еще так не называлось).

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

Одна из классических знаменитых задач линейного программирования – задача о диете Стиглера, датируемая 1945 годом. Звучит она примерно так: какие из 77 продуктов должны входить в потребительскую корзину одного человека (скажем, мужчины среднего веса), чтобы он получил необходимую норму девяти питательных веществ (включая калории) и при этом стоимость продуктов была минимальной? Это очень важная задача в экономике, потому что ее решение определяет минимальную потребительскую стоимость полноценного питания.

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

Уже к концу 1950-х линейное программирование достаточно широко использовалось в нефтяной индустрии. Сегодня оно лежит в основе огромного класса задач оптимизации, включая задачи менеджмента и микроэкономики: планирование, логистика, составление расписаний. Задачи, где нужно минимизировать стоимость или максимизировать доход при заданных ограничениях.

 

От задачи к решению

Несмотря на простую формулировку, решить задачу линейного программирования вовсе не просто. Самая большая сложность заключается в ограничениях. Это видно даже на нашем маленьком примере. Понятно, что выгоднее всего доставить товар обоим клиентам с дешевого южного склада. Трудность в том, что это невозможно, потому что там всего 70 листов, а нам нужно 100.

Чем больше переменных и ограничений, тем сложнее задача. В классической задаче о диете 77 переменных и 9 ограничений, и она уже представляет собой серьезную проблему с точки зрения вычислений. Линейное программирование стало рядовым инструментом менеджмента и планирования только благодаря тому, что математики придумали для таких задач множество совершенно нетривиальных методов решения.

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

Симплекс-метод, сильно улучшенный и усиленный другими методами, по-прежнему остается неотъемлемой частью современного программного обеспечения.

 

Идея симплекс-метода

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

Для начала давайте посмотрим, какие в принципе значения могут принимать переменные, чтобы не нарушить наших ограничений. Например, мы можем взять АЮ = 58, БЮ = 8. В этом случае получается решение, которое мы записали в виде табл. 2.2.

Таблица 2.2. Пример решения, где АЮ = 58, БЮ = 8

Ограничения выполнены, и оба клиента получили заказанное количество листов.

Но это не единственное решение. Например, мы могли отправить больше листов с дешевого южного склада клиенту А, скажем 60 листов, и 10 листов клиенту Б. Легко увидеть, что доставка клиенту А теперь обойдется в

5×60=300 руб.,

а доставка клиенту Б будет стоить

10×10+30×15=550 руб.

Тогда общая стоимость получается не 864, а 850 рублей, то есть немного меньше, чем указано в табл. 2.2.

Чтобы не выбирать наугад, нужно посмотреть на все возможные решения, которые удовлетворяют ограничениям. Мы их изобразили на рис. 2.1. По оси х мы откладываем АЮ, а по оси у – БЮ. Любая точка в заштрихованной области удовлетворяет ограничениям. В том числе точка (58,8), как в таблице выше.

Рис. 2.1. Решения, удовлетворяющие ограничениям

Примечание: любая точка в заштрихованной области удовлетворяет всем ограничениям. Точка (58,8) это решение из таблицы выше. Угловые точки (25,40), (30,40), (60,10) и (60,5) кандидаты на оптимальное решение (см. объяснение в тексте).

Ниже во врезке мы объясняем, как получилась заштрихованная область. Объяснения соответствуют уровню средней школы. При желании их можно пропустить.

Как получена заштрихованная область на рис. 2.1

Все значения АЮ и БЮ положительные.

Вертикальная прямая линия АЮ = 60 обеспечивает ограничение АЮ ≤ 60. Все возможные значения находятся либо на ней, либо слева от нее.

Аналогично горизонтальная прямая линия БЮ = 40 обеспечивает ограничение БЮ ≤ 40. Все возможные значения находятся либо на ней, либо под ней. Выражение штрихпунктирной прямой АЮ + БЮ = 70 можно переписать в более привычном виде:

БЮ = 70 − АЮ,

поэтому прямая идет под отрицательным углом 45°. Заметьте, что она пересекает ось х (в нашем случае ось АЮ), когда БЮ = 0 и, соответственно, АЮ = 70. Нам нужно, чтобы выполнялось неравенство АЮ + БЮ ≤ 70, то есть

БЮ ≤ 70 − АЮ.

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

Аналогично пунктирная прямая АЮ + БЮ = 65 обеспечивает ограничение АЮ + БЮ ≥ 65. Значения, которые удовлетворяют этому неравенству, находятся на этой прямой или над ней.

Заштрихованная область, включая границы, удовлетворяет всем ограничениям.

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

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

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

В нашем маленьком примере углов всего четыре: (25,40), (30,40), (60,10) и (60,5). Мы можем легко подставить значения и подсчитать, что самое лучшее решение в точке (30,40), то есть с южного склада нужно отправить 30 листов клиенту А и 40 листов клиенту Б. Оставшиеся 30 листов клиенту А следует отправить с северного склада. Результат приведен в табл. 2.3:

Таблица 2.3. Оптимальный план поставки листов железа

Общая стоимость – 760 рублей, что гораздо меньше, чем 864 рубля – наше первое, выбранное наобум решение. Выгода – 12 %, и это очень существенно, особенно если таких доставок много.

То, что решение нужно искать «по углам», сказано уже на первой странице работы Канторовича. Это понятно любому математику.

Если же ограничений много, то у нас получается уже не четырехугольник, а многоугольник. А если много переменных, у нас будет не многоугольник, а многогранник! Найти и перебрать все углы многогранника невероятно сложно, на это может уйти очень много времени.

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

 

Составление расписаний

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

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

x (задание 3, очередность 1) = 1.

А если этого не происходит, то

x (задание 3, очередность 1) = 0.

Каждая переменная в решении – это целое число: 0 или 1.

С помощью этих переменных можно записать стоимость любой последовательности и практически любые ограничения. Типичное строгое ограничение: прибор не может выполнять два задания одновременно. Но можно добавить ограничения и посложнее. Например, «задание 3 нужно (или желательно) выполнить раньше, чем задание 10».

В реальности даже для составления относительно небольшого расписания имеет смысл воспользоваться математической моделью. Например, несколько лет назад студенты факультета прикладной математики Университета Твенте разработали модель для расписания ежегодного фестиваля хоров. Там несколько десятков хоров, несколько сцен, не каждый хор может петь на любой сцене, и у некоторых хоров один и тот же дирижер. Раньше организаторы бились над расписанием не один день. А компьютерная программа, которую написали студенты, выдавала решение буквально за несколько минут. Восхищенные певцы пришли в университет на презентацию проекта и спели студентам благодарственную арию!

 

Почему целые числа сложнее дробных

Потребность в целочисленном решении кардинально усложняет задачу. Симплекс-метод не даст готового решения, потому что координаты углов многогранника вовсе не обязаны быть целыми и обычно целыми не будут. Целочисленное линейное программирование относится к разряду NP-трудных задач.

Классический подход к решению называется методом ветвей и границ. Он основан на «разветвлении» дробных решений на допустимые целочисленные и исключении неперспективных «веток».

Для практического применения наивное использование метода ветвей и границ абсолютно не годится. Математики дополнили его многими другими методами. Например, сейчас на практике широко применяется метод «отсекающих плоскостей» (алгоритм Гомори), позволяющий эффективно отсекать дробные значения.

За относительно недолгий срок своего существования эта область математики достигла невероятного прогресса.

 

Математика, обогнавшая компьютер

Американский ученый Роберт Биксби написал целую серию статей об истории линейного программирования. В нашем рассказе мы воспользовались его статьей 2012 года.

По словам Биксби, после нескольких усовершенствований симплекс-метода к 1953 году удалось решить вариант знаменитой задачи о диете с 71 переменной и 26 ограничениями.

Аппарат, на котором производились вычисления, не был компьютером в строгом смысле этого слова. Это был огромный численный прибор, программируемый с помощью перфокарт. Решение заняло 8 часов, большая часть которых ушла на то, чтобы вручную вставлять перфокарты в машину. Настойчивости и терпению ученых остается только удивляться.

Сегодня для решения задач линейного программирования на практике в основном используется коммерческое программное обеспечение. Среди самых известных пакетов – CPLEX и более недавний Gurobi.

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

Абсолютно очевидно, что любой алгоритм на современном компьютере будет работать гораздо быстрее, чем на давно устаревшей махине с перфокартами. Но и математика не стоит на месте. Старые алгоритмы совершенствуются, появляются новые. Как оценить роль математики в успехе коммерческих пакетов?

В 2007 году Биксби провел впечатляющий эксперимент. Он взял все версии пакета CPLEX, начиная с его первого появления в 1991 году, и опробовал их на большом количестве известных практических задач целочисленного линейного программирования. Ученые собрали внушительные коллекции таких задач. Биксби выбрал из них 1892, а затем сравнил скорость их решения, от версии к версии, на одном и том же компьютере.

Оказалось, что за 15 лет скорость решения увеличилась в 29 000 раз! Интересно, что самое большое ускорение, почти десятикратное, произошло в 1998 году, причем не случайно. До этого математики в течение 30 лет разрабатывали новые теории и методы, из которых очень мало было внедрено в практику. В 1998 году в версии CPLEX6.5 была поставлена задача реализовать по максимуму все эти идеи. В результате наши возможности в линейном программировании вышли на качественно новый уровень.

Процесс продолжается. Gurobi появился в 2009 году и к 2012-му ускорился в 16,2 раза. А общий эффект в 1991–2012 годах – в 29000×16,2 раз! Повторим, что это произошло независимо от скорости компьютера, иными словами, исключительно благодаря развитию математических идей.

Если верить закону Мура, то за 1992–2012 годы компьютеры ускорились примерно в 8000 раз. Сравните с почти полумиллионным ускорением алгоритмов! Получается, что если вам нужно решить задачу линейного программирования, то лучше использовать старый компьютер и современные методы, чем наоборот, новейший компьютер и методы начала 1990-х.

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

Конечно, самое поразительное – совместный эффект математики и компьютеров. Ускорение в 4 миллиарда раз. Задачи, на которые требовалось 126 лет в 1991 году, в 2012-м мы научились решать за одну секунду! И это не предел. В статье 2015 года Димитрис Бертсимас и Анжела Кинг из Массачусетского технологического института приводят новую цифру – 450 миллиардов – и предлагают новые приложения линейного программирования в статистике.

При столь невероятной эффективности для линейного программирования открываются новые горизонты, немыслимые ранее, но вполне реальные сегодня.

 

Расписание движения поездов на голландских железных дорогах

Самая престижная награда в исследовании операций – премия Франца Эдельмана за выдающиеся успехи науки в приложениях. В 2008 году ее получили Железные дороги Нидерландов за новое железнодорожное расписание, которое начало действовать в 2006 году.

Нидерланды – маленькая, но густонаселенная страна. На территории размером примерно с Нижегородскую область проживает около 17 миллионов человек. Железные дороги – основа всей голландской логистики. Многие каждый день ездят на поезде на работу. Совещание в другом конце страны – обычное дело. Голландцы – чемпионы Европы по пассажирским железнодорожным перевозкам. В 2006 году Железные дороги Нидерландов перевезли 15,8 миллиарда пассажиров.

До 2006 года действовало расписание, составленное в 1970 году. Перевозки увеличивались, составы постепенно удлинялись, а где возможно, добавлялись новые поезда. Пока наконец к началу 2000-х увеличивать перевозки в рамках старого расписания стало невозможно. Прокладывать новые пути фактически тоже невозможно из-за их безумной дороговизны, да и просто нехватки земли. Железнодорожные пути в Нидерландах строились и расширялись очень мало еще со времен Второй мировой войны. Задача, которая встала перед менеджментом железных дорог, – обеспечить требуемый объем перевозок при имеющейся инфраструктуре. Как это сделать? В 2002 году было решено составить новое расписание.

Расписание железных дорог – дело очень сложное. Нужно, чтобы два поезда одновременно не претендовали на один и тот же участок рельсов. Маршруты с пересадками тоже должны быть удобными, без получасового ожидания на платформе. Кроме того, нужно распределить пути прибытия и отправления на каждой станции, определить количество и тип вагонов для каждого состава, составить расписание кондукторов и машинистов. И все это для 5500 поездов в день!

Над задачей работала целая команда математиков. Основные сложности и идеи они описали в статье, за которую им была присуждена премия Эдельмана.

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

 

Что такое оптимальное решение

Если вы недавно посещали Нидерланды, то последний раздел вас мог удивить. Железнодорожное движение далеко от совершенства. Мелкие (и крупные) задержки случаются сплошь и рядом. Пересадки порой очень короткие, их легко пропустить при малейшем опоздании. Поезда часто переполнены, особенно вагоны наиболее популярного 2-го класса. Далеко не все обрадовались новому расписанию. Влиятельная голландская газета NRC Handelsblad писала:

Это единственная форма высшей математики, которая вызвала в обществе такую бурю эмоций.

Александр Схрейвер, знаменитый голландский математик, один из лучших в мире специалистов по оптимизации, играл ведущую роль в составлении нового расписания. Критика журналистов его не очень взволновала. В одной из статей, рассчитанной на широкую публику, он пишет:

Что определяет оптимальность? Комфорт пассажиров? Общий доход? Расписание персонала? Циркуляция материалов? Или пунктуальность? Каждый из этих аспектов сам по себе уже трудно оценить. Но даже если удастся, как взвесить эти факторы по отношению друг к другу?

Очень важно понимать, что оптимальное решение вовсе не означает решение идеальное. Оптимизация происходит с массой ограничений, и пожелания к решению противоречат друг другу. Например, максимальное количество пассажиров и дешевизна перевозок противоречат максимальному комфорту. Оптимальное решение – это лучшее, что мы можем сделать при заданных ограничениях и приоритетах.

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

 

Глава 3

Мир нулей и единиц

 

Перевод текста в килобайты

Как передаются тексты с одного компьютера на другой? Например, мы хотим переслать текст «Мама мыла раму» или «Над всей Испанией безоблачное небо». Как это сделать? Разумеется, по проводам нельзя передать напечатанные слова «мама», «небо» и другие. Можно передать только сигналы. Значит, каждой букве или слову нужно подобрать свой сигнал.

Как перевести слова в сигналы? Если подумать, то на ум приходит нечто вроде азбуки Морзе, когда все буквы и слова передаются в виде точек и тире. Совершенно аналогично компьютеры пользуются всего двумя сигналами. Поэтому вся информация в компьютере записывается посредством двух символов: 0 и 1.

Понятно, что мы только для примера написали фразы по-русски. А вдруг завтра нам понадобится передать сообщение на английском или французском, где совсем другие (латинские) буквы, не говоря уже о разных «акцентах», характерных для французского языка? А еще есть арабские буквы, несколько витиеватых алфавитов Индии и тысячи, если не десятки тысяч, китайских и японских иероглифов! Обучить компьютер отличать один язык от другого – не проблема, такие программы уже есть. Но для хранения и передачи информации это совершенно бесперспективно. Гораздо проще для каждого символа, будь то буквы, иероглифы или знаки препинания, составить свою, уникальную, последовательность из нулей и единиц. К этому можно добавить отдельные последовательности для часто употребляемых слов, особенно если их не слишком много.

Конечно, можно построить компьютеры, которые будут различать три разных сигнала или больше. Но двоичная система (два сигнала, два символа) гораздо удобнее. Ток либо есть (1), либо нет (0) здесь машина не может ошибиться. Поэтому устройства с двоичной системой проще в изготовлении и надежнее.

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

Соответственно, объем информации в компьютере определяется тем, сколько нулей и единиц нам понадобилось. Каждый ноль или единица представляют собой минимальный объем информации, так называемый один бит. Восемь битов, то есть последовательность из восьми нулей и единиц, называется один байт. Всем известный килобайт (Кбайт), та самая единица измерения объема наших имейлов и документов, равен 1024 байта, или 8192 нуля и единицы. Аналогично мегабайт – это 1024 килобайта.

Почему 1024, а не просто 1000? Потому что в двоичной системе, где всего две цифры, проще всего пользоваться степенями двойки: 2, 4, 8, 16, 32 и так далее. Вполне логично, что в привычной нам десятичной системе, где у нас 10 цифр от 0 до 9, удобно пользоваться степенями десятки: 10, 100, 1000 и так далее. Число 1024 – это два в десятой степени:

1024=2 10 =2×2×2×2×2×2×2×2×2×2

Многие считают, что килобайт – это тысяча байтов. Строго говоря, это не так, но приблизительно верно и больше соответствует нашей привычке считать десятками, сотнями и тысячами.

Сколько килобайтов в вашем сообщении, зависит не только от самого текста, но и от того, каким образом ваши слова были переведены в нули и единицы.

Как сделать сообщение компактным? Где гарантия, что замена нескольких нулей на единицы из-за помех в каналах связи не изменит смысл на полностью противоположный? Проблемы передачи информации послужили толчком для развития целой области современной математики – теории кодирования.

 

Что такое кодирование

Итак, наша цель – закодировать каждый символ или каждое слово текста с помощью нулей и единиц. Фактически код – это словарь, состоящий из кодовых слов. Каждое кодовое слово представляет собой последовательность нулей и единиц (желательно небольшой длины), которая что-то означает (буква, цифра, знак препинания или целое слово). Построить код можно множеством разных способов, а значит, эта задача очень интересная.

Давайте, к примеру, закодируем отдельно каждую букву русского алфавита. Забавно, кстати, что, когда ставишь эту задачу студентам, почти всегда кто-нибудь спрашивает, сколько букв надо учитывать: 32 или 33. По-видимому, они считают букву «ё» не вполне самостоятельной, потому что в текстах ее обычно меняют на «е». Будем все-таки считать, что букв у нас 33. Сколько байтов (нулей и единиц) нам понадобится, чтобы закодировать 33 буквы?

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

а: 100000000000000000000000000000000

б: 010000000000000000000000000000000

в: 001000000000000000000000000000000

г: 000100000000000000000000000000000

и так далее

я: 000000000000000000000000000000001

Сразу видно, что подобное кодирование неприменимо на практике. Слишком много драгоценных байтов уходит на нули, которые несут очень мало информации.

Какая минимальная длина кода нам понадобится, чтобы закодировать русский алфавит? Скажем, хватит ли нам кодов длины 5? Это зависит от того, сколько разных последовательностей из нулей и единиц длины 5 мы можем составить: 00000, 00001, 00010, 00011 и далее до 11111. Всего 32 такие последовательности. Получить данный ответ довольно просто: это 2 в степени 5, то есть 2 × 2 × 2 × 2 × 2.

Оказывается, последовательностей длины 5 не хватает, так что вопрос студентов попал в самую точку! Всего из-за одной «лишней» буквы нам понадобится как минимум 6 нулей и единиц в каждом «кодовом слове».

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

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

«Растет по экспоненциальному закону» на общедоступном языке означает «растет очень быстро»! Помните легенду о том, как король хотел наградить изобретателя шахмат? Умный изобретатель попросил короля положить на первую клетку доски одно зернышко, на вторую – два, на третью – четыре и далее в том же порядке: в два раза больше на каждую следующую клетку. Король согласился и был потрясен, когда зерна в его амбарах не хватило и на половину доски. Точно так же и количество возможных последовательностей из нулей и единиц возрастает очень быстро с их длиной: 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…

Экспоненциальная зависимость между количеством разных кодовых слов и их длиной – абсолютно фундаментальная концепция в информатике и вопросах передачи информации.

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

Основные концепции о том, как измерить количество информации, изложены в фундаментальной работе Клода Шэннона, опубликованной в 1949 году. Эти концепции во многих отношениях положили начало развитию информатики и строятся все на той же основополагающей экспоненциальной зависимости. Однако мы не будем углубляться в теорию информации, а вернемся к вопросу о том, как составить надежные и эффективные коды.

 

Коды, исправляющие ошибки

Как вы уже поняли, код – это просто любой набор последовательностей из нулей и единиц. Но не все коды одинаково хороши. Разумеется, неплохо, если каждое кодовое слово достаточно короткое. Об этом мы как раз говорили в прошлом разделе. Однако есть куда более интересные характеристики кода, нежели длина кодовых слов.

Представим, что мы начали передавать кодовые слова по каналу связи, но в нем иногда возникают помехи. Из-за каждой такой помехи передаваемый символ меняется на противоположный: ноль – на единицу, единица – на ноль. Можно ли подобрать кодовые слова так, чтобы все передаваемые символы, несмотря на ошибки, удалось однозначно восстановить? Звучит как научная фантастика! Но оказывается, можно! Достаточно лишь правильно сформулировать соответствующую математическую задачу.

Допустим, наши кодовые слова длины 6 и на каждое кодовое слово приходится не более одной ошибки. Поскольку это простой пример, представим, что наш словарный запас беднее, чем у Эллочки-людоедки из «Двенадцати стульев», и состоит всего из трех слов, которые мы закодировали тремя кодовыми словами:

111000, 001110, 100011.

Конечно, много таким кодом не передашь, но для примера вполне достаточно. Еще важно, что получатель знает наш «словарь», то есть ожидает от нас либо 111000, либо 001110, либо 100011 и ничего другого.

Предположим, мы сначала передаем слово 111000. В результате не более чем одной ошибки (ошибки мы выделили жирным шрифтом) оно может превратиться в одно из слов:

111000, 011000, 101000, 110000, 111100, 111010, 111001, (3.1)

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

001110, 101110, 011110, 000110, 001010, 001100, 001111. (3.2)

Наконец, для 100011 у нас выйдет:

100011, 000011, 110011, 101011, 100111, 100001, 100010. (3.3)

Замечательно то, что списки (3.1) (3.3) попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка (3.1), получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка (3.2) слово 001110; то же самое касается и списка (3.3). В этом случае говорят, что наш код исправил одну ошибку.

За счет чего произошло исправление? За счет двух факторов. Во-первых, получатель знал весь «словарь». Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.

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

Совершенно ясно, что наугад такие коды составить невозможно. За этим стоит целый математический аппарат. Нам нужно научиться измерять расстояния между словами и даже работать с шарами из слов. Что это такое и как это делается, может понять практически любой человек. Ниже мы попробуем объяснить, как создаются коды, исправляющие ошибки, и какие при этом возникают проблемы.

 

Шары Хэмминга

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

Рис. 3.1. Шар радиуса r в трехмерном пространстве. Все точки удалены от центра не больше чем на расстояние r

Зато понятия точка и расстояние в математике абсолютно абстрактные. Есть несколько простых правил, которых следует строго придерживаться, но в рамках этих правил – полная свобода. Точками могут быть сигналы, а могут – кривые и даже результаты случайных экспериментов. И расстояния между ними можно определить самыми разными способами. В итоге получаются «шары», не поддающиеся воображению. Тем не менее эти абстрактные шары играют в математике очень большую роль.

В теории кодирования точка – это кодовое слово, то есть последовательность нулей и единиц заданной длины. А расстоянием принято считать так называемое расстояние Хэмминга.

Расстояние Хэмминга между двумя кодовыми словами – это всего-навсего число позиций, на которых у этих слов стоят разные символы: у одного 0, а у другого 1. Например, на рис. 3.2 расстояние Хэмминга между двумя кодовыми словами равно трем. Мы заключили в рамки те позиции, где эти два кодовых слова отличаются друг от друга.

Рис. 3.2. Расстояние Хэмминга между двумя кодовыми словами – число позиций, на которых у этих слов стоят разные символы. На рисунке это расстояние равно трем. Позиции, где два кодовых слова отличаются друг от друга, заключены в рамки

Что происходит, если при передаче, скажем, слова 111000 произошла одна ошибка?

Получится другое слово, которое будет отличаться от 111000 всего на одной позиции. Иначе говоря, если у нас при передаче происходит не больше одной ошибки, расстояние Хэмминга между отправленным и полученным кодовым словом будет не больше единицы. Давайте снова посмотрим на перечень (3.1) предыдущего раздела:

111000, 011000, 101000, 110000, 111100, 111010, 111001.

Расстояние Хэмминга между словом 111000 и любым другим словом из перечня не превосходит 1. Значит, этот список – не что иное, как шар радиуса 1 с центром 111000!

Кстати, подобное определение можно ввести и для обычных слов русского языка одинаковой длины. Например, расстояние Хэмминга между словами «дочка» и «точка» равно единице, а между словами «точка» и «галка» – трем. Если слово «точка» – это центр шара Хэмминга радиуса 1, то слово «дочка» входит в этот шар, а слово «галка» – нет.

Шары Хэмминга очень трудно себе представить даже для маленьких кодов. На рис. 3.3 мы изобразили расстояния Хэмминга между кодовыми словами длины 3. Расстояния Хэмминга могут быть 0, 1, 2 или 3. На рисунке чем темнее цвет, тем больше расстояние. Если взять, например, колонку 000, то шар Хэмминга радиуса 1 – это все белые и светло-серые квадратики в этой колонке: 000, 001, 010, 100. Сразу видно, что расположение белых и, скажем, самых темных квадратиков в колонках неодинаковое, хотя, конечно, в рисунке много закономерностей. Например, рисунок из самых светлых тонов (белый и светло-серый) абсолютно симметричен рисунку из двух оставшихся более темных тонов.

Рис. 3.3. Расстояние Хэмминга между кодовыми словами длины 3. Справа изображен цветовой код. Расстояния: 0, 1, 2, 3. Чем темнее цвет, тем больше расстояние

Кодовые слова длины 3 – очень простой пример, их всего восемь. Стоит чуть увеличить длину кодового слова, и из-за уже знакомого нам экспоненциального закона слов станет так много, что картинка нам не поможет. Профессор Джон Слэни из Австралийского национального университета сделал замечательный рисунок, на котором изображены расстояния Хэмминга между кодовыми словами длины 8, а это всего один байт. Таких слов 256. Советуем заглянуть на веб-страницу Слэни и посмотреть на этот рисунок. Вам сразу станет понятно, что он никак не поможет найти хороший код. Картинка скорее напоминает красивый коврик. Нам нужен другой математический аппарат, и, к счастью, такой аппарат есть. Теория кодирования тесно связана с комбинаторикой – наукой о комбинациях тех или иных объектов.

Возможно, вы уже заметили связь между шарами Хэмминга и кодами, исправляющими ошибки. Допустим, мы передаем кодовые слова длины 10 и хотим, чтобы код исправлял две ошибки. Тогда надо построить код, в котором шары с центрами в кодовых словах и радиусами 2 попарно не пересекались бы. Все последовательности нулей и единиц в таком шаре будут означать одно и то же кодовое слово. Иначе говоря, кодовые слова должны отличаться друг от друга настолько, чтобы при наличии двух ошибок их невозможно было перепутать. На языке математики это значит, что расстояния Хэмминга между кодовыми словами должны быть как минимум равны 5.

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

 

История кодов, исправляющих ошибки

Ричард Хэмминг, именем которого названы расстояния между кодовыми словами, – один из основателей современной теории кодирования. Эта теория начала развиваться в конце 40-х годов XX века, когда Хэмминг работал в Bell Labs и занимался проблемами передачи информации.

Хэмминг заметил, что в коде, исправляющем ошибки, количество возможных кодовых слов неизбежно должно быть ограничено. Например, мы хотим построить код из слов длины 10, который исправляет две ошибки. Сколько разных кодовых слов мы можем использовать? Допустим, мы выбрали кодовое слово 0000011111, чтобы закодировать букву «а». Теперь все последовательности на расстоянии Хэмминга один или два от 0000011111, то есть в шаре радиуса 2 с центром 0000011111, нельзя использовать для кодирования никакой другой информации. Они нам нужны для исправления ошибок при передаче буквы «а». Такой шар содержит 56 последовательностей. Получается, что на каждое кодовое слово, которое что-то означает, приходится 56 слов на исправление ошибок. Поэтому мы можем закодировать не 1024, а всего лишь 1024/56, то есть 18 разных символов или сообщений. Если этого мало – например, мы хотим закодировать русский алфавит, – то длину кодовых слов придется увеличить. Это увеличит и количество килобайтов, но такова цена за исправление ошибок.

Рассуждая примерно так, как мы описывали в предыдущем параграфе, Хэмминг получил максимальное число слов любой длины с исправлением любого заданного количества ошибок. Эта формула называется границей Хэмминга.

Заметим, что граница Хэмминга – это максимально возможное число слов в коде, исправляющем ошибки. Но это еще не означает, что такой максимальный код можно найти. Представьте, что мы имеем дело с обычными шарами. Нельзя уложить круглые апельсины в ведро или коробку так, чтобы между соседними апельсинами не было пустот! Где же гарантия, что все последовательности из нулей и единиц можно разбить на шары Хэмминга так, чтобы они не пересекались и между ними не было свободного места? Оказывается, такое разбиение во многих случаях возможно. Мы не станем здесь описывать конструкцию, ее можно найти в специальной литературе (см.).

Впрочем, сделано в этом направлении далеко не все. Конструкции есть, но только асимптотические, то есть такие, в которых длина кодового слова очень большая и увеличивается до бесконечности, а количество ошибок при этом маленькое и фиксированное. Однако во многих практических задачах чем длиннее кодовое слово, тем больше ошибок. В такой ситуации проблема отыскания правильных верхних границ и построения максимальных кодов по-прежнему открыта! Более того, в этой ситуации известно, что граница Хэмминга, как правило, не точна, и есть еще масса более аккуратных оценок, среди которых и оценка Владимира Иосифовича Левенштейна, замечательного российского математика, и границы линейного программирования. Эти конструкции очень сложны и выходят далеко за рамки нашей книги.

Особый интерес вызывают так называемые равновесные коды. В них все кодовые слова содержат одинаковое количество единиц. Для таких кодов можно найти границу, аналогичную границе Хэмминга. И снова возникает вопрос о существовании равновесного кода, достигающего полученной границы. В начале 80-х годов XX века Войцех Рёдль придумал очень хитрую вероятностную технику, позволившую доказать наличие равновесных кодов, в которых число кодовых слов асимптотически равно верхней границе.

Буквально пару лет назад Питер Киваш из Оксфордского университета объявил о построении равновесных кодов, в которых количество слов достигает теоретической верхней границы. Это очень объемная и трудная математическая работа; она до сих пор тщательно проверяется и потому опубликована только в интернете.

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

 

Можем ли мы закодировать все подряд

Все описанное в этой главе в основном применимо к кодированию текстов. Другим видам информации присущи свои особенности.

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

Если вам когда-нибудь приходилось использовать нестандартные цвета в обычных программах типа Word или PowerPoint, вы, возможно, заметили опцию, где интенсивность красного, зеленого и синего можно задать вручную. Обычно интенсивность определяется числом от 0 до 255. Всего 256 вариантов – ровно по количеству разных последовательностей нулей и единиц длины 8, то есть один байт. В результате нам нужно всего три байта, чтобы закодировать 256 × 256 × 256 = 16777216 – более шестнадцати с половиной миллионов оттенков компьютерной палитры.

Если обозначать интенсивность цветов цифрами в стандартном порядке красный-зеленый-синий, то 0–0–0 – это черный цвет, а 255–255–255 – белый. Если интенсивность красного, зеленого и синего одинаковая, то между черным и белым получится целых 254 оттенка серого. А желтый можно получить, если использовать красный и зеленый с одинаковой интенсивностью. В табл. 3.1 приводится пример красно-зелено-синего кода для цветов радуги.

Таблица 3.1. Пример цветового кода для цветов радуги. Интенсивность основных цветов (красного, зеленого и синего) определяется числом от 0 до 255

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

Здесь требовалось решить задачу иного рода – задачу сжатия данных: как сделать код как можно короче и при этом не потерять информацию. Такие задачи часто возникают, когда нужно сохранить и использовать большое количество информации. Именно эту задачу решают программы для архивирования типа Zip.

Стандартный способ сжатия данных для фильма – полностью кодировать первый кадр, а затем кодировать не каждый кадр отдельно, а только изменения. Но при необходимости сохранить информацию иного рода, например кто с кем дружит в «Фейсбуке», понадобятся совершенно другие способы сжатия данных. И они, кстати, уже разработаны.

А вот со звуком все намного сложнее. Мы до сих пор не умеем кодировать звучание симфонического оркестра так, чтобы оно воспроизводилось как в концертном зале.

Эта задача выходит за рамки не только нашей книги, но и математики. Математика – великая наука, но ее возможности распространяются только на объекты, которые поддаются формальному описанию, буквами и числами. Математики научились кодировать текст потому, что когда-то люди изобрели слова и алфавит. Математики умеют кодировать цвет потому, что физики обнаружили, что любой оттенок определяется интенсивностью красного, синего и зеленого. Несомненно, математики придумали бы эффективные коды для живого звука, если бы хоть кто-нибудь сумел описать, из каких сигналов и интенсивностей он состоит. Но, к сожалению, сделать это исчерпывающим образом пока никому не удалось.

 

Глава 4

Надежность интернета

 

Связанные одной сетью

Практически каждый из нас ежедневно пользуется интернетом. Интернет – это сеть компьютеров и серверов, которые физически соединены каналами связи для передачи цифровой информации с одного сервера на другой.

Сигнал идет со скоростью света, поэтому совершенно неважно, где находятся серверы – в России, США или Австралии. Пройденные расстояния практически не влияют на скорость передачи. Мы все уже давно привыкли, что имейлы и WhatsApp доходят в считаные секунды, веб-страницы грузятся быстро, а наш голос и даже изображение передаются по скайпу в реальном времени. Но, если задуматься, где гарантия, что в любой момент любой сервер мира может связаться с любым другим?

В какой-то степени интернет можно сравнить с системой железных дорог. От любой станции можно добраться до любой другой. Но железные дороги спланированы централизованным образом, их план прошел множество инстанций. Интернет – совсем другое дело. Основные каналы связи (обычно это волоконно-оптические линии) принадлежат самым разным владельцам: компаниям и организациям, например крупным операторам телефонной и мобильной связи. Вместе они составляют так называемую опорную сеть интернета.

Большинство компаний, в том числе и многие интернет-провайдеры, заключают договоры на пользование каналами связи и платят аренду. Как только появляется выход к опорной сети, можно начинать строить собственную сеть, присоединять новые серверы и компьютеры. Возникают локальные сети, они соединяются друг с другом, образуют более крупные сети и так далее. И все эти гигантские сети сетей соединены центральной, опорной сетью. Отсюда и название интернет (Internet): net по-английски – сеть.

Ни один человек и ни одна компания в мире не отвечают за то, чтобы сервер, через который вы присоединились к интернету, был связан с другим сервером, скажем, на острове Кенгуру. Но вся система по своей природе устроена так, что связь гарантирована. Интернет – гигантская международная технологическая и коммерческая конструкция, без которой мы уже не представляем своей жизни, – прекрасно обходится без правления и правительства. Если вдуматься, это просто поразительно!

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

Эта глава о том, как мы можем хотя бы частично понять и объяснить удивительную надежность интернета.

 

Сети и помехи

Начнем с простого примера. Допустим, наш интернет состоит всего из трех компьютеров, которые соединены друг с другом как на рис. 4.1. Если все три канала связи работают, нет никаких проблем: все три компьютера могут обмениваться информацией.

Рис. 4.1. Мини-интернет из трех компьютеров, соединенных каналами связи. Все три канала работают, все три компьютера могут обмениваться информацией

Теперь допустим, что в одном из каналов связи возникли помехи и передать по нему в данный момент ничего нельзя. Мы изобразили эту ситуацию на рис. 4.2. Сразу видно, что наш мини-интернет не распался. Несмотря на то что прямая связь между компьютерами 1 и 2 утеряна, они по-прежнему могут передавать друг другу информацию через компьютер 3. Заметит ли пользователь неполадку в канале? Скорее всего, нет. Поскольку сигнал идет со скоростью света, нет никакой разницы в скорости доставки информации – пойдет ли сигнал напрямую из Москвы в Нижний Новгород или даст кругаля через Сидней или Нью-Йорк.

Рис. 4.2. Мини-интернет из трех компьютеров. Хотя канал связи между компьютерами 1 и 2 недоступен, они по-прежнему могут обмениваться информацией через компьютер 3

Чтобы развалить нашу маленькую сеть, нужно вывести из строя как минимум два, а то и все три канала связи, как показано на рис. 4.3.

Рис. 4.3. Мини-интернет из трех компьютеров. Сверху: вышли из строя два канала связи, компьютер 1 оказался отрезанным от сети. Снизу: вышли из строя все три канала связи, связь между компьютерами полностью прервана

Насколько устойчива наша мини-сеть? Сосчитать это совсем нетрудно. Допустим, помехи в отдельных каналах связи возникают независимо друг от друга с какой-то вероятностью, скажем 40 %. На практике это означает, что в среднем в четырех из десяти случаев канал оказывается недоступным. Сорок процентов – многовато для реального интернета, но для примера подойдет.

Компьютер 1 может оказаться отрезанным от сети, как на рис. 4.3 сверху с вероятностью 0,4 × 0,4 × 0,6 = 0,096(×100 %) = 9,6 %. В аналогичную ситуацию могут попасть компьютеры 2 и 3 с той же долей вероятности. Наконец, надо добавить вероятность самой плохой ситуации, как на рис. 4.3 снизу, которая равна 0,4 × 0,4 × 0,4 = 0,064(×100 %) = 6,4 %. В результате получается, что наша сеть «развалится» с вероятностью 3 × 9,6 % + 6,4 % = 35,2 %.

Конечно, 35,2 % – довольно много, но мы взяли нереально большую вероятность помех. Самое интересное, что вероятность потери связи в сети меньше, чем вероятность потери связи в одном канале: 35,2 % меньше, чем 40 %. Сеть более устойчива, чем отдельно взятый канал!

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

Таблица 4.1. Вероятности потери связи в мини-сети (правая колонка) при заданной вероятности потери связи в одном канале (левая колонка)

Мы видим, что значения в правой колонке убывают гораздо быстрее, чем в левой. Если вероятность недоступности канала 1 % – величина вполне реальная на практике, – то наша скромная мини-сеть в 33 раза устойчивее, чем отдельный канал связи!

Конечно, наш мини-интернет очень далек от реальности. Что, если у нас не три компьютера, а целая сеть из десятков, сотен, тысяч машин? Скорость света по-прежнему позволит передавать информацию не напрямую, а по длинным цепочкам. Однако подсчет вероятностей значительно затруднится.

И вот тут опять понадобится математика! Задачи об устойчивости больших сетей требуют глубоких концепций и новых моделей на стыке комбинаторики и теории вероятностей. К счастью, необязательно вникать в длинные доказательства, чтобы понять основные идеи. О некоторых таких фундаментальных идеях, проникающих в самую суть устройства сетей и уже ставших классикой, мы расскажем в следующих разделах.

 

Случайные графы

Математическая теория, которая, в частности, позволяет ответить на вопрос об устойчивости больших сетей, возникла на рубеже 50–60-х годов XX века. Ее авторами стали два замечательных венгерских математика Пол Эрдеш и Альфред Реньи.

Эрдеш – настоящий классик современной комбинаторики, теории чисел, теории вероятностей. Он написал более полутора тысяч статей, решил множество проблем и еще больше поставил задач, которые определили пути развития науки на долгие годы. Реньи – выдающийся венгерский специалист по теории вероятностей. Его именем назван математический институт в Будапеште, подобно тому как математический институт в Москве носит имя Владимира Андреевича Стеклова.

Пол Эрдеш

Пол Эрдеш (1913–1996) очень необычная фигура в математике. Он написал около 1500 статей с 509 соавторами.

Практически вся его собственность умещалась в один чемодан. Деньги его совсем не интересовали. Он жил в дороге, ездил с одной конференции на другую или останавливался у коллег. Рассказывают, что он появлялся на пороге и говорил: «Мой мозг открыт». Затем он работал с хозяевами несколько дней, получал результаты для нескольких статей и ехал дальше, в следующий дом и к другим задачам.

Его соавтор Фэн Чжун написала в своих воспоминаниях: «Все 83 года своей жизни он был абсолютно верен себе. Его не соблазняли посты и деньги. Большинство из нас окружили себя множеством земных благ и обязательств. Каждая встреча с ним напоминала мне, что это все-таки возможно, вот так идти за своей мечтой, не обращая никакого внимания на мелочи жизни. Именно по этому качеству дяди Пола я скучаю больше всего».

В математике, как в искусстве или моде, есть индивидуальные стили и вкусы. Соавторы Эрдеша рассказывают, что ему удавалось найти задачи, подходящие именно для них. Так хорошо он понимал своих соавторов и столько разных задач у него было в запасе! Результаты Эрдеша – разнообразные и в огромном количестве – сильно повлияли на современную науку.

Среди математиков есть понятие число Эрдеша . Это количество соавторов, которые отделяют математика от Эрдеша. У соавторов Эрдеша число Эрдеша равно 1. У их соавторов, которые с Эрдешем не работали, число Эрдеша – 2. И так далее. Самое распространенное значение – 5, и очень редко у кого из математиков число Эрдеша равно 8 или больше.

У одного из нас число Эрдеша 3, а у другого 2. Мы оба работаем со случайными графами и вносим свой посильный вклад в решение пока нерешенных проблем.

Теория, основы которой заложили Эрдеш и Реньи, называется теорией случайных графов. А математическая модель, рассмотренная в их первых работах, носит имя случайный граф Эрдеша – Реньи. Конечно, эти графы не имеют ничего общего с князьями и баронами. Слово «граф» в данном случае имеет то же происхождение, что и слово «график», хорошо известное со школы. Граф – это просто рисунок.

Например, нашу мини-сеть из предыдущего раздела очень легко представить в виде графа. Мы это сделали на рис. 4.4 слева. Сеть изображена в виде трех узлов (компьютеров), которые соединены линиями (каналами связи). В математике узлы называются вершинами графа, а линии между ними – ребрами. Чтобы не затруднять восприятие абстрактными терминами, мы в основном будем пользоваться более интуитивными терминами «узлы» и «линии».

Рис. 4.4. Слева: мини-сеть в виде графа. Узлы – это компьютеры, а линии – каналы связи. Справа: социальная сеть из в виде графа. Узлы – это люди, а линии – «дружба» в социальной сети

В мы вернемся к графам, когда будем обсуждать социальную сеть. В этом случае узлы – это люди, а линии между ними – «дружба» в социальной сети. Мы изобразили пример графа из на рис. 4.4 справа.

Естественно, узлов у графа может быть и тысяча, и миллион, и миллиард…

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

У случайных графов есть еще одна особенность. Нам неизвестно заранее, какие узлы связаны линией, а какие – нет. Линии между узлами могут существовать или нет с определенной вероятностью. Именно эту ситуацию мы обсуждали в примере с мини-сетью. При наличии помех канал связи становится недоступным, линия между узлами исчезает.

Случайный граф – естественная модель во многих ситуациях. Например, дружба в социальных сетях возникает непредсказуемым образом. В телекоммуникациях или электрических сетях на линиях связи могут случаться сбои. Если попытаться смоделировать нейронную сеть мозга, то взаимодействия нейронов можно выявить только с определенной вероятностью.

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

Что же говорит теория случайных графов об устойчивости сети?

 

Результат Эрдеша – Реньи

В связи с устойчивостью интернета нас интересует вопрос о связности случайного графа. Граф называется связным, если между двумя любыми его вершинами можно пройти по цепочке ребер, то есть все узлы связаны друг с другом. Оба графа на рис. 4.4 – связные. На рис. 4.5 мы сделали их несвязными, удалив по два ребра.

Рис. 4.5. Слева: мини-сеть в виде графа; каналы 1–2 и 1–3 недоступны; граф несвязный, из вершины 1 нельзя попасть в вершины 2 и 3. Справа: социальная сеть в виде графа; пользователь 1 не знаком с пользователями 5 и 6; граф несвязный; нет цепочки знакомых между пользователями 5, 6 и остальными

Эрдеш и Реньи задались вопросом: при какой вероятности помех сеть заданного размера остается связной? Результат получился поразительным! Оказывается, в больших сетях связность сохраняется даже при повышенной вероятности помех.

Например, возьмем сеть из 100 связанных между собой компьютеров. Получается, что каждый отдельный канал может быть недоступен с вероятностью аж 86 %, тем не менее сеть останется связной с вероятностью как минимум… 99 %! Эта ситуация изображена на рис. 4.6: 86 % из всех возможных линий отсутствует, однако сразу видно, что из любого узла можно добраться до любого другого.