Ideas probabilistas en diseño de algoritmos#
Introducción#
Métodos probabilísticos (*)#
Las técnicas probabilíticas tienen varios usos en el diseño y análisis de algoritmos. Platicaremos de los siguientes dos:
La probabilidad sirve para estudiar los casos promedio de nuestros algoritmos
La probabilidad sirve para agregar un ingrediente probabilista a nuestro problema y usar eso como parte de un algoritmo.
La primera se refiere a que, en el análisis asintótico del costo de un algoritmo, en vez de estudiar el peor caso estudiemos el caso promedio. La segunda se refiere a agregar probabilidad en nuestro algoritmo para que funcione mejor.
Tarea moral#
Los siguientes problemas te ayudarán a practicar lo visto en esta entrada. Para resolverlos, necesitarás usar herramientas matemáticas, computacionales o ambas.
Problema
Problema
Problema
Problema
Problema