Taller de teoría de la computación 2009
posgrado en computación, unam
Topology Control in Sensor Networks Using Directional Antennae
Directional and omnidirectional are the two types of antennae being used in sensor networking. The former emit greater power in one direction thus achieving increased transmission range and performance as well as reduced interference from unwanted sources. On the contrary, omnidirectional antennae radiate power uniformly in all directions in the plane. Regardless of the type of antenna being used the transmission cost of each antenna is proportional to the coverage area of the antenna. It is therefore of interest to design efficient algorithms that minimize the overall transmission cost while at the same time maintaining network connectivity. Consider a set S of n points in the plane modeling sensors of an ad hoc network. Each sensor uses a fixed number, say k, of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius).
We present recent algorithms and study trade-offs on the max angle, sum of angles, max range and number k of antennae being used per sensors for the problem of converting networks
of omnidirectional sensors into strongly connected networks of sensors using at most k directional antennae per sensor.
Semblanza
Evangelos Kranakis se recibó de licenciatura en Matemáticas en la Universidad de Atenas en 1973 y de doctorado en Lógica Matemática en la Universidad de Minnesota en 1980. Desde 1991 es investigador en el School of Computer Science de Carleton University. Ha publicado en analisis de algoritmos, bioinformática, redes inalámbricas y ad hoc, geometría computacional y combinatoria, computación distribuida, y seguridad de redes. Es autor de tres libros: Primality and Cryptography, Boolean Functions and Computation Models, y Principles of Ad Hoc Networking.
programa
-
10:00am “Geometría, Combinatoria y Algoritmos”, Jorge Urrutia, Instituto de Matemáticas, UNAM -
10:30am “Topology Control in Sensor Networks Using Directional Antennae”, Evangelos Kranakis, Carleton, Canada
-
11:00am “Proyectos en las áreas de lógica modal”, Francisco Hernández Quiroz, Facultad de Ciencias, UNAM
-
11:30am “Algoritmos genéticos para encontrar conjuntos de puntos”, Ruy Fabila, Departamento de Matemáticas , Cinvestav
-
12:00am “Métodos y aplicaciones del PLN orientado al análisis de textos”, Gerardo Sierra, Instituto de Ingeniería, UNAM
-
12:30am “¿puede el computo alternativo ayudarnos a romper la barrera P≠NP?”, Ricardo Strausz, Instituto de Matemáticas, UNAM
-
13:00am, “Uncertainty in distributed computing: a quick overview”, Corentin Travers, U. Paris, Francia
-
13:30am, “Cómputo distribuido y topología”, Sergio Rajsbaum, Instituto de Matemáticas, UNAM
Ponentes y resumenes
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).
Uncertainty in distributed computing: a quick overview
Semblanza
Corentin Travers terminó el doctorado en 2007 con Michel Raynal en la Universidad de Rennes, Francia. Después de una estancia posdoctoral en UPM Madrid, y otra en el Technion de Israel, es ahora esta en la Universidad de Paris. Ha publicado 30 artículos de investigacion acerca de algoritmos distribuidos, en temas relacionados a detectores de fallas y problemas de acuerdo.
Proyectos en las áreas de lógica modal
En el curso de unas cuantas décadas, las lógicas modales han pasado de ser un tema casi exclusivamente filosófico para convertirse en una técnica básica en la computación y en la modelación de fenómenos en otras ciencias.
Actualmente, estamos trabajando en cuatro problemas específicos en los que la lógica modal es el tema o la herramienta central: (a) una lógica dinámica epistémica basada en el cálculo Pi asíncrono; (b) una lógica dinámica epistémica para describir el desarrollo y las estrategias de los jugadores de dominó; (c) la verificación y evaluación de patrones de software paralelos por medio de álgebras de
procesos y lógicas modales basadas en estas álgebras; (d) la representación algebraica de información genética y epigenética y su análisis por medio de la lógica modal.
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).
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.
¿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.
Algoritmos genéticos para encontrar conjuntos de puntos.
El área Geometría Combinatoria considera problemas combinatorios sobre objetos geométricos. Muchos de estos problemas son de conteo, donde dado un conjunto S de n puntos en el plano se pregunta cuantos objetos de un determinado existen sobre eses conjunto de puntos. Para muchos de estos problemas se conocen buenas cotas y ejemplos extremales. Sin embargo existe todavía una considerable brecha este entre ellos. Por otra parte existen algoritmos eficientes para contar estos objetos. En esta plática explotaremos esta situación y usaremos algoritmos genéticos (y sus parientes) para encontrar conjuntos de puntos con pocos (o muchos, según sea el caso) de estos objetos geométricos.
Sembanza
Ruy Fabila estudio la licenciatura en Ciencias de la Computación en la Facultad de Ciencias de la UNAM. Realizó los estudios de Maestría y Doctorado en Matemáticas en el instituto de Matemáticas también de la UNAM. Actualmente se encuentra trabajando como profesor
invitado en el Departamento de Matemáticas de CINVESTAV. Sus intereses son la Geometría Computacional y Combinatoria así como la Teoría de Gráficas; cuenta con 9 artículos de investigación en estas áreas.
Métodos y aplicaciones del PLN orientado al análisis de textos
El Procesamiento de Lenguaje Natural (PLN) busca el diseño de herramientas para analizar o sintetizar el lenguaje natural hablado o escrito. En el segundo caso, las aplicaciones son diversas, como la recuperación y extracción de información, la clasificación y agrupamiento de documentos, el resumen automático de textos, la traducción automática y la minería de textos de documentos científicos o de redes sociales. En todos los casos, se requieren técnicas y métodos comunes que, ya sea basados en reglas, en estadísticas o en una combinación de ambos, implican un análisis de los distintos niveles del lenguaje humano: morfológico, sintáctico, semántico y pragmático.
Semblanza
Doctor en Lingüística Computacional en UMIST, Inglaterra, jefe del Grupo de Ingeniería Lingüística. Docencia, investigación y desarrollo, en áreas como lexicografía computacional, terminótica, recuperación y extracción de información, minería de textos y corpus lingüísticos. Actualmente es Investigador Titular A, Investigador Nacional II, evaluador de proyectos Conacyt, miembro de varios comités científicos. Cursos conjuntos en la UNAM para las Facultades de Ingeniería y de Filosofía y Letras, así como a los Posgrados de Lingüística, de Bibliotecología y de Computación. Ha logrado que en el Programa de Estudios de la Facultad de Ingeniería se abra un módulo de especialidad sobre Tecnologías del Lenguaje en la Carrera de Ingeniería de Computación.
fecha:
20 noviembre 2009
Lugar:
Auditorio del IIMAS, UNAM
Horario:
10am a 2pm
Organizador:
Sergio Rajsbaum
informes:
acerca de Teoría de la computación
“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.”
