Departamento de Computación

Texto completo de la Conferencia   

Clásicamente se consideran intratables los problemas que sólo se saben resolver en tiempo exponencial, que es enorme. Pero en la práctica ya son intratables problemas que trabajan con secuencias biológicas y que sólo sabemos resolver en tiempo cuadrático, porque el ADN es muy largo y cuadrático aquí es demasiado, es lo que se llama complejidad de grano fino o "fine-grained complexity". Queremos asegurarnos de que los problemas relacionados con alineamiento de dos secuencias, por ejemplo, son intratables cuando ponemos el listón de tiempo en el poco del que disponemos para casos de estudio tan grandes. Por el camino hablaremos del SARS-CoV-2 que causa el COVID-19 como caso de estudio.
 

Elvira Mayordomo (Zaragoza, 1967) es catedrática de Lenguajes y Sistemas Informáticos de la Universidad de Zaragoza y presidenta de la Asociación Científica "Computability in Europe" (CiE). Es también colaboradora asociada de la Iowa State University, de EE.UU. Sus temas de investigación incluyen teoría de la información algorítmica, complejidad computacional, geometría fractal algorítmica, filogenética computacional y genómica computacional. Asimismo, es associate editor of ACM Transactions on Computation Theory, managing editor of Computability, y associate editor of Theory of Computing Systems.