Herramientas Personales
Usted está aquí: Inicio / ICC / Grupos de Investigación / Kapow

KAPOW (Problemas y algoritmos sobre secuencias)

KAPOW Grupo de investigación en problemas y algoritmos sobre secuencias
kapow       KAPOW is un grupo de investigación en teoría de la computación con foco en problemas combinatorios sobre secuencias, aleatoriedad algorítmica, números normales y complejidad de Kolmogorov. 

KAPOW pertenece al  Departamento de ComputaciónFacultad de Ciencias Exactas y NaturalesUniversidad de Buenos Aires y también es parte del Laboratoire International Associé  INFINIS  (Université Paris Diderot-CNRS/UBA-CONICET) .

 

 

Nos dedicamos a problemas abiertos sobre secuencias en relación a la propiedad de "ser azarosas".  Por ejemplo, la condición más básica del azar para secuencias infinitas se define de manera combinatoria y se llama normalidad.  Si consideramos secuencias infinitas de 0s y 1s,  una secuencia es normal si cumple que el 0 aparece la mitad de las veces (por lo tanto el 1 aparece también la mitad de las veces)  y  cada uno de los bloques de una misma longitud  aparece con la misma  frecuencia que los demás (dado que estamos contando apariciones en una secuencia infinita debemos considerar la frecuencia asintótica). 

Son muchas las preguntas que continúan abiertas desde que Émile Borel dio la definición secuencia normal, hace más de 100 años. La más famosa es si las constantes matemáticas usuales, como Pi o la base del logaritmo natural e, o la raíz cuadrada de 2  tienen expansiones decimales normales. Se cree que sí.  

En KAPOW nos ocupamos de la aleatoriedad en distintos modelos de cómputo (autómatas finitos, máquinas de Turing), de cómo pasar de aleatoriedad en un alfabeto a aleatoriedad en otro,  y cómo asegurar independencia de secuencias aleatorias.  Otros problemas surgen al formalizar preguntas sobre secuencias naturales (como genomas o proteínas). Tenemos colaboración con el Laboratorio de Fisiología de Proteínas del Departamento de Química Biológica de la FCEyN, UBA. 

Para resolver los problemas usamos resultados de teoría de grafos, teoría de autómatas, aritmética elemental,  algoritmos eficientes, análisis de complejidad computacional, un poco de teoría de números y otro poco de lógica y computabilidad.

 

Grupo KAPOW 
Departamento de Computación
Facultad de Ciencias Exactas y Naturales
Universidad de Buenos Aires
Pabellón I , Ciudad Universitaria
C1428EGA Buenos Aires,  Argentina
Tel: +54(11)45763359
Email:  vbecher@dc.uba.ar

 

KAPOW is a research group in theoretical computer science with focus in combinatorial problems on words (sequences), algorithmic randomness, normal numbers and Kolmogorov complexity.