Автор книги: Нелли Литвак
Жанр: Математика, Наука и Образование
Возрастные ограничения: +12
сообщить о неприемлемом содержимом
Текущая страница: 1 (всего у книги 11 страниц) [доступный отрывок для чтения: 3 страниц]
Нелли Литвак, Андрей Райгородский
Кому нужна математика? Понятная книга о том, как устроен цифровой мир
Все права защищены. Никакая часть настоящего издания ни в каких целях не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами, будь то электронные или механические, включая фотокопирование и запись на магнитный носитель, если на это нет письменного разрешения издателя.
© Н. Литвак, А. Райгородский, 2016
© Издание, оформление. ООО «Манн, Иванов и Фербер», 2017
* * *
Введение
О чем эта книга
В этой книге мы расскажем о некоторых современных приложениях математики. Мы выбрали семь тем, по одной на каждую главу:
1) задачи планирования и составление расписаний (глава «Менеджмент и многогранники»);
2) кодирование текстов для хранения и передачи в цифровом виде (глава «Мир нулей и единиц»);
3) структура соединения серверов каналами связи в интернете (глава «Надежность интернета»);
4) балансирование нагрузки в телекоммуникациях (глава «Сила выбора из двух»);
5) шифрование конфиденциальных сообщений (глава «Секретные числа»);
6) операции подсчета при анализе больших данных (глава «Счетчики с короткой памятью»);
7) распределение рекламных мест в поисковых системах, таких как Google и «Яндекс» (глава «Миллион аукционов в минуту»).
Мы ни в коем случае не претендуем на хоть сколько-нибудь полный обзор бесчисленных приложений математики. На это понадобится не одна книга, а целая библиотека! Например, мы вообще не упоминаем о медицинских приложениях, скажем, о создании подвижной трехмерной картинки на экране при компьютерной томографии или нахождении мутаций в геномах клеток рака. Мы также не касались приложений в высокотехнологичном производстве, например в машиностроении и авиации, и широкого спектра применений в экономике.
Выбранные нами темы объединены одной идеей. Все они связаны с компьютерами и интернетом. Мы хотим на ярких и конкретных примерах показать, что сам по себе компьютер, даже самый мощный, не способен творить ставшие уже столь привычными для нас чудеса: показывать тексты и фотографии, делать сложные расчеты, искать информацию и пересылать данные по всему миру. За всем этим стоит математика; без нее компьютер остался бы просто безжизненным и практически бесполезным устройством.
Конечно, даже эту тему невозможно полностью раскрыть в одной книге. Мы выбрали лишь несколько наиболее близких к теме наших собственных исследований примеров. Если бы эту книгу писали другие авторы, то и темы были бы другими, но не менее впечатляющими.
Мы очень хотим разделить с вами если не наше увлечение, то хотя бы наше восхищение математикой – точной и красивой, древней и всегда современной и, безусловно, невероятно полезной!
Для кого эта книга
Эта книга написана для широкого круга читателей и не требует специальной подготовки. При этом для наиболее заинтересованных и подготовленных читателей мы добавили, кроме основного текста, дополнительные объяснения и приложения.
Основной текст. Основной текст книги не требует абсолютно никакой математической подготовки. Мы постарались писать его так, чтобы он был интересен и понятен каждому читателю. В каком-то смысле наш рассказ можно сравнить с научно-популярными телевизионными программами.
Дополнительные объяснения. Иногда для интересующегося читателя мы объясняем основные идеи чуть более подробно. Этот текст мы приводим во врезках. В основном он не требует математической подготовки. Но при желании его можно пропустить без ущерба для понимания остального содержания главы.
Приложения[1]1
Мы включили в книгу приложения для подготовленного читателя, чтобы ее можно было использовать в качестве учебника, например для спецкурса в старших классах или для вводных лекций в вузе.
[Закрыть]. В конце книги мы поместили приложения к каждой главе, где приводим более строгие математические формулировки, включая формулы, теоремы и доказательства (или хотя бы идеи доказательств). Сноски на них ищите в соответствующих главах. Приложения рассчитаны на уровень старшеклассников, увлекающихся математикой.
Глава 1
«Кому-то еще нужна математика?»
Нелли
После долгого перелета и полуторачасового стояния в очереди я наконец предъявляю паспорт и кладу указательный палец на маленький сканер в аэропорту Атланты. Унесенные ветром…
– С какой целью вы приехали в США? – в голосе пограничника нет ни капли интереса.
– Я приехала на конференцию.
– Какую?
– По математике.
Со мной все ясно, пограничник ухмыляется и берется за печать:
– И что, кому-то еще нужна математика?
Нет, вы только подумайте! Он сидит в аэропорту Атланты, где буквально каждые десять минут приземляется самолет, сканирует мой паспорт, компьютер в долю секунды находит мои отпечатки пальцев среди миллионов других отпечатков и сравнивает мой файл с сотнями тоненьких линий на маленьком сканере. Каким образом, хотелось бы знать, было решено, во сколько, куда и какой самолет должен садиться? Как сохранить отпечатки пальцев в компьютере, который хоть и показывает на экране всякие картинки, на самом деле не умеет хранить ничего, кроме нулей и единиц? Как быстро найти нужную запись среди миллионов других? И как компьютер – кучка пластмассы и железа – может решить, совпадают ли две картинки, отфильтровав при этом неизбежные помехи и неточности?
Можно копать и дальше, разбираясь в конструкции самолета (максимальная прочность при минимальном весе), вникать в таинственную систему определения стоимости билетов и так далее и тому подобное. И ничего этого – заметьте, абсолютно ничего! – нельзя было бы сделать без математики. Самолеты, цены, линии на пальцах – все это описано с помощью переменных, функций и уравнений. И для всех этих задач найдены эффективные и точные способы решения. Потому что у компьютера нет глаз, и при этом он должен узнать мой отпечаток пальца быстро и безошибочно. Целая команда математиков могла бы работать всю жизнь, занимаясь исключительно проблемами, связанными с аэропортом Атланты.
Я беру свой паспорт и улыбаюсь пограничнику:
– Конечно нужна!
Развивать дискуссию бесполезно. И потом, при всей бессмысленности вопроса не его вина, что он представляет себе математику как бесконечный ряд никому не нужных экзерциций с числами и формулами. И уж конечно, не он один такой.
Недавно я обсуждала эту ситуацию на занятии со студентами-математиками. Вас спрашивают: где вы учитесь? Вы отвечаете: на прикладной математике. Вас спрашивают: и зачем это нужно? В аудитории смущенные понимающие улыбки. Каждый не раз слышал этот вопрос.
Я считаю, что математика должна быть либо красивой, либо полезной. А лучше – как это часто бывает в настоящей науке – и то и другое! Наверное, без специальной подготовки красоту математики понять довольно сложно. Но мне кажется удивительным, что в эпоху цифровых технологий широкой публике так мало известно о невероятной полезности математики. Скептицизм американского пограничника – скорее правило, чем исключение. В этой книге мне хотелось понятно и интересно рассказать именно о пользе математики. Ну и о красоте, конечно, тоже. Надеемся, читатель сможет ее увидеть и оценить.
Андрей
В моей семье многие имели отношение к математике. Мама с папой, например, познакомились в МИИТе, где мама училась на факультете прикладной математики, а папа – на автоматизации систем управления (так тогда называли программистские факультеты). Папа в свое время учился в знаменитой 2-й школе. А мамин папа, мой дедушка, перед самой войной окончил мехмат МГУ и потом всю жизнь работал над расчетами траекторий космических аппаратов (скажем, тех же первых луноходов) сначала у Королева в Подлипках, потом у Лавочкина в Химках. Он, пожалуй, и оказал на меня наибольшее влияние. Я тоже учился на мехмате МГУ. Там на мой выбор математики в качестве профессии радикально повлиял мой научный руководитель – Николай Германович Мощевитин.
До мехмата я учился в школе с французским уклоном и любил многие предметы. Меня интересовали языки – в том числе с точки зрения лингвистики. В старших классах я имел возможность сменить школу на школу с математическим уклоном, но сознательно предпочел остаться и доучить французский.
Я не считаю, что математика – это естественная наука, как физика, химия или биология. Это некий вид искусства. Знаменитый математик Эрдеш говорил, что у Бога есть книга, в которой содержатся идеальные математические доказательства, «доказательства из книги». Я тоже думаю, что математика открывает истины, содержащиеся в идеальном мире, и только потому она и имеет приложения, что видит «высшую реальность», проекцией которой служит этот мир. Иными словами, не математику оправдывают ее приложения (она прекрасна сама по себе), они возникают за счет того, что так устроен мир, и математика как раз об этом, об устройстве мира.
Моя наука – комбинаторика – замечательна тем, что делает очень многие формулировки и доказанные сложные результаты понятными даже школьнику, интересующемуся математикой. Поэтому рассказывать о ней исключительно круто. Однако эта наука богата и задачами, которые при всей простоте своих постановок пока совершенно не поддаются решению. В книге мы рассмотрим некоторые из них: они до сих пор остаются открытыми, несмотря на их актуальность.
Лучший ответ на вопрос «Кому нужна математика?»
Пожалуй, приз за лучший ответ на вопрос «Кому нужна математика?» можно смело отдать выдающемуся немецкому математику по имени Мартин Гротшел. Не гарантируем точности изложения, но байка, которую рассказывают на конференциях, звучит так:
Как-то раз немецкое правительство решило выделить целевым образом значительные суммы на развитие самых передовых и необходимых областей науки. На заседание государственной комиссии были приглашены физики, химики, биологи – представители всех наук. Гротшел представлял математику. Все ораторы с огромным энтузиазмом рассказывали о необыкновенных достижениях своей науки и том, как без нее мир и Германия рухнут. Естественно, все докладчики выходили за рамки отпущенного времени. Гротшел выступал последним. Заседание уже подходило к концу, чиновники сидели осоловевшие от обрушенного на них потока информации. Гротшел вышел на трибуну и сказал примерно следующее:
– Уважаемые господа! Я не буду утомлять вас длинной речью, а просто приведу пример. Недавно мы получили заказ от большой страховой компании, планирующей создать автосервис для своих клиентов. Идея очень проста: если у клиента в дороге сломалась машина, он может позвонить по телефону и к нему тут же приедет аварийная служба. Вопрос в том, как правильно организовать такой сервис. В принципе, задачу можно решить довольно просто – например, приставить к каждому клиенту личную аварийную машину с механиком. Тогда клиент в любой момент немедленно получит помощь. Но это очень дорого! Другой вариант – вообще не связываться с аварийным сервисом. Клиенты могут ждать до бесконечности, зато это не будет стоить им ни цента. Так вот. Если вас эти решения не устраивают, то я должен вам сообщить, что для любых других вариантов понадобится математика! Спасибо за внимание.
Нужно ли говорить, что математика получила колоссальные правительственные субсидии. Результаты этих инвестиций во всех областях, от транспорта до медицины, абсолютно потрясающие!
Кстати, среди студентов Нелли приз за лучший ответ получила Клара, которая сказала, что без математики невозможно было бы составить расписание поездов и они все время сталкивались бы друг с другом. О расписаниях поездов мы подробнее расскажем в главе 2, а пока немножко поговорим о том, чем занимаются профессиональные математики, от выпускников вуза в компаниях до ведущих ученых-теоретиков.
Математика на каждый день
На выпускников с дипломом математика в Европе большой спрос. Даже средненькие студенты легко находят работу. Причем они далеко не всегда становятся программистами, даже если их компания и производит программное обеспечение. Оптимальный красивый код – это задача инженеров-программистов. Задача математиков – придумать методы решения проблемы.
Сфера деятельности математиков очень широкая: логистика, планирование, высокотехнологичное производство, биомедицинские технологии, финансы.
Бывший коллега Нелли защитил диссертацию по финансовой математике, а потом пошел работать в компанию. «Мы управляем активами пенсионных фондов на рынке ценных бумаг. Многие думают, что это занятие типа купи-продай. А я тут сижу и целыми днями решаю дифференциальные уравнения. И ребята, которые торгуют, сидят тут же, в трех метрах от меня. Вот сейчас досчитаю и скажу им, что покупать».
Среди ученых-математиков есть те, кто напрямую работает с приложениями. Мор Харкол-Балтер из университета Карнеги – Меллон говорит, что все ее исследования основаны на приложениях. Например, в 2011 году она сотрудничала с «Фейсбуком». По оценкам Мор, «Фейсбук» задействовал свои включенные серверы не более чем наполовину, а остальное время они простаивали. Включенный и незадействованный сервер тратит примерно две трети энергии работающего сервера. Но компании боятся выключать серверы, потому что чем их больше, тем быстрее они справляются с запросами пользователей. При этом на включение сервера уйдет 4–5 минут, а «Фейсбук» хочет выполнять запрос за полсекунды! Однако Мор не сомневалась, что серверы можно спокойно отключать. Из математической теории – теории массового обслуживания – ясно следовало, что если серверов много (а у «Фейсбука» их очень много!), то время, затраченное на включение, не оказывает никакого влияния. Мор и ее ученики разработали метод, при котором серверы включались и выключались без какого-либо ущерба для пользователей. «Фейсбук» последовал рекомендациям и, по утверждению компании, теперь экономит 10–15 % энергии.
Профессора университета Твенте Ричард Бушери и Эрвин Ханс и их ученики занимаются логистикой здравоохранения. В результате их исследований в больницах Нидерландов произошли существенные изменения. Например, больница в Роттердаме раньше всегда держала наготове специальную операционную для экстренных операций. Большую часть времени операционная пустовала, драгоценное время тратилось впустую. Но менеджмент опасался, что в противном случае экстренным пациентам придется ждать слишком долго. При этом им все равно приходилось ждать, скажем, если вдруг привозили сразу двух экстренных пациентов. Математические подсчеты показали, что правильно составленное расписание плановых операций (еще одна нетривиальная задача!) позволяет быстро принять практически всех экстренных пациентов. В результате экстренную операционную упразднили и отдали под плановые операции.
Многие математики работают с приложениями, но далеко не все настолько вплотную, как в приведенных выше примерах. Разработка новых теорий важна для практики не меньше, чем решение непосредственных практических задач. Об этом мы поговорим подробнее в следующих разделах.
Новые теории для современной практики
В 2008 году международное статистическое сообщество отпраздновало столетие со дня появления распределения Стьюдента. Стьюдент – это псевдоним очень талантливого математика по имени Вилльям Госсет. Госсет работал на пивоваренном заводе «Гиннесс» в Дублине. Его исследования в области статистики имели чисто коммерческие цели: они применялись при тестировании качества сырьевых продуктов, из которых делали пиво. Госсету не разрешалось публиковать труды по статистике под собственным именем, поэтому он публиковался под псевдонимом Стьюдент. Госсет вывел новое распределение вероятностей (распределение Стьюдента) и на его основе разработал теперь уже классическую статистическую процедуру, знаменитый t-тест.
t-тест обычно используется при необходимости сравнить случайную выборку с какой-то нормой или две случайные выборки между собой. Например, вы выпускаете шурупы и хотите проверить, соответствуют ли они норме по длине. Или вам нужно сравнить урожайность при использовании двух разных видов удобрений. Такие тесты широко применяются на практике, для них разработано стандартное программное обеспечение, t-тест не проходят разве что на филфаке.
За 100 лет статистика ушла далеко вперед. Сара ван де Гейр, профессор Швейцарской высшей технической школы Цюриха, работает над тестами с многомерными данными. Задача, так же как и задача Госсета, пришла из практики. Компания DSM в Швейцарии выпускает витамины и пищевые добавки. Витамин В2 производится с помощью бациллы сенной палочки. Компания хочет увеличить выпуск витамина благодаря генной инженерии. Имеются измерения производительности 115 бактерий, генный состав которых включает 4088 возможных генов. Спрашивается, какие гены способствуют росту производства витамина В2?
Это очень сложная задача, учитывая, что данных мало, а параметров много, причем все они взаимосвязаны. Существующие теории для этого случая не подходят, поэтому Сара и ее сотрудники сосредоточились на создании новых теорий. Это очень сложная математика, доступная только специалистам. Но то же самое сто лет назад можно было сказать и о работе Госсета! И мы совершенно не удивимся, если статистические процедуры, разработанные Сарой, через пару десятков лет займут свое место в университетских учебниках по статистике и задачка про сенную палочку будет предложена студентам-биологам на экзамене. Когда мы поделились этими мыслями с Сарой, она абсолютно серьезно сказала: «Конечно, очень скоро это будет стандартная статистика».
Поскольку современная реальность постоянно усложняется, существующего математического аппарата часто не хватает. И это, безусловно, мощный стимул для появления новых задач и теорий.
Математика неизвестного будущего
Не все математические задачи взяты из практики. Так и должно быть, потому что мы не можем с уверенностью предсказать пути развития общества и технологий даже в ближайшем будущем. Это не по силам даже самым информированным людям с совершенно неуемной фантазией. Например, хорошо известно, что писатели-фантасты практически ничего не сумели предугадать. В основном они описывали технологии своего времени, приукрашивая их фантастическими деталями.
Никто не предрек появления интернета. Наоборот, Нобелевский лауреат Деннис Габор, изобретатель голографии, в 1962 году заявил, что передача документов по телефону хоть и возможна в принципе, но требует таких огромных расходов, что эта идея никогда не найдет практического воплощения. При этом первый успешный модем был представлен в том же году! А Кен Олсен, один из создателей Digital Equipment Corporation (DEC), в 1977 году сказал, что вряд ли найдется человек, которому может дома понадобиться компьютер. Через сколько лет после этого компьютер появился в вашем доме?
Никто не знает, какая абстрактная теория завтра может найти практическое применение. Потрясающий пример – теория чисел, область математики, изучающая числа и их закономерности. Теория чисел оставалась абстрактной наукой со времен Древней Греции до второй половины XX века. Сегодня эта теория широко используется для шифрования сообщений, передаваемых через интернет. Именно благодаря ей сохраняется конфиденциальность ваших паролей и номеров кредитных карточек, когда вы вводите их на многочисленных сайтах. Мы расскажем об этом подробнее в главе 7.
Наконец, нам трудно удержаться от еще одного варианта ответа на вопрос, зачем нужны новые сложные теории. Да просто ради красоты этих теорий! Красивая математика имеет полное право на существование. В научном мире должно оставаться что-то от Касталии Германа Гессе, где ученым разрешено заниматься чем угодно, где целью жизни может стать «игра в бисер»[2]2
Отсылка к знаменитому одноименному роману лауреата Нобелевской премии Германа Гессе. Прим. ред.
[Закрыть] – «самая блистательная и самая бесполезная». Почему? Потому что нельзя поставить науку полностью на службу материальным нуждам общества. Наука выполняет функцию просветительства. Это единственная сфера деятельности, в которой человек может работать, движимый исключительно непрактическим любопытством. Грубо говоря, наука делает мир умнее и нужна человечеству так же, как и искусство, которое делает мир более духовным.
Глава 2
Менеджмент и многогранники
Компьютерные будни логистики
На специальности «Прикладная математика» в основном обучают математике. Доля программирования не так уж велика по сравнению с бесконечным матанализом, алгеброй и матфизикой. При этом выпускники часто становятся программистами.
– Интересно, насколько тебе нужна вся эта математика? – спросила Нелли у друга и бывшего однокурсника, а сегодня системного администратора в международной компании. Тот не задумался ни на секунду:
– Конечно нужна! Вот недавно клиенты заказали программу для распределения товаров по вагонам. Мы сразу поняли, что такую задачу ежедневно решают все поставщики всех товаров. Значит, она известная. Через полчаса мы уже знали, что это «задача об упаковке», и могли предложить несколько решений. Кстати, клиентам пришлось объяснять, что задача NP-трудная, то есть мы не можем гарантировать самое лучшее из всех возможных решений. И они согласились. А что им оставалось?
Вся современная логистика основана на математических методах. Где расположить склады и сервисные пункты? Как распределить товары по вагонам и грузовикам и какими маршрутами все это отправить? Сколько товара держать на складе и как часто его пополнять? Как составить расписание поездов, самолетов, большого производства и даже спортивных соревнований?
Этими вопросами занимается область прикладной математики под названием исследование операций. По большому счету это наука о том, как оптимально организовать процессы бизнеса и производства. Сюда, безусловно, относится логистика, а также многие другие задачи, например из области финансов или телекоммуникаций.
Исследование операций начало развиваться относительно недавно, после Второй мировой войны. И далеко не сразу научные результаты нашли практическое применение. В 2002 году в специальном юбилейном выпуске в честь 50-летия журнала «Исследование операций» Чарльз Холт делится своими воспоминаниями о том, как он и его коллеги Франко Модильяни, Джон Муф и Герберт Симон разрабатывали и внедряли научные методы планирования производства:
Мы взяли интервью у менеджеров пятнадцати компаний. Поначалу менеджеры отрицали наличие каких-либо проблем. По крайней мере таких, с которыми коллеги-профессора могли хоть как-то помочь. Но когда мы расспрашивали более подробно, возникали картины наподобие телеги на разваливающихся колесах – системы, катящиеся без всякого контроля от одного кризиса к другому{1}1
Holt Charles С. Learning how to plan production, inventories, and work force // Operations Research, 50(l):96–99, 2002.
[Закрыть].
В процессе работы все менеджеры постепенно переключились на систему «коллег-профессоров». Команда написала книгу «Планирование производства, инвентаря и трудовых ресурсов». Модильяни и Симон получили Нобелевские премии по экономике, а работы Муфа легли в основу исследований Роберта Лукаса, тоже впоследствии лауреата Нобелевской премии.
Методы исследования операций глубоко внедрились в современный бизнес. Никому не придет в голову планировать большое производство или составлять расписание самолетов вручную. Для этого есть подготовленные специалисты и стандартное коммерческое программное обеспечение. Даже самый элементарный подход в рамках исследования операций всегда превзойдет любое решение «на глазок». Исследование операций преподают не только на факультетах прикладной математики, но и в бизнес-школах.
В этой главе мы расскажем о задачах оптимизации, которые, в частности, возникают при планировании и составлении расписаний.
Правообладателям!
Данное произведение размещено по согласованию с ООО "ЛитРес" (20% исходного текста). Если размещение книги нарушает чьи-либо права, то сообщите об этом.Читателям!
Оплатили, но не знаете что делать дальше?
