Йэн Стюарт – Это база: Зачем нужна математика в повседневной жизни (страница 20)

Если в схеме участвуют только циклы длины 2, то оптимальное множество обменов может быть вычислено за полиномиальное время, класс сложности P, с использованием стандартных методов построения паросочетаний с максимальным весом в графе. Если присутствуют и циклы длины 3, даже без доноров-альтруистов, задача оптимизации становится NP-трудной. Тем не менее Мэнлав с коллегами разработал работоспособный алгоритм на базе линейного программирования, о котором мы говорили в главе 3. Их алгоритм UKLKSS перестраивает задачу оптимизации так, чтобы ее можно решить при помощи последовательности вычислений по методу линейного программирования. Результат каждого расчета подается на вход следующего как дополнительное ограничение. Так что условие (1) оптимизируется; при этом используется метод, известный как алгоритм Эдмондса в реализации Сильвио Микали и Виджая Вазирани. Алгоритм Эдмондса находит максимальное покрытие в графе за время, пропорциональное числу ребер, умноженному на квадратный корень из числа вершин. Покрытие связывает пары вершин на концах общего ребра, и задача в том, чтобы покрыть как можно большее число пар вершин без использования двух ребер, которые имеют одну общую вершину.

После того как оптимизация по условию (1) проведена, полученное решение оптимизируется по условию (2) с использованием алгоритма, известного как целочисленный программный решатель COIN-Cbc, части библиотеки алгоритмов проекта Вычислительной инфраструктуры для исследования операций, и т. д.

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

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

Мечта Лейбница осуществилась в XX веке после весьма существенных достижений XIX века. Мы сегодня называем эту область математики топологией, и в главе 13 я покажу некоторые ее новые применения. Теория графов по-прежнему не теряет связи с топологией, но их развитие шло разными путями. Такие понятия, как вес ребра, имеют численный, а не топологический характер. Но идея о том, что графы можно использовать для моделирования сложных взаимодействующих систем и решения задач оптимизации, восходит к Эйлеру. Он занялся вопросами нового типа потому, что они захватили его воображение, и придумал собственные способы поиска ответов на них. Произошло это в Санкт-Петербурге, в России, куда он приехал по приглашению недавно созданной Академии наук почти три столетия назад. Всякий, кому пересаживают почку, будь то в Великобритании или в любой другой стране, где пользуются методами теории графов для более эффективного распределения органов, должен восхищаться тем, что сделал Эйлер.

5

Будьте осторожны в киберпространстве

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

Пьер де Ферма знаменит своей Великой теоремой, которая гласит, что если n равно по крайней мере 3, то сумма двух n-х степеней целых чисел не может также быть n-й степенью целого числа. Эндрю Уайлс в конечном итоге нашел этому современное формальное доказательство в 1995 году, примерно 358 лет спустя после того, как Ферма высказал свою гипотезу{39}. По профессии Ферма был юристом, советником парламента в Тулузе, но большую часть времени посвящал математике. У него был друг по имени Френикль де Бесси, парижский математик, известный прежде всего полным каталогом 880 магических квадратов четвертого порядка. Они активно переписывались, и 18 октября 1640 года Ферма написал де Бесси (по-французски), что «каждое простое число делит… одну из степеней любой прогрессии за вычетом единицы, а показатель этой степени делит данное простое число за вычетом единицы».

Если перевести этот текст на алгебраический язык, то Ферма утверждал, что если p – простое число и a – произвольное число, то a^p–1–1 делится на p (без остатка). Например, поскольку 17 – простое число, то, согласно его утверждению, все числа

1¹⁶–1 2¹⁶–1 3¹⁶–1 … 16¹⁶–1 18¹⁶–1…

кратны 17. Очевидно, 17¹⁶–1 придется пропустить: это число никак не может быть кратно 17, поскольку оно на единицу меньше такого числа, а именно 17¹⁶. Ферма понимал, что такое дополнительное условие необходимо, но не упомянул этого в письме. Проверим такой случай:

16¹⁶–1 = 18 446 744 073 709 551 615

и, разделив это число на 17, получим 1 085 102 592 571 150 095 ровно. Как вам такое?

Этот любопытный факт в настоящее время называют Малой теоремой Ферма, в отличие от Последней (или Великой) теоремы. Ферма был одним из пионеров теории чисел, изучающей глубокие свойства целых чисел. Как в его время, так и в последующие три столетия теория чисел представляла собой самую что ни на есть чистую математику. Она не имела важных применений, и было непохоже, чтобы они когда-нибудь появились. Один из ведущих специалистов Великобритании по чистой математике Годфри Харольд Харди, несомненно, думал именно так, о чем и заявил в своем небольшом шедевре – эссе «Апология математика», опубликованном в 1940 году. Теория чисел была для Харди одной из любимых областей математики, и в 1938 году он вместе с Эдвардом Мейтлендом Райтом выпустил классический труд «Введение в теорию чисел». В нем можно найти и Малую теорему Ферма – это Теорема 71 в главе VI. Мало того, вся глава, по существу, рассказывает о ее следствиях.

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

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