Расчеты COVID раскрывают решение 30-летней проблемы информатики

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статья “Цельнозерновые сети Петри и процессы” только что была опубликована Журнал АКМ.