fdelu
commented
5 months ago Hola, les dejo la corrección de la reentrega. Para empezar, de los criterios de aprobación de la consigna:
Les voy a tomar la reentrega igual pero si llegan a tener que corregir algo en el próximo TP, por favor en un anexo...
Otras observaciones:
- Me hubiera gustado que reescriban un poco más la parte del análisis, pero con los cambios que hicieron más la conversación que tuvimos por Slack ya lo considero suficiente
-
Sobre esta frase:
En conclusion, nuestro óptimo $OPT(n, j)$ representa la maxima cantidad de abatidos en el minuto $n$, con una carga de al menos $j$, ya que no necesariamente se esta utilizando esa carga $j$ exactamente.
¿Por qué de "al menos $j$"? ¿No quedamos en nuestra conversación que era exactamente lo contrario ("a lo sumo j")?
- La complejidad del algoritmo de reconstrucción es correcta, en el peor caso recorren toda la matriz (o al menos su triángulo inferior). Hubiera estado bueno que mencionen cual es ese peor caso, que sería cuando conviene atacar todos los minutos con carga 1.
Tengan muchísimo cuidado con el
list.insertque usaron. Ese método en Python es $O(n)$ (ver documentación) ya que se implementa como un arreglo, no como una lista enlazada. Esto no se les fue a cúbico de casualidad, porque esa operación solo la hacen una vez por minuto entonces les queda $O(n \cdot (n + n))$ que sigue siendo $O(n^2)$. Si durante la construcción de la matriz se guardaban un arreglo con las posiciones máximas de cada minuto, podrían hacer la reconstrucción en $O(n)$ -
Respecto a como afecta la variabilidad a los tiempos medidos: es verdad que para el algoritmo original no afecta la complejidad temporal, pero si hubiera estado bueno que hagan un análisis con distintas combinaciones de valores (por ejemplo, los $x_i$ mucho más grandes que los $f(j)$ y viceversa) Para el algoritmo de reconstrucción dicen:
Por otro lado, la variabilidad de los valores de entrada si afecta la complejidad del algoritmo de reconstruccion, ya que segun los valores se puede dar que solo se vea un valor por fila de la matriz, y esto hace que haya que recorrerla toda.
Perfecto, ¿cómo tienen que ser los valores para que pase eso? También se podrían haber fijado casos particulares. Por ejemplo, si conviniera atacar solamente en el día $n$ con carga $j$, técnicamente su algoritmo de reconstrucción sería $O(n)$ (sería $O(1)$ pero tienen que insertar $n-1$ veces el "DESCANSAR"). Eso podría llegar a pasar si los $x_i$ crecen mucho cada minuto y los $f(j)$ son muy grandes, por ejemplo.
- Para el próximo TP esperaría que apliquen algunas de las las sugerencias que les di en el TP1 de la parte de mediciones
Les cierro el TP aprobado con un 6, cualquier cosa avisenme! Saludos
iinaki
Buenas, les dejo las correcciones del TP2
2. Análisis del problema
El máximo entre esa cantidad de bajas más la suma acumulada, ¿y qué otra cosa?
3. Propuesta de Solución
Entiendo que cuando dicen "día" se refieren a "minuto".
No me quedó del todo claro lo de $j$. Segun entendí, definen $OPT(n, j)$ como la máxima cantidad de bajas en el minuto $n$ con carga $j$ (es decir, el último ataque fue en el minuto $n-j$), ¿correcto?
¿Por qué el subíndice $i$? ¿Qué representa?
¿Por qué? Si yo tengo $OPT(n, j)$ con la definición que dieron, siempre es óptimo atacar el minuto $n$, ya que entre sumar 0 y sumar $min(x_n, f(j))$ es mejor sumar $min(x_n, f(j))$.
Más allá de eso, ¿por qué decidir no atacar ese minuto sería igual al óptimo del mismo minuto con un nivel de carga $j-1$? ¿no tendría que ir al minuto anterior ($n-1$)? Si yo digo que no ataco en el día $n$ el óptimo sería más bien $OPT(n-1, j-1)$ (es decir, el óptimo del minuto anterior con 1 de carga menos)
¿Por qué nivel de carga $n-j$? Si yo atacó el día $n$ con carga $j$, efectivamente le sumo $min(x_n, f(j))$ al óptimo del minuto $n-j$, pero no necesariamente al óptimo del minuto $n-j$ con carga $n-j$ sino al mejor óptimo de todos los de ese minuto (que por como definieron sus ecuaciones justo es siempre el de carga $n-j$, pero esas ecuaciones no se condicen con lo que están explicando en palabras).
Más allá de todo esto, les quería mencionar también que este ejercicio sí se puede hacer con una sola variable y no 2. No baja puntos que lo hayan hecho con 2, ya que la complejidad temporal en definitiva es la misma, pero si va a mejorar después la complejidad espacial hacerlo unidimensional.
4.2 Complejidad
La complejidad es correcta, pero falta la complejidad del algoritmo de reconstrucción.
También faltó esta parte de la consigna: Analizar si (y cómo) afecta a los tiempos del algoritmo planteado la variabilidad de los valores de las llegadas de enemigos y recargas..
5. Mediciones temporales
En general esta bien, correcto, pero valen casi todas las mismas correcciones del TP1, no aplicaron ninguna. Me hubiera gustado que hagan el ajuste de cuadrados mínimos (más que nada en este TP que la complejidad era polinomial y era mucho más fácil que en en el TP1), para demostrar realmente que coinciden las mediciones con la complejidad esperada. Les dejo este hilo de slack donde hablamos de esto por si les sirve para el próximo TP: https://tdafiuba.slack.com/archives/C05HT3QTQQP/p1714772633752529
También haría las mediciones con valores un poco más grandes de $n$. Una ejecución de 10000 no les puede tardar mucho más de un minuto.
Nota
Les voy a tener que pedir que me hagan una reentrega, corrigiendo más que nada la propuesta de la ecuación de recurrencia y agregando el punto de las consigna que les faltó (por más que sea corto).
Respecto a la propuesta de la solución, este es el item más importante a corregir. Lo primero que quiero aclarar es que sí, la ecuación de recurrencia y el algoritmo que dieron funciona, pero no por las razones que dieron. Es decir, casi todo el análisis que los llevó a la ecuación de recurrencia en definitiva es incorrecto. A mi parecer tienen 3 opciones:
Las últimas 2 opciones implican cambiar los demás puntos del TP, a mi entender no les debería complicar mucho ya que en definitiva las respuestas son casi las mismas y ya tienen todo el código para las mediciones hecho, pero cualquier cosa lo podemos charlar.
Para cerrar les quiero dejar que hagan este análisis para ver si entienden por que su definición de $OPT(n, j)$ no coincide con su ecuación (más que nada si van por la opción 1 de las de arriba):
Fijense ahí el $OPT(4, 3)$ (es decir $n=4, j=3$) vale 1189. Eso quiere decir, con la definición que dieron, que el óptimo para el minuto 4 con 3 de carga es 1189, ¿no?. Perfecto. Claramente en el minuto 4 con 3 de carga me conviene atacar, porque le sumo al óptimo del minuto 3 $min(x_4, f(3))=656$ y si no ataco no sumo nada. Asi que si sumé 656, el óptimo del minuto 3 era 1189-656=533. Pero fijense que en la fila del minuto 3 ninguna celda tiene ese valor. Asi que evidentemente algo anda mal.
Estoy disponible para cualquier consulta que tengan. Ahora de todas formas les hablo por Slack para que nos comuniquemos por ese medio. Saludos!