Este curso introductorio está diseñado para estudiantes avanzados de licenciatura en Informática. Su objetivo es explorar el análisis probabilístico de algoritmos y la combinatoria analítica, áreas esenciales en el diseño y análisis de algoritmos y estructuras de datos eficientes.
El análisis probabilístico de algoritmos ha permitido modelar el rendimiento y el comportamiento de algoritmos en situaciones realistas, donde las entradas son aleatorias o extremadamente complicadas. Iniciado por Donald Knuth, este enfoque ha tenido un profundo impacto en la Informática, explicando el comportamiento eficaz de ciertos algoritmos fundamentales, como Quicksort, tablas de hash y arrays dinámicos, al revelar cómo la naturaleza de los datos puede influir en el desempeño. La combinatoria analítica, desarrollada en gran medida por Philippe Flajolet, ha proporcionado herramientas matemáticas precisas para analizar sistemáticamente estructuras combinatorias y algoritmos mediante técnicas de funciones generatrices y análisis complejo.
Este curso ofrece una introducción al análisis probabilístico de algoritmos y a la combinatoria analítica. A lo largo de cinco clases, se cubrirán tres módulos principales: primero, los métodos probabilísticos que permiten modelar el rendimiento promedio de algoritmos clásicos, además de su aplicación en temas recientes como la predicción de Branching, modelando en parte el comportamiento del procesador. En el segundo módulo, los estudiantes descubrirán las técnicas de la combinatoria analítica para describir sistemáticamente y con precisión el comportamiento asintóticamente de estructuras y algoritmos, mediante el uso de funciones generatrices y análisis complejo. Finalmente, el tercer módulo abordará métodos avanzados para la generación aleatoria de estructuras combinatorias, con especial énfasis en los Boltzmann Samplers. El curso combina teoría y aplicaciones prácticas, con un enfoque en aplicaciones reales que demuestran el impacto de estos métodos en la informática moderna.
Tema 1: Métodos Probabilísticos en Algoritmos
Repaso y Fundamentos de Probabilidad en Algoritmos
Modelos de Entrada Realistas y Aplicaciones Modernas
Tema 2: Combinatoria Analítica y Aplicaciones
Introducción a la Combinatoria Analítica
Aplicaciones Clásicas y Modernas
Tema 3: Generación Aleatoria de Estructuras Combinatorias
Métodos clásicos: generación rescursiva, cadenas de Markov
Boltzmann Samplers y Generación Aleatoria de Tamaño Controlado
Los estudiantes deberán tener conocimientos básicos en algorítmica, probabilidad y matemática discreta.
Martínez C., Nebel M. y Wild S.: Analysis of branch misses in quicksort.
Martínez C., Nicaud C. y Rotondo P.: A probabilistic model revealing shortcomings in Lua's hybrid tables.
Flajolet, P. y Sedgewick, R.: Analytic Combinatorics.
Duchon, P., Flajolet, P., Louchard G. y Schaeffer G.: Boltzmann samplers for the random generation of combinatorial structures.
Auger, N., Nicaud, C., y Pivoteau, C.: Good predictions are worth a few comparisons.
Knuth, D. E.: The Art of Computer Programming.
Desarrollado por el Departamento de Computación, FCEyN, UBA