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

Knowledgeable Algorithms for Problems On Words

 

kapow      

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

Kapow belongs to  Departamento de ComputaciónFacultad de Ciencias Exactas y NaturalesUniversidad de Buenos Aires and  is also part of the Laboratoire International Associé  INFINIS  (Université Paris Diderot-CNRS/UBA-CONICET) .
 

 

About KAPOW (In Spanish)

Nos dedicamos a problemas combinatorios sobre secuencias finitas e infinitas. Por ejemplo, la condición más básica del azar para secuencias infinitas se define de manera combinatoria y se llama normalidad. La normalidad asegura que todos los bloques de símbolos del mismo tamaño ocurren, en el límite, con  la misma frecuencia.  Son muchas las preguntas que continúan abiertas desde que Émile Borel dio la definición, 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 fraccionarias normales en alguna base. Se cree que sí. 

En el grupo KAPOW nos ocupamos de cómo definir secuencias aleatorias bajo restricciones o con propiedades especiales, cómo computarlas eficientemente, cómo calibrar distintas nociones de aleatoriedad, cómo definir  la noción de independencia entre secuencias normales, como pasar de aleatoriedad en un alfabeto a aleatoriedad en otro.  Otros problemas surgen al formalizar preguntas sobre secuencias naturales (como genomas o proteínas). Tenemos una colaboración activa 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 y un poquito de lógica y computabilidad.

 

KAPOW group
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