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

«Как и многие другие, я хотел просчитать, как будет развиваться эпидемия. Я хотел исследовать некоторые идеи из теоретической информатики в этом контексте. Однако я понял, что отсутствие решения старой проблемы было препятствием», — говорит Йоахим Кок, доцент кафедры математики Копенгагенского университета.

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

Умный метод, изобретенный немецким подростком

Чтобы понять прорыв, нужно знать, что такие сложные системы можно математически описать с помощью так называемых сетей Петри. Метод был изобретен в 1939 году немцем Карлом Адамом Петри (кстати, в возрасте всего 13 лет) для применения в химии. Подобно тому, как здоровый человек, встречающийся с человеком, инфицированным COVID, может вызвать изменение, то же самое может произойти, когда два химических вещества смешиваются и вступают в реакцию.

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

Простая версия сети Петри для заражения COVID. Отправной точкой является незараженный человек. «S» означает «чувствительный». Контакт с инфицированным человеком («Я») — это событие, которое приводит к заражению двух человек. Позже произойдет еще одно событие, удаляющее человека из группы зараженных. Здесь «R» означает «выздоровевший», который в этом контексте может быть либо вылечен, либо мертв. В любом случае человек будет удален из зараженной группы.

Ученые-компьютерщики сочли проблему неразрешимой

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

Иоахим Кок имел в виду применение более индивидуально ориентированных сетей Петри из информатики для расчетов COVID. Это было, когда он столкнулся со старой проблемой:

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

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

«Проблема заключалась в том, что никто не смог объединить два подхода. Компьютерщики более или менее смирились, считая проблему неразрешимой. Это произошло потому, что никто не понял, что нужно вернуться назад и пересмотреть само определение сети Петри», — говорит Иоахим Кок.

Небольшая модификация с большим эффектом

Датский математик понял, что небольшая модификация определения сети Петри позволит решить проблему:

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

Точная математическая причина, по которой эта дополнительная информация важна, сложна, но ее можно проиллюстрировать аналогией:

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

Точно так же информация теряется, когда отдельные стрелки сети Петри заменяются числом.

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

Круг до COVID замкнулся

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

«Это связано с тем, что необходимые модификации в основном обратно совместимы и могут применяться без необходимости пересмотра всей теории сети Петри».

«Несколько удивительно, что некоторые эпидемиологи начали использовать пересмотренные сети Петри. Так что, можно сказать, круг замкнулся!»

Иоахим Кок видит в этой истории еще один момент:

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