TecnoXplora» SINC

EN LA AUTÓNOMA DE BARCELONA

Resuelven un viejo problema de teoría de la computación a partir del estudio del covid

Al inicio de la pandemia, un matemático de la Universidad Autónoma de Barcelona empezó a experimentar con modelos epidemiológicos. No logró mejorar las predicciones, pero resolvió una cuestión abierta desde la década de 1980 en informática teórica sobre las redes de Petri.

Resuelven un viejo problema de teoria de la computacion a partir del estudio de la covid

Resuelven un viejo problema de teoria de la computacion a partir del estudio de la covidSinc

Publicidad

Uno de los modelos matemáticos más simples y más utilizados para describir epidemias es el llamado modelo SIR. El modelo considera a la población compartimentada en tres grupos: las personas sanas (S), las personas infectadas (I) y las personas recuperadas e inmunes (R). También estipula que hay dos transiciones posibles entre estos grupos: una tiene lugar cuando una persona sana se convierte en una infectada porque se ha encontrado con otra que lo estaba –ambas pasan a ser personas infectadas– y la otra transición pasa cuando una persona infectada se recupera.

La red de Petri cuenta con compartimentos (los grupos de personas) y transiciones (cambios de un grupo a otro)

Este modelo puede ser analizado matemáticamente mediante una herramienta llamada red de Petri, un tipo de red que cuenta con compartimentos (los grupos de personas) y transiciones (los cambios de un grupo a otro), con flechas ponderadas para describir las relaciones entre compartimentos y transiciones (véase la figura). A partir de la red de Petri con los parámetros que indican con qué tasa se efectúan las transiciones (estimados experimentalmente), el modelo describe la evolución de los compartimentos y, por tanto, de la epidemia.

Acerca de las redes de Petri, había un viejo problema de la informática teórica abierto desde la década de 1980 que, de manera inesperada, fue resuelto gracias a los trabajos de modelización de la Covid, realizados por el investigador de la Universitat Autònoma de Barcelona (UAB), Joachin Kock. La investigación ha sido publicada recientemente en la prestigiosa revista Journal of the ACM.

Individuos en lugar de grupos

Cuando al inicio de la pandemia Kock empezó a modelizar la COVID-19 mediante redes de Petri, quería experimentar con la posibilidad de considerar a las personas no como grupos estadísticos sino como individuos, una idea inspirada en la informática teórica. En este ámbito, las redes de Petri consideran un número determinado de fichas en cada compartimento, que se mueven de acuerdo con las transiciones, de modo que una transición puede tener lugar si hay suficientes fichas en los compartimentos de entrada: se consumen fichas en los compartimentos de entrada y se producen nuevas en los de salida.

En esta disciplina, el uso más importante de las redes de Petri se da como modelo de la computación concurrente, pero este estudio presentaba un viejo problema irresuelto. Este radica en que existen dos formas distintas de razonar matemáticamente sobre estas redes como modelo de concurrencia, dos 'semánticas' que no se habían podido reconciliar: una semántica algebraica y una geométrica, con sus ventajas e inconvenientes.

Para encontrar una solución, el profesor de la UAB revisó la teoría de las redes de Petri y descubrió que era necesario modificar la propia definición

Simular la COVID-19 con las redes de Petri que se utilizan en computación con el fin de considerar individuos "no fue una buena idea desde el punto de vista de la epidemiología", explica Kock, "porque el formalismo de estas redes no permitía trazar a las personas individualmente". Esta "obstrucción" resultó ser la misma que impedía reconciliar las semánticas algebraica y geométrica, lo que devolvía a los científicos al viejo problema de las redes de Petri.

Para encontrar una solución, el profesor de la UAB revisó toda la teoría de las redes de Petri y descubrió que era necesario modificar ligeramente la propia definición para que estas redes admitieran flechas paralelas en lugar de pesos, es decir, pasar de un número que representa el peso de una flecha a un conjunto de flechas con ese número de elementos.

"En la teoría de homotopía, uno de mis campos de investigación, este tipo de consideración es habitual", concreta Kock. "En este caso, al introducir los conjuntos de flechas aparecen formas de reordenarlas y simetrías que no existen si tenemos en cuenta solo el peso como número, como sucede en la definición convencional".

Experimentar con ideas sin saber adónde llevan

Lo que faltaba en las redes de Petri convencionales era exactamente el acceso a la información de las simetrías de una red que proporciona la definición de Kock."Con algo de teoría de homotopía y teoría de categorías, demostré que la nueva versión de las redes de Petri admite una reconciliación de las dos semánticas, la algebraica y la geométrica", en sus propias palabras.

La nueva definición propuesta por el investigador del Departamento de Matemáticas de la UAB ya ha sido utilizada por otros investigadores (Evan Patterson y su equipo en Berkeley, EE. UU.) para desarrollar un programa informático basado en redes de Petri, con el objetivo de modelizar epidemias como la de Covid.

"De esta forma se cierra el círculo. La matemática abstracta ha permitido transferir conocimientos y experiencia de una ciencia a otra, en este caso de forma inesperada. Busqué una cosa y he acabado encontrando otra muy distinta. A veces es productivo experimentar con ideas que no se sabe exactamente hacia dónde te van a llevar", concluye Kock.

Referencia:

J. Kock. Whole-grain Petri Nets and Processes. Journal of the ACM (2023).

Publicidad