Sesión 09: Repaso¶
Acuerdos¶
Proyecto 14 de Noviembre
Estrategias algoritmicas¶
Divide y vencerás con memorización memoización
- Es un problema de divide y vencerás
- Hay subproblemas repetidos
- Se puede usar una estructura de datos para almacenar las respuestas a subproblemas para evitar recalcular
Programación dinámica
- Son problemas divide y vencerás pero con enfoque de optimización (existe un mejor solución)
- Los subproblemas se repiten y se pueden reutilizar
- Subestructura optima: Permite almacenar los subproblemas
- Garantiza solución optima global
Programación voraz
- Puede resolver con programación dinámica
- Hay una propiedad de escogencia voraz
- No garantiza solución optima
Introducción a la optimización¶
Problema de optimización
Es un problema donde tenemos muchas soluciones validas pero solamente algunas de ellas son las mejores de acuerdo a un criterio
Como se expresa un problema de optmización
- Función objetivo a maximizar o minimizar
- Conjunto de restricciones