Herramientas Personales
Usted está aquí: Inicio / ICC / Grupos de Investigación / Kapow
Agenda [Ver +]
Defensa Tesis Licenciatura Nicolás Saravia 17/11/2017 16:00 — Laboratorio 5
Defensa Tesis Licenciatura Ariel Zylber 21/11/2017 17:00 — Aula a confirmar
Charla de la Carrera 28/11/2017 14:00 — Hall Central
 

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 palabras (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 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.  Si consideramos  secuencias de 0s y 1s, una secuencia es normal si, en el limite, el 0 aparece  con frecuencia 1/2 y  también el 1 aparece con frecuencia 1/2. Los bloques 00,  01,  10 y 11 aparecen 1/4 de las veces. Y todos los bloques de la misma longitud aparecen con la misma frecuencia en el límite. 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 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 y un poquito 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, algorithmic randomness, normal numbers, Kolmogorov complexity.