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 ICC CONICET y al  Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires  y también es parte del Programa Internacional de Investigación  SINFIN (ex INFINIS)  (Université de Paris-CNRS/UBA-CONICET) .

 

• Quienes somos
• Algoritmos y software
• Nuestras tesis
• Nuestros proyectos
• Nuestras publicaciones

 

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.

 

Kapow!, por Patricia Olivella, El Cable 926, Subsecretaría de Comunicación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires 23 mayo 2018. pdf link

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)5285-7480
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.