gabokatta / tda-2c2023

Repositorio para TPs de Teoria de Algoritmos

Repositorio de Trabajos Práctios - Teoría de Algoritmos

Integrantes:

• Arian Jarmolinski - 94727
• Fernando Buono - 103523
• Gabriel Katta - 105935

---

tda-2c2023's Issues

Corrección TP3

Hola! Les dejo las correcciones del TP en orden de importancia:

1. Falta gran parte del punto 5. Se pedía calcular y demostrar una cota de $r(A)$ matemáticamente, y luego verificarlo de forma empírica, no calcular la cota con las mediciones.

2. La justificación de la complejidad del algoritmo de backtracking esta muy escueta, no hacen un análisis real de su algoritmo.

3. La justificación de la complejidad del algoritmo greedy tiene algunos errores. Primero, no queda claro si $m$ es la cantidad de jugadores por pedido (ignorando que los pedidos tienen distinta cantidad de jugadores...) o la cantidad total de jugadores.

   Asumiendo que $n$ es la cantidad de pedidos y $m$ la cantidad total de jugadores, y en el peor caso que todos los jugadores estan en todos los pedidos, entonces sort_jugadores_por_frecuencia no tiene complejidad $O(m \times n \times \log(m))$. La complejidad del ordenamiento es $O(m \times \log(m))$ y la del loop $O(m \times n)$ por lo que la de la función es $O(m \times \log(m) + m \times n)$ = $O(m \times (\log(m) + n))$. La complejidad del otro loop en seleccion_greedy del algoritmo está bien.

4. 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 $C$ y $B_i$ es finito y conocido". No es incorrecto pero estaría bueno que aclaren cuál es ese tamaño finito y conocido, y que expliquen explícitamente como es que verifican que la intersección no es vacía.

   Es decir, aclarar que $C$ y $B_i$ tienen sí o sí menos de $n$ elementos, donde $n$ es la cantidad de jugadores, entonces se puede verificar la intersección en $O(n)$ usando tablas de hash o en $O(n^2)$ con un doble for.

   Desde ya, decir que "estamos realizando una operación constante (verificar la intersección de $C$)" si es un error más grave. Definitivamente no es una operación constante, a lo sumo es lineal.

5. 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.

6. En la verificación de la reducción:
   "Si existe un Hitting-Set $C'$ en $A$, entonces $C'$ interseca todos los subconjuntos de $A$. Por lo tanto, como $C'$ cubre al menos una arista de cada vértice un vértice de cada arista de $G$, $C'$ conforma un Vertex Cover en $G$."

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 $r(A)$ del la aproximación por programación lineal (no su algoritmo greedy), las demás correcciones no hacen falta.

Cualquier consulta, avísenme. Saludos!

Corrección TP2

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!

Corrección TP1

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.