Herramientas Personales
Usted está aquí: Inicio / Investigación / Algoritmos, Complejidad y Aplicaciones

Algoritmos, Complejidad y Aplicaciones

Se enfoca en algoritmos eficientes en optimización discreta, combinatoria y continua y on-line, en teoría de grafos, aplicaciones internet y análisis de ficheros de texto (stringología) y también para la evaluación de consultas particulares de bases de datos muy grandes en genómica, recuperación de imágenes búsquedas en la web y geometría elemental. Complejidad en computación científica (cotas superiores e inferiores de complejidad en el contexto numérico, seminumérico y simbólico).

Campos: Teoría general de grafos, optimización lineal y no-lineal, local y global, algoritmos on- line, Knowledge Management, microeconomía y algorítmica de publicidad on-line, complejidad de Kolmogorov y azar, algoritmos para problemas de palabras (stringology) con aplicaciones en genómica, álgebra lineal numérica, sampling, teoría de números efectiva, criptografía, constraint data bases, geometría algebraica, semialgebraica y diofántica efectiva (Computer Algebra), teoría algebraica de la complejidad.

 

Grupos de Investigación/Temas:

- Algoritmos sobre palabras/secuencias y aplicaciones - Kapow: http://www.dc.uba.ar/kapow

 

Nos dedicamos a problemas sobre palabras (secuencias, strings), especialmente en temas de aleatoriedad y combinatoria, con un enfoque que integra la teoría y la práctica. Diseñamos e implementamos  algoritmos y estructuras de datos para volúmenes muy grandes de datos, donde la complejidad de representación, complejidad tiempo y complejidad  memoria son cruciales. También trabajamos en la visualización, ideando e implementando interfases para mostrar los resultados computacionales.

Uno de los proyectos actuales, en colaboración con especialistas en genómica comparativa, trata sobre secuencias de ADN. Dimos una aproximación computable y eficientemente calculable de la función de complejidad de Kolmogorov, garantizando buenas propiedades matemáticas, como la subaditividad. Usamos nuestra función para aproximar la cantidad de información de distintos genomas que los biólogos interpretan desde la perspectiva genómica y evolutiva. Este proyecto incluye temas de algorítmica, complejidad, cómputo de alta performance y diálogo interdisciplinario.

 

- Algoritmos y Herramientas computacionales para los motores búsqueda y la publicidad online

La venta de publicidad asociada a los resultados de las búsquedas o a los contenidos de una página se ha convertido en la mayor fuente de ingresos de las principales empresas del sector, y su importancia relativa continúa creciendo. Las decisiones acerca de cuántos y cuáles avisos elegir, en qué orden mostrarlos, cómo y cuánto cobrarlos, abren un amplio campo de investigación que vincula distintas disciplinas, en la búsqueda de mecanismos que permitan satisfacer los intereses de los distintos actores involucrados (editores, anunciantes y usuarios), con propiedades de eficiencia y practicidad adecuadas a las características de la aplicación (masividad, velocidad de respuesta requerida, etc.). Se busca analizar tanto teórica como experimentalmente los mecanismos actualmente en uso y otros nuevos, con el objeto de proveer nuevas herramientas a los participantes de esta importante y novedosa actividad económica. Otra línea de investigación de este grupo consiste en el diseño de algoritmos y estructuras de datos más eficientes para la recuperación de información, en particular la construcción de índices distribuidos.

- Criptografía

El tema central de investigación es el desarrollo de algoritmos polinomiales de factorización de enteros, esencial para la seguridad del método estándar de criptografía de clave pública (RSA).

- Investigación en Grafos y Optimización: Teoría y Aplicaciones: http://www.dc.uba.ar/inv/grupos/grafos

 

Dentro del área de Teoría de Grafos, las principales líneas de investigación son: Coloreo de grafos; Caracterizaciones estructurales de clases de grafos; Complejidad computacional. Dentro de lo que es Optimización Combinatoria, las principales áreas abordadas son: Combinatoria poliedral; Problemas de scheduling deportivo; Aplicaciones a problemas reales (ruteo de vehículos, logística); Aplicaciones en teoría de juegos. Los profesores del DC que dirigen el grupo son Flavia Bonomo y Javier Marenco. El grupo está dirigido también por Guillermo Durán (DM, FCEN-UBA), y se completa con investigadores y tesistas del DC, el DM y del Instituto de Ciencias la UNGS. A su vez tiene una activa colaboración con investigadores de primer nivel internacional. Con respecto a los proyectos aplicados, entre los últimos se encuentran la segmentación de viviendas para el Censo Nacional 2010, la planificación de la recolección de residuos en contenedores en la zona sur de la Ciudad de Buenos Aires, el diseño del fixture de la liga de primera división de vóley masculino, el diseño de un modelo matemático para administrar la licitación de Internet para las escuelas públicas de la Ciudad de Buenos Aires y la implementación de modelos de simulación para el Sistema de Administración de Aportes de Productores en el ámbito de la Ciudad de Buenos Aires.

 

- Teoria de Grafos: http://www.dc.uba.ar/grupinv/invop

 

Realiza investigaciones en el área de combinatoria, teoría de algoritmos y estructuras de datos complejas. Se estudian propiedades de diferentes clases de grafos, se caracterizan estas clases y se estudia el problema de reconocimiento de las mismas. Por otro lado, desarrollamos nuevos algoritmos que resuelven problemas ya resueltos en la literatura, intentando mejorar la "eficiencia" de las soluciones conocidas.


Profesores del área:

- Verónica Becher

- Flavia Bonomo

- Esteban Feuerstein

- Marina Groshaus

- Joos Heintz (coordinador)

- Javier Marenco

- Oscar Min Chin Lin

- Hugo Scolnik


Doctorandos:

Angel Barberis, Clara Betancur, Mónica Braga, Luciano Grippo, Pablo Heiber, Ivo Koch, Javier Martinez Viademonte,  Alexis Muñoz, Martín Safe