Corrección TP2

[fdelu]

Buenas! ¿cómo están?

Les dejo la corrección del trabajo práctico. La nota es un 5.

El algoritmo esta bien, encuentra el óptimo, pero me costó bastante entender por qué funcionaba, me da la sensación que algunas cosas quedaron en el código por miedo a romperlo (porque funciona) pero no están del todo bien o no se entiende muy bien cómo es que funciona. Lo mismo con la ecuación de recurrencia.

Empiezo por la ecuación de recurrencia. Primero que nada plantean una función $G(i, j)$ que da la ganancia óptima del día $i$, ni idea el $j$: no definen concretamente que representa la función. Más adelante en el informe, cuando hablan de la matriz, dicen que "Cada fila de la matriz representa un día del cronograma, mientras que cada columna de la matriz representa la energía que está siendo utilizada". Por lo tanto, entiendo que $i$ vendría a ser el día, $j$ vendría a ser el índice de la energía siendo utilizada (por lo tanto, $j$ es hace cuantos días no descansamos, o equivalentemente, cuantos días de entrenamiento seguidos llevamos) y $G(i, j)$ la ganancia óptima del día $i$ habiendo descansado hace $j$ días.

El problema es que si tomamos esas definiciones, su ecuación de recurrencia no tiene sentido. Dicen que es el máximo entre haber entrenado o haber descansado el día anterior. Pero, si descansaste el día anterior, debería ser $j = 1$. Para cualquier otro $j \neq 1$ si o si entrenaste el día anterior.

Les dejo por ejemplo estas 2 líneas de su algoritmo:

ganancia[i][j] = max(ganancia_entrenando, ganancia_descansando)
ganancia[i][1] = max(ganancia[i][1], ganancia_descansando)

Esas son las 2 líneas que no me cerraban. Primero que nada, la segunda línea corresponde perfectamente a lo que les dije arriba: están planteando que la ganancia con $j = 1$ es la mejor en la que se descansó el día anterior. Eso en la ecuación de recurrencia no está en ningún lado definido. Si implementamos el algoritmo a partir de la ecuación de recurrencia esa línea no estaría.

La primera línea tiene un error que corresponde a lo otro que les dije arriba: Salvo que $j = 1$, no tiene sentido utilizar el ganancia_descansando ahí. De hecho, si reemplazo esa línea por esta: ganancia[i][j] = ganancia_entrenando, el algoritmo funciona igual y da óptimo. Esto es lo que decía al principio que "me da la sensación que algunas cosas quedaron en el código por miedo a romperlo".

Para corregir eso entonces, su algoritmo sería algo así con ese cambio:

def optimo_propuesto(esfuerzos, energias):
    dias = len(esfuerzos)
    ganancia = [[0] * (dias) for _ in range(dias)]

    for i in range(1, dias):
        for j in range(1, dias):
            ganancia_entrenando = ganancia[i - 1][j - 1] + min(
                energias[j], esfuerzos[i]
            )
            ganancia_descansando = (
                0
                if (i < 2 or j < 2)
                else ganancia[i - 2][j - 2] + min(energias[1], esfuerzos[i])
            )
            ganancia[i][j] = ganancia_entrenando
            ganancia[i][1] = max(ganancia[i][1], ganancia_descansando)

    return ganancia, max(ganancia[dias - 1])

Que si se fijan, es exactamente equivalente a este código (ustedes el valor de ganancia[i][1] lo calculan iterando todos los $j$, este lo hace cuando $j = 1$):

def optimo_propuesto(esfuerzos, energias):
    dias = len(esfuerzos)
    ganancia = [[0] * (dias) for _ in range(dias)]

    for i in range(1, dias):
        for j in range(1, dias):
            if j != 1 or i < 2:
                # Ayer entrené (o estamos en día 1, i = 1)
                ganancia[i][j] = ganancia[i - 1][j - 1] + min(energias[j], esfuerzos[i])
                continue

            # La mejor ganancia habiendo descansado ayer es
            # la mejor de antes de ayer, más la de entrenar hoy
            ganancia[i][1] = max(*ganancia[i - 2]) + min(energias[1], esfuerzos[i])

    return ganancia, max(ganancia[dias - 1])

O sea, para que quede bien definida la ecuación de recurrencia, lo que tendrían que haber hecho es distinguir los casos en los que $j = 1$ y los que $j \neq 1$.

En el algoritmo original de ustedes, asignan el valor de haber descansado ayer a una posición de la matriz con $j \neq 1$ cuando era óptimo dormir el día anterior en comparación a no hacerlo, pero esto en realidad es incorrecto. Imaginen que al calcular ganancia[i][j] = max(ganancia_entrenando, ganancia_descansando) (con $j \neq 1$) gana ganancia_descansando. Eso significa que durmieron en el día $i - 1$. Luego cuando calculen $G(i + 1, j + 1)$ entrenando van a usar el valor de $G(i, j) + min(s{j+1}, e{i+1})$ cuando en realidad tendrían que usar $s{2}$ (que es más grande que $s{j+1}$) porque durmieron hace 2 días. No les afectó esto al resultado final porque para calcular $G(i + 1, 2)$ si que usa $s_{2}$ y como les da mayor esa columna los cálculos de las siguientes filas van a usar ese valor.

Una última aclaración de esto. Ustedes $G(i, 0)$ lo dejaron (al menos en su código) como 0 en todas las filas. Si pensamos en la definición de más arriba, $G(i, 0)$ sería la ganancia óptima del día $i$ habiendo desansado hace 0 días. Es decir, habiéndo descansado hoy. Asi que, técnicamente no sería 0, sino que sería el $max_j(G(i - 1, j))$ (el máximo del día anterior). Incluso implementando el algoritmo de esa manera (con los casos $j=0$ y $j \neq 0$) queda mucho más fácil en mi opinión personal que con $j=1$ y $j \neq 1$ como les quedó a ustedes, ya que no les interesa si se entrenó o descansó el día anterior sino el día actual, y no tienen que ir dos días para atrás en los casos de descanso.

Bueno, perdón por el choclazo de texto, pero quería que entiendan bien esa corrección, que es la más importante. Cualquier cosa pregúntenme o incluso nos podemos juntar en una llamada si quieren.

La segunda corrección más importante sería que no cumplieron esta parte de la consigna: "Debe ser claro cómo ejecutar el programa pasando por parámetro un set de datos como los que se dan de ejemplo.". La verdad que acá hago un poco de mea culpa que no se los corregí en el TP1 que como no tuve que probar no me di cuenta, por eso queda aprobado, pero la nota se debe más que nada a la corrección anterior y esta. En este TP si hice algunas pruebas y tuve que meterme a cambiar su código, intenten la próxima de tener un archivo de código ejecutable por el que le pasas por línea de comandos el path de un archivo como los de la cátedra y te da el óptimo y el tiempo transcurrido. Les recomiendo si usan Jupyter tener el algoritmo en un archivo .py aparte e importarlo desde el notebook y desde el archivo ejecutable.

Les dejo entonces ahora sí la lista con todas las correcciones, en orden de importancia:

• La ecuación de recurrencia no es correcta/no esta bien definida. Además de lo comentado arriba, intenten también definir que pasa en los casos base con $i = 0$ y $j = 0$, o en su caso también con $i = 1$ y $j = 1$ ya que usan en la ecuación $i - 2$ y $j - 2$ como índices. Incluso también con $i < j$, ¿tiene sentido esa mitad de la matriz?
• El algoritmo no coincide con la ecuación de recurrencia planteada
• Falta el ejecutable para probar archivos de prueba
• Aclaren siempre cuando mencionen cosas del estilo "y se almacena en la posición (i, 1) la ganancia por haber descansado" que se refieren a haber descansado el día $i - 1$, no el día $i$, sino se presta mucho a confusión
• No aplicaron el suavizado que les sugerí en el TP1 para los gráficos ("como mejora para los gráficos hacer un promedio de varias samples para cada punto, así se reduce la varianza y queda más suavizado."). Aun así me gustó mucho como les quedó el gráfico de la complejidad (especialmente con ese escalado de la función $n^2$), en el otro gráfico creo que si hubiera quedado mejor con varias samples por punto para reducir el ruido
• Por alguna razón la sección de "Análisis de la Solución" no incremento el índice del informe

En este caso el trabajo esta aprobado, pero si ustedes quieren hacer una reentrega para subir la nota se las acepto. Cualquier pregunta que tengan me pueden preguntar al mail o por slack.

Saludos!

[gabokatta]

Buenas Felipe! Primero que nada muchas gracias por la detallada devolución la vamos a estar leyendo. Te quería consultar si la fecha detallada en el calendario de la catedra 30 de Octubre es la correcta de limite para plantear una reentrega, si es así, me llevo estas correcciones y lo planteo con los muchachos así vemos de mejorarlo. Cualquier duda que se nos tope te avisamos!

Muchísimas gracias nuevamente por la disposición!

[gabokatta]

Una consulta con respecto al grafico: En este caso no hicimos el suavizado porque justamente estábamos bastante contentos con como quedo graficado todo, en un futuro si nos topamos con una situación como el del TP1 sin duda que lo haremos! Consideras que para una reentrega le debemos hacer el suavizado o te gusta como quedaron estos?

Saludos @fdelu, feliz finde largo!

[fdelu]

Buenas de nuevo 🙂 Si, idealmente la reentrega debería ser antes del 30 de octubre. El gráfico de la complejidad quedó re bien sí, el segundo si que tiene esos picos más marcados que quizás estaría bueno suavizar. Igual nada, no es algo súper relevante, los últimos dos items son más detalles que otra cosa. Buen finde!

[gabokatta]

Buenas @fdelu ! Espero estés bien!

No llegamos a coincidir con los tiempos con los chicos del grupo y no pudimos reunirnos a armar la reentrega, te queríamos avisar de antemano para que no quedaras esperando.

Nos llevamos el aprendizaje de la corrección y lo aplicamos al TP3. Muchas gracias igualmente por el gran detalle y explicación! Abrazo!