fanusaez/tda-g04

Respositorio de los TPs de la materia Teoria de Algoritmos

tda-g04's Issues

TP Aprobado: 8 (Ocho)

Algoritmo por BackTracking

Una poda que se puede aplicar es evitar agregar un elemento y explorar su rama si ese elemento no permite Hittear ningún subset adicional a los ya hitteados por el resto de los elementos.

En ese sentido los tiempos resultantes de algoritmo de Backtracking podían mejorarse, especialmente si se tomaba otro enfoque al mismo, buscando subconjuntos que aún no hayan sido satisfechos y agregando jugadores de los mismos, por supuesto también por Backtracking

Sin embargo, en el caso concreto de ’10 todos’, la estrategia de poda se revela como ineficaz.
En este contexto particular, no podemos descartar ramas de la soluci´on durante la exploraci´on, ya
que la soluci´on ´optima requiere seleccionar una cantidad de jugadores equivalente a la cantidad
de subconjuntos. Es decir, no podremos descartar soluciones en donde la longitud de la asignaci´on
que estamos explorando sea mayor a la mejor asignaci´on encontrada hasta el momento

Es decir, empirícamente la cantidad de elementos en cada subconjunto es también relevante, además de la cantidad de elementos totales y la cantidad de subconjuntos

Un gráfico con las mediciones de tiempo tomadas nos pueden ayudar a entender de qué manera crecen los tiempos en función de las diferentes variables

Aproximaci´on

wi es siempre 1 ya que no hay penalidades de peso para cada elemento

apariciones_ordenado = dict ( sorted ( apariciones . items () , key = lambda item :
item [1] , reverse = True ))

No es necesario hacer ordenamiento por cada iteración. Cada iteración se requiere solamente el elemento más grande. Eso se puede hacer con la búsqueda del máximo

La funci´on es soluci´on verifica si la asignaci´on actual constituye una soluci´on v´alida revisando
cada subconjunto. La complejidad de esta funci´on es O(m ∗ n), donde m es la cantidad de subconjuntos y n es el tama˜no promedio de cada subconjunto. En el peor caso, se deben revisar todos los
subconjuntos para determinar si la asignaci´on actual es una soluci´on.

No se está teniendo en cuenta que se ordena varias veces

Si acotamos, podemos concluir que la complejidad temporal del algoritmo es

Las complejidades calculadas se constantan de forma empírica? Los niveles de crecimiento empírico coinciden con los calculados teóricamente?

TP Aprobado: 8 (Ocho)

El análisis de optimalidad del algoritmo es acertado.

Variabilidad de los valores

Buscabamos que se analice a su vez si estos valores afectan de alguna manera a la complejidad temporal, cosa que en este caso se podría verificar que no ocurre

Casos de prueba

Para los casos de prueba se podría especificar de qué manera se logró identificar el valor óptimo, como parte del diseño de la prueba.
En los casos de test de optimalidad con pocos elementos, el tiempo resultante es siempre el del último ayudante. Vale la pena agregar otras pruebas en el que este no sea el caso, más allá de pruebas aleatorias o que involucran archivos

Mediciones

Creo que recomendaría que para cada n se corra más veces el algoritmo, en promedio ayuda a que la curva sea más fiel a la teoría

No teman agregar al informe apartados sobre cómo fue la metodología de creación de los sets de datos, pueden incluso embeber código relevante si lo consideran necesario

TP Aprobado: 8 (Ocho)

Pero solo con esta variable resulta imposible poder determinar para un d´ıa i el ´optimo solo
teniendo en cuenta el ´optimo de d´ıas anteriores. Para poder plantear la ecuaci´on de recurrencia,
necesitamos una variable m´as, que por la forma en que se plantea la energ´ıa disponible, conviene
que sea ”d´ıas desde el ´ultimo descanso”.

sí a todo, pero, por qué? Se siente apresurada la conclusión sin un desarrollo o justificación

m´ax0≤d≤1 P(k − 2, d) + m´ın(sk, e1)

Un error en la ecuación de recurrencia, debería ser: m´ın(s1, ek), no m´ın(sk, e1)

Luego el d´ıa k se va a generar un beneficio de min(sk, e1).

Misma confusión

Caso d = 0:
Es el caso donde no hay descansos en k d´ıas

Es raro el caso d=0, pareciera ser el mismo caso de d mayor a 1 pero con un valor igual a la cantidad de días transcurridos. En ese sentido, siempre se puede asumir que antes de comenzar con los entrenamientos el equipo llega descansado, por lo tanto el primer día de entrenamiento siempre hay una energía disponible s1

Paso a dejarles otra metodología de resolución, más que nada para que sepan de su existencia y vean algo raro que tiene, que a veces podemos hacer crecer los subproblemas desde el final hacia el principio

Paso a mostrarles como podría quedar la ecuación de recurrencia considerando:

las dos variables días i y descanso hace días k
Sabiendo que en el último día n lo conveniente es siempre entrenar (aunque no sabemos cuántos días seguidos venimos entrenando), el proceso sería dar vuelta el problema y comenzar calculando desde el día n, bajando hasta 0.
De cualquier manera, esto sigue implicando hacer crecer el tamaño de los subproblemas, así:
para todo k posible, los subproblemas más pequeños involucran un solo día, el día n
luego
para todo k posible, crecemos e involucran dos días, el día n y el n-1
etc

∀i, k ∈ N;i, k < n; k ≤ i
OPT[i, k] = max(min(ei; sk) + OP T[i + 1, k + 1]; OP T[i + 1, 1])

De esta manera el óptimo siempre se refiere a un día i+1, que siempre fue calculado previamente.
El resultado final queda en el origen 0,0 de la matriz

1 def obtener_matriz_optima ( e_de , e_dis ):

No sé si nos beneficia cambiar la terminología respecto del resto de la explicación

LLeno la matriz para el caso donde nunca se toma un descanso .

Se trata de un caso particular o puede ser resuelto por el algoritmo general?

Ahora analizando todo en conjunto la complejidad total deber´ıa calcularse como:

En otras palabras, para n^2-n casilleros, cada casillero se calcula en tiempo constante, dando una complejidad de O(n^2)
Para n-2 casilleros, cada uno de ellos se calcula en O(n), aportando otro término O(n^2).
Dando O(n^2) en total

Esto significa que es necesario evaluar todas las posibles
combinaciones de subproblemas para determinar cu´al es la mejor soluci´on global.

Esta exploración en muchos casos es implícita, ya que podemos descartar casos que sabemos que no son óptimos.
De lo contrario, para hacer una exploración explícita se deberían explorar la cantidad exponencial de posibilidades que este problema plantea.

Siendo que hay que explorar todas las soluciones la complejidad temporal del algoritmo se
mantendr´ıa constante sin importar la variabilidad de los valores

Esta no es una buena justificación. En realidad se justifica dado que los valores numéricos no son parte de la complejidad temporal, solamente depende de la cantidad n

Medici´on 1

Se podría por ejemplo graficar para cada n el valor del (tiempo consumido/n), el gráfico resultante debería asemejarse a una recta.