MATERIA: Métodos probabilísticos en computación

CLAVE: COMP-690

SEMESTRE DE UBICACION: Sexto

AREA: Matemáticas

OBJETIVOS: El curso se centra en aleatoriedad en algoritmos. Consiste de tres partes. La primera introduce el método probabilístico como una herramienta poderosa para demostrar la existencia de objetos combinatorios. Las técnicas que se introducen son importntes para el resto del curso. La segunda parte discute varios algoritmos aleatorizados en distintos ambientes. La tercera parte completa el ciclo y trata con métodos para quitar la aleatoriedad en los algoritmos de tal manera de volverlos determinísticos. Este curso busca hacer conciencia respecto al papel que juega la aleatoriedad en la teoría de algoritmos

TEMARIO:

1. El método probabilístico
   • Conceptos básicos de la teoría de la probabilidad

   • Linealidad de la expectativa

   • El método de remoción

   • El método del segundo momento

   • Fórmulas monotomas para mayorías

2. Algoritmos aleatorizados
   • Métodos algebráicos

   • Programación lineal

   • Problemas de conteo

3. Remoción de la aleatoriedad
   • Introducción

   • El método de las probabilidades condicionales

   • Independencia limitada

   • Espacios de probabilidad con perjuicios (bias) pequeños

   • Aplicaciones para los espacios de probabilidad con perjuicios pequeños

BIBLIOGRAFIA:

• Alon, S., The Probabilistic Method, John Wiley & Sons, 1991

BIBLIOGRAFIA COMPLEMENTARIA:

• Naor, S., Probabilistic Methods in Computer Science, Notas de clase editadas en: international Computer Science Institute at Berkeley, Computer Science Department at Stanford University. 1992

• Enslein, K., Ralston, A., Wilf, H.S., Statistical Methods for Digital Computers, Vol. III of Mathematical Methods for digital Computers, John Wiley, NeW York, 1977

• Patterson, B.A.S., Computer-Related Mathematics and Statistics, Manchester: National Computing Center Publications, 1988