Sobre el grupo
KAPOW es un grupo de investigación en ciencias de la computación teóricas del ICC-CONICET y el Departamento de Computación de la UBA. Su foco está en problemas combinatorios sobre palabras (secuencias), aleatoriedad algorítmica, números normales y complejidad de Kolmogorov.
El equipo investiga preguntas abiertas sobre secuencias y sus propiedades de aleatoriedad. Define condiciones básicas de aleatoriedad combinatoriamente, particularmente a través del concepto de normalidad. Las actividades incluyen examinar la aleatoriedad bajo diferentes modelos computacionales (autómatas finitos, máquinas de Turing), convertir aleatoriedad entre alfabetos, garantizar independencia de secuencias aleatorias, y formalizar preguntas sobre secuencias naturales como genomas y proteínas. Colabora con el Laboratorio de Fisiología de Proteínas. Metodológicamente emplean teoría de grafos, teoría de autómatas, aritmética elemental, algoritmos eficientes, análisis de complejidad computacional, teoría de números, lógica y teoría de la computabilidad. KAPOW participa del IRP SINFIN.
Líneas de investigación (4)
Aleatoriedad algorítmica y números normales
Estudio combinatorio de la aleatoriedad mediante la noción de normalidad de secuencias y bloques, complejidad de Kolmogorov y dimensión de estados finitos.
Combinatoria sobre palabras y autómatas
Aleatoriedad respecto a modelos computacionales (autómatas finitos, máquinas de Turing), conversión entre alfabetos, secuencias de De Bruijn extendidas.
Análisis probabilístico de algoritmos
Estudio del comportamiento asintótico y promedio de algoritmos sobre estructuras combinatorias aleatorias.
Secuencias biológicas (genomas y proteínas)
Formalización y análisis de repeticiones máximas en secuencias genómicas; herramientas para encontrar repeticiones perfectas en genomas. Colaboración con Fisiología de Proteínas.
Proyectos (4)
-
PICT-2018-02315: Complejidad Temas Abiertos, tipo A
Investigación en temas abiertos de complejidad.
💰 ANPCyT (PICT) 📅 2020-2022 -
STIC-AmSud 20-STIC-06: Randomness and Probabilistic Analysis of Algorithms
Cooperación entre V. Becher (UBA), L. Lhote (ENSICAEN/Caen) y A. Viola (UdelaR).
💰 STIC-AmSud 📅 2020-2022 -
ECOS PA17C04: Randomness and finite-state machines
V. Becher (UBA) y O. Carton (Université Paris Diderot).
💰 ECOS-Sud 📅 2018-2022 -
UBACyT 20020170100309BA: Algoritmos, Azar y complejidad
Proyecto UBA dirigido por J. Heintz con codirección de V. Becher.
💰 UBACyT 📅 2018-2022
Investigadores (10)
