Taller de teoría de la computación 2011

posgrado en computación, unam

Jorge Urrutia

Geometría, Combinatoria y Algoritmos

La Geometría ha sido desde el principio una de las áreas mas estudiadas de las Matemáticas. Los Libros de Euclides, uno de los compendios matemáticos mas antiguos, dedica una gran parte de ellos a la Geometría. Puede afirmarse que lo que hoy conocemos como la Geometría Computacional, nace justo ahí, en los libros de Euclides. En los mismos se dan recetas sobre como trazar un círculo que pase por tres puntos, rectas paralelas, etc. Con el desarrollo de las computadora, el desarrollo de la geometría algorítmica recibió hace alrededor de 30 años un nuevo impulso. 

En esta platica daremos una revisión muy breve de algunos problemas que se han estudiado en el área conocida como la "Geometría Computacional". También presentaremos algunos resultados en los que hemos trabajado, incluyendo resultados de tipo teórico y aplicado, mostrando como el desarrollo de ambas corrientes en el quehacer científico son de suma importancia.

Semblanza

Jorge Urrutia obtuvo su licenciatura en matemáticas en la Facultad de Ciencias de la UNAM en 1974, y su maestria y doctorado en la Universidad de Waterloo en 1980. Desde 1999 trabaja en el IMATE en la UNAM. Ha publicado mas de 210 artículos. Actualmente dirige 10 estudiantes de doctorado y 9 de maestría en el programa de posgrado en Ciencias e Ingeniería de la Computación en la UNAM.  Ha dictado mas de 20 pláticas plenarias en congresos internacionales en Geometria Computacional, y ha participado en mas de 100 congresos internacionales. Fue editor en jefe de la revista "Computational Geometry, Theory and Applications" de 1990 al 2000, actualmente, esa revista es la de mayor impacto en su área. Ha colaborado en la organización de mas de 30 congresos y talleres de investigación a nivel nacional e internacional. Anualmente organiza varios talleres de investigación en diversos lugares de la República Mexicana en los que participan investigadores mexicanos, extranjeros y sus estudiantes de posgrado. Pertence al Sistema Nacional de Investigadores (nivel III).

Francisco Hernández Quiroz

Equidad, vitalidad y otras virtudes en el desarrollo de software

Los patrones de software son una forma de generalizar soluciones
útiles que surgieron en un contexto específico a situaciones
estructuralmente similares. En particular, en el desarrollo de
software basado en el paralelismo los patrones pueden ser muy útiles
para la adopción de soluciones exitosas previas a nuevas situaciones.

Habitualmente, las descripciones de patrones de software paralelo se
realizan con una combinación de lenguaje natural y diagramas, pero el
uso de éstos no se basa en ningún formalismo aceptado de manera
general. Este estilo de presentación hace muy difícil saber si el
software basado en estos patrones funcionará de manera confiable.

Esta plática presentará algunos intentos en la formalización de
patrones de software paralelo con el objetivo de demostrar que se
cumplen propiedades deseables en sistemas paralelos y concurrentes, en
particular, las propiedades de equidad, vitalidad y ausencia de
bloqueo. .

Semblanza

Francisco Hernández estudió Matemáticas y Filosofía en la UNAM, y  el doctorado en Ciencias de la Computación en Imperial College. Sus principales líneas de investigación son la teoría de la concurrencia, la aplicación de la lógica en las Ciencias de la Computación y el concepto de computabilidad y su relación con las explicaciones posibles de la realidad mental y física. Actualmente, en la Facultad de Ciencias de la UNAM, imparte clases en la licenciatura en Ciencias de la Computación y los Posgrados de Ciencia e Ingeniería de la Computación y Filosofía de la Ciencia. Pertence al Sistema Nacional de Investigadores (nivel I).

Sergio Rajsbaum

Cómputo distribuido y topología

Se ha descubierto que la posibilidad de resolver problemas que tiene un sistema que consiste de varias procesos, computadoras o procesadores, depende de las propiedades topológicas de objetos geométricos que lo representan. Estos objetos pueden capturar el modelo de comunicación, tolerancia a fallas y sincronía del sistema distribuido. Se presenta una introducción a esta sorprendente conexión entre dos áreas tan distintas aparentemente.

Semblanza

Obtuvo el grado de Ingeniero en Computación de la UNAM en 1985, y el grado de Doctor en Ciencias de la Computación del Instituto Tecnológico de Israel en 1991. Hizo una estancia posdoctoral en el MIT, y una sabatica en el los Laboratorios de Investigacion de HP. Desde 1991 es investigador del Instituto de Matemáticas de la UNAM, y ahora Secretario Académico de éste. Investigador Titular C, SNI III. Su área principal de investigación es el Cómputo Distribuido, especialmente problemas relacionados a coordinación, sincronización, tiempo y  tolerancia a fallas, muchos de los cuales tienen que ver con Internet y el Web. También ha trabajado en sistemas de administración de información en Plone, algoritmos y otros problemas matemáticos relacionados a la computación y sus fundamentos.

Ricardo Strausz

¿puede el computo alternativo ayudarnos a romper la barrera P≠NP?

En los ultimos años se han explorado algunos modelos de cómputo alternativo que permiten computar MUCHO más rápido que con las computadoras digitales convencionales pero, ¿significa esto que podemos resolver problemas NP-completos en "tiempo polinomial"? ¿a que costo?

Semblanza

Ricardo Strausz obtuvo el doctorado en matemáticas en la Facultad de Ciencias de la UNAM en 2003. Después de estancias de investigación en Budapest, Hungría, y en Praga, República Checa, se incorporó al Instituto de Matemáticas de la UNAM como investigador. Sus áreas de interés incluyen a la combinatoria, geometría y biocomputación.

  David Flores Peñaloza

Gráficas geométricas.

Una gráfica (abstracta) se especifica mediente vértices (nodos) y aristas que unen pares
de vértices. Las gráficas son una estructura de datos elemental y tienen
aplicaciones en muy diversas áreas de la computación, tanto teóricas como aplicadas.

En esta plática hablaremos sobre una de las maneras más naturales de dibujar
una gráfica en una hoja de papel: como una "gráfica geométrica".
Las "gráficas geométricas" son (dibujos de) gráficas en el plano euclidiano,
con la propiedad de que los vértices de la gráfica son puntos en el plano, y las aristas
son segmentos de recta que unen los vértices.
Haremos un recuento del tipo de problemas, tanto combinatorios como algorítmicos,
que podemos estudiar en este tipo de gráficas.

El objetivo de la plática será mostrar que el campo de las gráficas geométricas es
muy activo en la investigación, y que es un campo muy adecuado para madurar matemáticamente
y desarrollar una tesis orientada a la teoría.

Sembanza

Estudió Ingeniería en Computación en el Instituto Tecnológico de Iguala, y Maestría y Doctorado en Ciencias de la Computación en la UNAM. Actualmente es profesor de tiempo completo en la Facultad de Ciencias de la UNAM, en donde imparte los cursos de Licenciatura de Sistemas Operativos y de Redes de Computadoras. Sus intereses abarcan aspectos teóricos y aplicados de Computación, incluyendo Geometría Computacional y Combinatoria, Redes, Sistemas Operativos,  y Cómputo de Alto Rendimiento.

Armando Castañeda Rojano

Consenso y subconsenso en sistemas distribuidos

El problema del consenso consiste en que cada agente de un sistema distribuido
propone un valor a los demás agentes del sistema y debe decidir uno de
los valores que fueron propuestos.
Este problema es considerado fundamental dentro de la teoría
del computo distribuido por sus fuertes implicaciones tanto teóricas
como prácticas.
Entre los muchos y diversos resultados acerca del consenso
se sabe que es universal en el sentido de que cualquier problema
distribuido puede ser implementado a partir
de objetos que solucionan consenso. Dada la universalidad del consenso,
resulta entonces natural utilizarlo para medir el poder de cómputo de
los problema distribuidos.
Esta medida induce una jerarquía, conocida como jerarquía del consenso.
Sin embargo, existen problemas que dada su fina estructura y complejidad
no pueden ser capturados en esta jerarquía. A esta clase de problemas
se les conoce como problemas de subconsenso .

Semblanza

Estudié la carrera de Ingeniería en Sistemas Computacionales en la
Escuela Superior de Cómputo del Instituto Politécnico Nacional.
Los grados de Maestro y Doctor en Ciencias de la Computación
los obtuve del Posgrado en Ciencia e Ingeniería de la Computación
de la Universidad Nacional Autónoma de México, ambos bajo la
supresión del Dr. Sergio Rajsbaum. Actualmente trabajo en el
Institut National de Recherche en Informatique et en Automatique (INRIA)
de Francia.