Taller de teoría de la computación 2010

posgrado en computación, unam

 
 

















Evangelos Kranakis

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

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

  2. Bullet 9:30am “Games, Triangulations, and some Theory”, Oswin Aichholzer, Department, University, Austria

  3. Bullet 10:00am “Procesamiento de imagenes medicas: hacia la medicina digital”, Leo Joskowicz, Universidad Hebrea de Jerusalem, Israel

  4. Bullet 10:30am  “The role of asynchronicity in knowledge degradation: a modal perspective”, Francisco Hernández Quiroz, Facultad de Ciencias, UNAM

  5. Bullet 11:00am descanso

  6. Bullet 11:30am “An introduction to wait-free computing”, Michel Raynal, Universidad de Rennes, Francia

  7. Bullet 12:00am “La geometria de los sistemas distribuidos”, Sergio Rajsbaum, Instituto de Matematicas, UNAM

  8. Bullet 12:30am “Computo paralelo”, David Flores, Instituto de Matematicas, UNAM

  9. Bullet 12:30am “¿puede el computo alternativo ayudarnos a romper la barrera P≠NP?”, Ricardo Strausz, Instituto de Matemáticas, UNAM

  10. Bullet 13:00am, “Filogenetica computacional”, David Fernandez Baca, Department of Computer Science, Iowa State University, EUA

  11. Bullet 13:30am, “Metodos computacionales para el algebra abstracta”, Vladislav Khartchenko, FES Cuatitlan, 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).


 
Corentin Travers


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.

 
Francisco Hernández Quiroz


The role of asynchronicity in knowledge degradation: a modal perspective


In recent years, computer scientists have found it useful to apply the notion of knowledge to contexts where (not necessarily human) agents play a role, i.e., interactive systems, communication protocols, computer security, etc.


Modal logic is a well accepted paradigm to formalize (partially) the notion of knowledge. Dynamic epistemic logics can model many of the non-static phenomena of knowledge acquisition and updating. Nevertheless, most models assume (explicitly or implicitly) synchronous communication. But asynchronicity has a strong effect over information accuracy and can lead to knowledge degrading into mere believe even if we assume truthful, well-meaning agents.

In this talk we use a dialect of dynamic epistemic logic based upon the pi calculus (a process algebra with communication based upon private channels) to formalize knowledge degradation in some basic contexts and discuss some requirements for sound inferences in the presence of asynchronicity.


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.

 
Oswin Aichholzer


Games, Triangulations, and some Theory.


In this talk we present some basic ideas about how to play a certain class of mathematical games optimally, namely nim-type games using the Sprague-Grundy theory. We show that not only playing games but also knowing the theory behind them is fun (especially because you then know how to win). Beside well-known games (like NIM, Northcott's game, Dawson's Kayles, and chomp) we will also consider more recent games on triangulations (a central data structure in computational geometry), like the triangulation coloring game and the monochromatic triangle game. For all games we show how to decide whether the first or second player can win, and we present a classic framework which provides also the optimal winning strategy (except for chomp)..


Sembanza

Oswin bio here...

continues here....

 
Gerardo Sierra Martínez


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.

 

“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.”