- Arian Jarmolinski - 94727
- Fernando Buono - 103523
- Gabriel Katta - 105935
gabokatta / tda-2c2023 Goto Github PK
View Code? Open in Web Editor NEWRepositorio para TPs de Teoria de Algoritmos
Repositorio para TPs de Teoria de Algoritmos
Hola! Les dejo las correcciones del TP en orden de importancia:
Falta gran parte del punto 5. Se pedía calcular y demostrar una cota de
La justificación de la complejidad del algoritmo de backtracking esta muy escueta, no hacen un análisis real de su algoritmo.
La justificación de la complejidad del algoritmo greedy tiene algunos errores. Primero, no queda claro si
Asumiendo que sort_jugadores_por_frecuencia
no tiene complejidad seleccion_greedy
del algoritmo está bien.
En la demostración de que Hitting-Set es NP, dicen que "Esto se puede hacer en tiempo lineal, ya que el tamaño de
Es decir, aclarar que
Desde ya, decir que "estamos realizando una operación constante (verificar la intersección de
Sobre el algoritmo de backtracking, en general esta bien, pero les dejo algunos puntos de mejora:
Estas 2 líneas (líneas 3 y 4 del informe) son innecesarias:
if len(seleccion_actual) < len(seleccion_final):
seleccion_final = seleccion_actual.copy()
Al estar constantemente podando si la selección actual es peor que la mejor hasta el momento, siempre que lleguen a esta parte del código, la selección actual va a ser mejor que la final.
De la misma manera, el if jugador_actual not in seleccion_actual:
de la línea 13 no hace nada. Fijense que como pasan i + 1
en las siguientes llamadas recursivas no hay forma de agarrar a un jugador que ya este seleccionado. No sé si les queda del todo claro como estan explorando el espacio de soluciones.
Esto no es una corrección, nada más un comentario: me llamó la atención la forma en la que recorren el espacio de soluciones.
Para resolver el hitting set por backtracking, hay 2 formas de pensarlo: recorriendo por jugadores o recorriendo por sets. Ustedes (al igual que yo) lo pensaron recorriendo jugadores. Ahora bien, cuando se van recorriendo los jugadores, en definitiva hay 2 opciones: que un jugador sea parte de la solución o que no lo sea.
Les comento como lo pensé yo. Que haya 2 opciones para cada jugador me llevó a pensar que para cada llamada recursiva, haya otras 2 llamadas, una con el jugador y otra sin el jugador. Les dejo una de mis soluciones:
def hitting_set(
elements: list[str],
i: int,
pending_sets: list[set[str]],
chosen_elements: list[str],
best_solution: list[str],
) -> list[str]:
if i == len(elements) or len(chosen_elements) + 1 >= len(best_solution):
return best_solution
element = elements[i]
chosen_elements.append(element)
new_pending_sets = [s for s in pending_sets if element not in s]
if len(new_pending_sets) == 0:
best_solution = chosen_elements.copy()
chosen_elements.pop()
return best_solution
best_solution = hitting_set(
elements,
i + 1,
new_pending_sets,
chosen_elements,
best_solution,
)
chosen_elements.pop()
best_solution = hitting_set(
elements,
i + 1,
pending_sets,
chosen_elements,
best_solution,
)
return best_solution
Notarán que la mayor diferencia entre esa solución y la suya es que hay 2 llamadas recursivas pero no hay ningún loop. Ustedes la opción de no agregar un jugador la consideran en las iteraciones del loop después de haber ya probado agregando el jugador. Me pareció relevante comentarles esta alternativa, aunque la que hicieron es también válida.
un vértice de cada arista
de Estuvimos discutiéndolo, y les voy a tener que pedir que me hagan una reentrega con el primer punto de la corrección (segunda parte punto 5 del trabajo prácitco), porque es una parte bastante importante del trabajo. Se busca que hagan algo parecido a lo de la clase de algoritmos de aproximación.
Les extiendo la fecha de reentrega hasta el lunes 18, para que puedan centrarse en el examen del viernes. Lo único que les pido es un anexo con el cálculo y la demostración del
Cualquier consulta, avísenme. Saludos!
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
matriz representa la energía que está siendo utilizada". Por lo tanto, entiendo que
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
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
La primera línea tiene un error que corresponde a lo otro que les dije arriba: Salvo que 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
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
En el algoritmo original de ustedes, asignan el valor de haber descansado ayer a una posición de la matriz con ganancia[i][j] = max(ganancia_entrenando, ganancia_descansando)
(con ganancia_descansando
. Eso significa que durmieron en el día
Una última aclaración de esto. Ustedes
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:
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!
Buenas! Les dejo la corrección del TP1. Está aprobado, la nota es un 8.
Ustedes llegan a la conclusión correcta respecto al algoritmo óptimo, aunque la idea del TP era más bien que vayan en el sentido opuesto. Hicieron las pruebas sobre todos los algoritmos que propusieron y con eso llegan a la conclusión de cual de ellos es el óptimo. La idea del TP es más bien que ustedes propongan esos algoritmos, digan cuál es el óptimo y por qué, y que luego corroboren con esas pruebas en código. De todas formas, aclaro que lo que hicieron no está necesariamente mal.
La corrección principal sería respecto a la justificación del algoritmo óptimo. Dicen en la sección 2.4 que "Esta solución a simple vista resultó ser la más intuitiva, ya que le da completa prioridad a los asistentes en lugar de a Scaloni, el cual ya se planteó que el orden en que ve los videos no es relevante" y en la conclusión "Por ende lo que es variable y optimizable en este problema son los tiempos de los asistentes y como estos se solapan entre si". Todo eso esta perfecto, y si bien no exigimos una demostración formal de optimalidad, en la justificación no explican por qué justamente al hacer ese ordenamiento estamos reduciendo el tiempo total. ¿Qué es lo que logran ordenando de mayor a menor esos tiempos?
Más allá de eso, el TP esta bastante bien. Les dejo como sugerencia revisar la ortografía (faltan bastantes tildes), y 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.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.