mrti259 / tda-i-tps Goto Github PK

Hola! Les dejo por acá las correcciones.

• Dicen que no puede resolverse por medio de un algoritmo greedy y plantean una idea de contraejemplo. Esto es conceptualmente incorrecto: plantean una idea de un algoritmo greedy que no funciona, eso no significa que ningún algoritmo greedy puede obtener la solución óptima.
• Justificación o explicación de cómo llegan a la ecuación de recurrencia: porfis creeme.
• La ecuación de recurrencia parece estar planteada al revés: dependen de valores posteriores en vez de anteriores. Si bien funciona y es completamente correcto, no les recomiendo para nada afrontar problemas de programación dinámica de esta forma.
• No es Memorización, es Memoización (detalle menor, pero lo menciono, memoization).
• Como recomendación: separar la resolución de PD de la reconstrucción de la solución. Esto para asegurarse a nivel programático que cada función haga una cosa, y además para facilitar entender y analizar bien la complejidad de cada cosa. En este caso es medio obvia la complejidad del algoritmo de PD, pero el de la reconstrucción no es del todo obvio, y si lo es, como mínimo es interesante de mencionar cómo varía su comportamiento respecto a los valores de $s_i$ y $e_i$.
• En particular, ustedes mencionan que esto es lineal. Si los valores de $s_i$ son muy grandes (es decir, conviene siempre entrenar), entonces efectivamente va a ser lineal (es el mejor caso posible), pero si $s_1$ es medianamente grande y $s_2$ es chico (y de allí para abajo), seguro va a terminar conviniendo intercalar entrenamientos con descansos, con lo cual hay que ir buscando máximos, terminando en algo peor que lineal. Corríjanme si me equivoco, es lo que entiendo así nomás del código, pero hay algo que no me termina de convencer de lo mismo que estoy leyendo yo.

Lo más importante de lo que marco son las primeras dos cosas.
Dicho esto, la nota del tp es 8.

A la demostración de ser NP-Completo le falta algo: no hay límite en elegir una variable y su complemento (que sería nuestra interpretación de ser true o false). ¿Por qué dicen además que supongamos k = 2? ¿Ponen alguno cualquiera? Si mis cláusulas son x1 y x1 (por separado), entonces si K = 2 van a decir que es en efecto posible obtener un hitting set de tamaño 2 cuando la expresión no es satisfacible. Esto lo van a tener que volver a hacer. Como recomendación: vayan por 3-SAT, de paso se simplifican un poco (la reducción es en sí la misma en ambos casos, pero al menos se simplifican un poco para pensarlo mejor).

Hola! Dejo por acá las correcciones:

• Sobre la demostración de si el problema está en NP, ver la cantidad de elementos de un conjunto es de tiempo constante. ¿De dónde sale el logaritmo? Luego, constante o logarítmico, $mathcal{O}(\log k + k)$ es $\mathcal{O}(k)$ (estoy obviando la n, que por supuesto sigue estando).
• A la demostración de ser NP-Completo le falta algo: no hay límite en elegir una variable y su complemento (que sería nuestra interpretación de ser true o false). ¿Por qué dicen además que supongamos k = 2? ¿Ponen alguno cualquiera? Si mis cláusulas son $x_1$ y $~x_1$ (por separado), entonces si K = 2 van a decir que es en efecto posible obtener un hitting set de tamaño 2 cuando la expresión no es satisfacible. Esto lo van a tener que volver a hacer. Como recomendación: vayan por 3-SAT, de paso se simplifican un poco (la reducción es en sí la misma en ambos casos, pero al menos se simplifican un poco para pensarlo mejor).
• No pude ejecutar el programa como ponen en el readme. Lo traté de ejecutar desde este nivel tal cual indican en el readme (poetry run python tp3/selector.py <.....>/200_bis.txt, para ejecutar una prueba), y de otras formas, y hasta sin poetry, pero siempre tuve el mismo error:

Traceback (most recent call last):
  File "/Users/mbuchwald/Downloads/tda-i-tps/tp3/tp3/selector.py", line 3, in <module>
    from tp3.archivos import *
ModuleNotFoundError: No module named 'tp3'

• No está enunciado el modelo de programación lineal. Tuve que deducirlo de ver el código.
• No está hecha la demostración de la cota del algoritmo de aproximación que nosotros les propusimos.
• Al análisis del algoritmo greedy propuesto por ustedes habría estado bueno que le calculen una cota de aproximación empírica (no pedimos demostrada, pero al menos algo de análisis por ese lado).

Dicho esto, les pido que reentreguen al menos con la demostración correcta que el problema es NP-Completo, y la cota de aproximación del algoritmo de aproximación.
Lo demás es opcional. Y me indiquen qué debo hacer para poder ejecutar el programa para terminar de hacer unas validaciones.