Buenas! Les dejo las correcciones del TP. La nota es un 8.
Cualquier cosa que no entiendan o que me quieran preguntar, me pueden mandar un mail o un mensaje por Slack :)
4. 1. Demostración por Inversiones
La demostración en general está bien. Solo les dejo algunas observaciones:
Cuando dicen "Si después de una inversión obtenemos una solución con un valor igual o menor, entonces la solución original también era óptima.". Si después de una inversión se obtiene una solución con un valor menor entonces $S'$ no era realmente óptima, ¿no? Y no veo como eso les diría que la solución original era óptima (salvo con toda la demostración que viene después, esa sería la contradicción de la demostración en sí, pero esto me lo dicen antes de todo eso).
Creo que en la definición de inversión se les borró algun verbo ("Se define una inversión en una solucion tenemos dos batallas $s[i]$ y $s[j]$ en la secuencia tal que $i \lt j$ pero $C_i \lt Cj$ "_).
El caso sin inversiones si bien esta bueno mostrarlo no sería un $S'$ válido. Ustedes mismos definieron $S'$ como "una solución óptima diferente a la propuesta". Si su solución propuesta es ordenar los $C_i$ de mayor a menor, entonces una solución en cualquier orden para un problema donde todos los $C_i$ son iguales (que sería el caso sin inversiones) sería parte de sus soluciones propuestas. En otras palabras, un $S'$ siempre va a tener inversiones.
5. Algoritmo
Está perfecto.
Como detalle totalmente irrelevante a la materia pero que si hace a las buenas prácticas de programación que por ahi les sirve (obviamente no les baja nada la nota esto), por lo general cuando una función modifica una estructura de datos in-place se suele no devolver la estructura modificada.
Fijense por ejemplo la misma documentación list.sort() de Python: "To remind users that it operates by side effect, it does not return the sorted sequence (use sorted() to explicitly request a new sorted list instance)". Cuando se devuelve la estructura modificada se sobreentiende que es una copia de la estructura original.
5.1. Complejidad
"Primero el metodo de ordenamiento de la lista de batallas, el cual asumimos que ordena en $O(n log n)$"
¿Por qué asumimos? Aclarenlo ustedes mismos como parte de su respuesta. Digan que su algoritmo utiliza un algoritmo de ordenamiento que ordena en $O(n \log n)$. Si se refieren a la implementación de Python pueden referir a la documentación.
6. Mediciones temporales
Los gráficos están bien. Algunos items para mejorar:
Siempre que usen números aleatorios en este tipo de informes asegúrense de usar una seed fija para que los resultados sean reproducibles (ver documentación). Es decir, con esto los datos van a seguir siendo "aleatorios" pero siempre van a ser los mismos números cada vez que ejecuten el notebook.
De la misma manera, para disminuir un poco la varianza de las mediciones por los tiempos medidos por la aleatoridad, esta bueno hacer más de una medición por cada punto del gráfico y promediar los resultados (en este TP en particular, en vez de medir el algoritmo 1 vez para cada tamaño $n$ de la lista, medirlo por ejemplo 10 veces y que el punto en $n$ sea el promedio de todas las mediciones).
Si usan otro algoritmo para comparar, intenten por lo menos mencionar cual es ese algoritmo y aclarar que no es óptimo.
Algo que se puede hacer para verificar mejor la complejidad computacional (ya apuntando al 10) es agarrar la fórmula de la complejidad (en este caso $T(n) = n \log n$) y hacer cuadrados mínimos de $A \cdot T(n) + B$ con los tiempos medidos a partir de un $n$ más o menos grande. Con eso pueden ver que tanto se ajustan sus mediciones a la complejidad teórica, y pueden poner la función en el mismo gráfico que sus mediciones en vez de tenerlos separados.
Otras observaciones
No vi nada en el informe sobre el punto 5:
Realizar ejemplos de ejecución para encontrar soluciones y corroborar lo encontrado.Adicionalmente, el curso proveerá con algunos casos particulares que deben cumplirse su optimalidad también..
Podrían por ejemplo haber hecho un mini seguimiento del algoritmo óptimo usando los ejemplos que usaron en la sección 3. Propuesta de Solución para mostrar que los otros algoritmos no funcionaban, y sumar los resultados de los provistos por la cátedra.
La idea del punto es que hagan algún seguimiento/ejemplo sencillo de la ejecución de su algoritmo y lo pongan en el informe.
La consigna dice "Debe ser claro cómo ejecutar el programa pasando por parámetro un set de datos como los que se dan de ejemplo". Su programa no toma ningún parámetro sino que hay que copiar el archivo a entrada.txt. Intenten para el próximo TP hacer que el programa tome el path del archivo como argumento de la línea de comandos para facilitar un poco las pruebas. Otro corrector los hubiera mandado a reentrega por esto, se hace mucho más complicado ejecutar las pruebas de nuestro lado de manera rápida de esa forma...
Ya como detalle también podría estar bueno que imprima por pantalla el resultado de la ejecución (no el orden de las batallas pero si el coeficiente).
Buenas! Les dejo las correcciones del TP. La nota es un 8. Cualquier cosa que no entiendan o que me quieran preguntar, me pueden mandar un mail o un mensaje por Slack :)
4. 1. Demostración por Inversiones
La demostración en general está bien. Solo les dejo algunas observaciones:
Cuando dicen "Si después de una inversión obtenemos una solución con un valor igual o menor, entonces la solución original también era óptima.". Si después de una inversión se obtiene una solución con un valor menor entonces $S'$ no era realmente óptima, ¿no? Y no veo como eso les diría que la solución original era óptima (salvo con toda la demostración que viene después, esa sería la contradicción de la demostración en sí, pero esto me lo dicen antes de todo eso).
Creo que en la definición de inversión se les borró algun verbo ("Se define una inversión en una solucion tenemos dos batallas $s[i]$ y $s[j]$ en la secuencia tal que $i \lt j$ pero $C_i \lt Cj$ "_).
El caso sin inversiones si bien esta bueno mostrarlo no sería un $S'$ válido. Ustedes mismos definieron $S'$ como "una solución óptima diferente a la propuesta". Si su solución propuesta es ordenar los $C_i$ de mayor a menor, entonces una solución en cualquier orden para un problema donde todos los $C_i$ son iguales (que sería el caso sin inversiones) sería parte de sus soluciones propuestas. En otras palabras, un $S'$ siempre va a tener inversiones.
5. Algoritmo
Está perfecto.
Como detalle totalmente irrelevante a la materia pero que si hace a las buenas prácticas de programación que por ahi les sirve (obviamente no les baja nada la nota esto), por lo general cuando una función modifica una estructura de datos in-place se suele no devolver la estructura modificada.
Fijense por ejemplo la misma documentación
list.sort()de Python: "To remind users that it operates by side effect, it does not return the sorted sequence (use sorted() to explicitly request a new sorted list instance)". Cuando se devuelve la estructura modificada se sobreentiende que es una copia de la estructura original.5.1. Complejidad
"Primero el metodo de ordenamiento de la lista de batallas, el cual asumimos que ordena en $O(n log n)$"
¿Por qué asumimos? Aclarenlo ustedes mismos como parte de su respuesta. Digan que su algoritmo utiliza un algoritmo de ordenamiento que ordena en $O(n \log n)$. Si se refieren a la implementación de Python pueden referir a la documentación.
6. Mediciones temporales
Los gráficos están bien. Algunos items para mejorar:
Otras observaciones
No vi nada en el informe sobre el punto 5:
Realizar ejemplos de ejecución para encontrar soluciones y corroborar lo encontrado. Adicionalmente, el curso proveerá con algunos casos particulares que deben cumplirse su optimalidad también..
Podrían por ejemplo haber hecho un mini seguimiento del algoritmo óptimo usando los ejemplos que usaron en la sección 3. Propuesta de Solución para mostrar que los otros algoritmos no funcionaban, y sumar los resultados de los provistos por la cátedra.
La idea del punto es que hagan algún seguimiento/ejemplo sencillo de la ejecución de su algoritmo y lo pongan en el informe.
La consigna dice "Debe ser claro cómo ejecutar el programa pasando por parámetro un set de datos como los que se dan de ejemplo". Su programa no toma ningún parámetro sino que hay que copiar el archivo a
entrada.txt. Intenten para el próximo TP hacer que el programa tome el path del archivo como argumento de la línea de comandos para facilitar un poco las pruebas. Otro corrector los hubiera mandado a reentrega por esto, se hace mucho más complicado ejecutar las pruebas de nuestro lado de manera rápida de esa forma...Ya como detalle también podría estar bueno que imprima por pantalla el resultado de la ejecución (no el orden de las batallas pero si el coeficiente).