Programación Dinámica Flashcards
¿Cuales son los componentes de la ecuación de recurrencia en la programación dinámica?
- Definir el estado: MAX(i) que representa la solución óptima para las primeras i actividades.
- Ganacia actual
- Ganancia que se puede obtener: MAX(compatible(i)
- Ganancia si no tomo la decisión: MAX(i-1)
MAX(i)=max(ganancia(i)+MAX(compatible(i)),MAX(i−1))
Problema de “Fraccionamiento de aceite de oliva”.
¿Cuál es el problema?
Encontrar la forma óptima de fraccionar el aceite para obtener la mayor ganancia posible.
Problema de “Fraccionamiento de aceite de oliva”.
¿Cómo se resuleve el problema?
- Se utiliza programación dinámica para evitar recalcular subproblemas.
- Se parte del caso base (0 litros) y se avanza hasta el total de litros disponible, almacenando las ganancias máximas en cada paso.
- Para cada cantidad de litros, se calcula la mejor ganancia posible comparando todas las opciones de fraccionamiento anteriores.
- Se guarda qué fraccionamiento se eligió para cada subproblema para reconstruir el camino de decisiones óptimo.
Problema “Máxima cantidad de intervalos con valor”.
¿Cuál es el problema?
Consta de seleccionar actividades con inicio y fin definidos para maximizar la ganancia total, garantizando que ninguna actividad seleccionada se superponga con otra.
Problema “Máxima cantidad de intervalos con valor”.
¿Cómo se resuleve el problema?
- Ordenar las actividades por fecha de finalización.
- Usar programación dinámica para evitar recomputaciones, almacenando los resultados parciales.
- Definir la función recursiva MAX(i): Máxima ganancia con las primeras i actividades.
- MAX(i)=max(ganancia(i)+MAX(PrevioCompatible(i)),MAX(i−1))
¿Cómo funciona el algoritmo de Kadane para el problema del subvector máximo?
- Recorre la lista y calcula el mejor segmento que termina en cada posición.
- Si un segmento anterior reduce la suma (es negativo), se ignora y se comienza un nuevo segmento.
- Mantiene un MaximoGlobal y un MaximoLocal para almacenar la suma máxima.
¿Por qué falla el algoritmo de Dijkstra con costos negativos?
Dijkstra falla con costos negativos porque no revisa todas las combinaciones posibles y utiliza una estrategia greedy, eligiendo el camino que parece más barato en cada paso. Esto puede llevar a decisiones subóptimas.
¿Qué es un ciclo negativo en un grafo?
Un ciclo negativo es una vuelta cerrada dentro del grafo donde el costo total es negativo, lo que permite disminuir indefinidamente el costo al recorrer el ciclo.
¿Cómo resuelve el algoritmo Bellman-Ford el problema de caminos mínimos con costos negativos?
Bellman-Ford revisa todos los caminos posibles, permite costos negativos (sin ciclos negativos) y actualiza los costos mínimos de los nodos iterativamente.
Describe el proceso de funcionamiento de Bellman-Ford.
Bellman-Ford recorre el grafo varias veces, actualizando los costos mínimos para cada nodo y detectando caminos más baratos. Si después de n-1 iteraciones aún se encuentra un camino más barato, se detecta un ciclo negativo.
¿Qué es un modelo de mínimos cuadrados segmentados?
Un modelo de mínimos cuadrados segmentados busca encontrar una fórmula matemática que explique datos medidos (como la aceleración de un carrito) usando segmentos rectos para predecir futuros comportamientos sin ser excesivamente detallado.
¿Cómo se mide el error en un modelo de mínimos cuadrados segmentados?
El error se mide calculando la suma de las diferencias al cuadrado entre los puntos reales y los puntos correspondientes en la recta ajustada:
