Horario: 9 a 12 hs

Dr. Leen Stougie es Assistant Professor en el Departamento de Matemáticas de la Universidad Tecnológica de Eindhoven (Holanda). Obtuvo su doctorado en 1985, dirigido por J. K. Lenstra y A. H. G. Rinooy Kan. Se ha desempeñado como investigador y profesor en las universidades de Rotterdam, Amsterdam, Berkley, L’Aquila y Yale. Ha publicado numerosos trabajos en congresos y revistas internacionales. Sus principales temas de interés incluyen: análisis probabilístico, algoritmos probabilísticos, algoritmos on-line y programación entera estocástica.

Los algoritmos probabilísticos han atraído el interés de los investigadores de manera creciente en los últimos 20 años, y actualmente son un tema central de investigación en Ciencias de la Computación, Investigación Operativa, y Matemática Discreta. El poder de la "randomización" para resolver problemas proviene de que un algoritmo probabilístico es una distribución probabilística sobre una clase de algoritmos determinísticos. Para cualquier instancia dada de un problema, algunos de los algoritmos determinísticos en la base del algoritmo probabilístico pueden comportarse pobremente, pero eso puede ser compensado con buenas prestaciones de otros en forma tal que el comportamiento esperado sea bastante bueno.

Otra aplicación quizás inesperada de los algoritmos probabilísticos es en pruebas de teoremas de existencia relativos a propiedades de objetos combinatorios. Esta técnica de prueba es conocida en la literatura como método probabilístico. Las pruebas a través de algoritmos probabilísticos son comunmente mucho más simples que otras pruebas, y en muchos casos son las únicas conocidas.

A pesar de la creciente cantidad de literatura sobre algoritmos probabilísticos, la investigación y el conocimiento acerca del poder de la aleatoriedad está todavía en sus comienzos. Muchas cuestiones interesantes y problemas básicos siguen abiertos, proveyendo un atractivo campo de investigación. Por otro lado los algoritmos probabilísticos ya han mostrado su utilidad en una gran variedad de aplicaciones en los campos de estructuras de datos, programación lineal, problemas de gráfos, programación paralela y distribuída, y problemas on-line.

En el curso nos concentraremos en los resultados más teóricos en este campo. Sin embargo, la exposición será principalmente a través de ejemplos, algunos de ellos de interés práctico directo. Durante el curso serán tratados temas seleccionados del libro de R. Motwani y P. Raghavan "Randomized Algorithms". Literatura adicional será provista a los participantes.

Prerrequisitos:

Nociones básicas de probabilidades y análisis de algoritmos.