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. 9:00am “Geometría Discreta y Computacional”, Jorge Urrutia, Instituto de Matemáticas, UNAM

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

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

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

5. 11:00am descanso

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

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

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

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

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

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

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.

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