Taller de teoría de la computación 2011

posgrado en computación, unam

 
 























.
 

programa

  1. Bullet 9:00am “Geometría Discreta y Computacional”, Jorge Urrutia, Instituto de Matemáticas, UNAM

  2. Bullet 9:30am “Gráficas geométricas”, David Flores Peñaloza, Facultad de Ciencias, UNAM

  3. Bullet 10:00am Receso

  4. Bullet 10:30am  “Equidad, vitalidad y otras virtudes en el desarrollo de software”, Francisco Hernández Quiroz, Facultad de Ciencias, UNAM

  5. Bullet 11:00am --cancelada--

  6. Bullet 11:30am “Cómputo Natural”, Ricardo Strausz, Instituto de Matemáticas, UNAM

  7. Bullet 12:00am Receso

  8. Bullet 12:30am "Efficient Implementations of Concurrent Objects", Michel Raynal, Universidad de Rennes, Francia

  9. Bullet 13:00am, "Consenso y subconsenso en sistemas distribuidos"
                 Armando Castañeda, IRISA, Universidad de Rennes , Francia

  10. Bullet 13:30am, “Dos historias acerca del amor: La geometría de los sistemas distribuidos”, Sergio Rajsbaum, Instituto de Matematicas, UNAM

Ponentes y resumenes

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


 
 
Michel Raynal
Michel Raynal
IRISA, Universidad de Rennes

His research interests include distributed algorithms, distributed
computing systems, networks and dependability. His main interest lies
in the fundamental principles that underly the design and the construction
of distributed computing systems. He belongs to the editorial board of several international journals, has published more than 120 papers in journals, and more than 230 papers in conferences. He has also written eight  books devoted to parallelism, distributed algorithms and systems.




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.

 

“La computación teórica se interpreta ampliamente de manera que incluye  algoritmos, estructuras de datos , teoría de la complejidad computacional, computación distribuida, computación paralela, VLSI, aprendizaje por máquinas, biología computacional, geometría computacional, teoría de la información, criptografía, computación cuántica, teoría de números computacional y álgebra, semántica de programas y verificación, teoría de autómatas, y el estudio de la aleatoriedad. El trabajo en este campo se distingue usualmente por su énfasis en las técnicas matemáticas y rigor.”