Pr7 Ej1

Pr7 Ej1

de Bruno Scanziani Etchebarne -
Número de respuestas: 6

Buenas, quería consultar si la idea de esta solucón es correcta.

El algoritmo se basa en llevar un registro de la calse de equivalencia a la que pertenece cada tarjeta. En un principio todas estan en su misma clase. Luego, a medida que voy poniendo tarjetas en la misma clase, chequedo si la calse a la que le acabo de agregar un elemento tiene n/2 o más elementos. Si esto se cumple, por sugerencia sé que debo retornar true y salir, de lo contrario debo continuar.

Algoritmo: 


// arreglo para saber a que clase de equiv pertenece cada tarjeta

claseEquiv[t] = t para toda tarjeta t

largo = claseEquiv.largo()


Algoritmo(tarjetas, inf, sup)

// Caso base

if (sup == inf + 1) 

if (equivalentes([tarjetas[inf], tarjetas[sup]))

// Si son equivalentes actualizo la calse de equiv de una de las tarjetas

claseEquiv[tarjetas[inf]] = claseEquiv[tarjetas[sup]]

// Chequedo si hay n/2 tarjetas en la clase de equiv de tarjetas[sup]

contador = 0

foreach t en claseEquiv

if (claseEquiv[t] == claseEquiv[tarjetas[sup]]

contador++

endif

endfor

if contador >= largo/2

return true

else

return false

endif

else

return false

else

//Paso recursivo

return Algoritmo(tarjetas, inf, (sup / 2) - 1) || Algoritmo(tarjetas, (sup / 2), sup)

endif

end

En respuesta a Bruno Scanziani Etchebarne

Re: Pr7 Ej1

de Bruno Scanziani Etchebarne -
Buenas, corrigo, me di cuenta de que este algoritmo no cumple los requerimientos de tiempo, porque en los pasos inductivos siempre hace el for de largo n. Para solucionar esto agregué un array cantElemEnClase que me lleva la cuenta de cuantos elementos tiene cada calse de equivalencia. Con esto puedo hacer en O(1) lo que antes hacía en el for en O(n)

Algoritmo:

// arreglo para saber a que clase de equiv pertenece cada tarjeta
claseEquiv[t] = t para toda tarjeta t
// arreglo que me indica cuantos elementos tiene cada clase de equivalencia
cantElemEnClase[t] = 1 para toda clase de equiv t
largo = claseEquiv.largo()

Algoritmo(tarjetas, inf, sup)
// Caso base
if (sup == inf + 1) 
if (equivalentes([tarjetas[inf], tarjetas[sup]))
// Si son equivalentes actualizo la calse de equiv de una de las tarjetas
claseEquiv[tarjetas[inf]] = claseEquiv[tarjetas[sup]]
cantElemEnClase[tarjetas[sup]]++
if cantElemEnClase[tarjetas[sup]] >= largo/2
return true
else
return false
endif
else
return false
else
//Paso recursivo
return Algoritmo(tarjetas, inf, (sup / 2) - 1) || Algoritmo(tarjetas, (sup / 2), sup)
endif
end
En respuesta a Bruno Scanziani Etchebarne

Re: Pr7 Ej1

de Fernando Fernandez -

Hola Bruno.

Me parece que el algoritmo no es correcto.

Si lo entiendo bien, lo que hace es comparar las tarjetas 2i-1 y 2i para cada i desde 1 hasta n/2. Y el resultado es verdadero si y solo si en alguna de las comparaciones se detectó que son equivalentes.

Y si es así, si, por ejemplo, las únicas equivalentes son la 1 y la 2 el resultado será verdadero cuando debería ser falso. 

En el otro sentido, si n es impar y las tarjetas de las posiciones impares son equivalentes, el resultado será falso cuando debería ser verdadero.

Está bien que intentes dividir el problema en dos subinstancias de la mitad del tamaño de la original (hay un error ahí, porque sup/2 sería el punto medio solo si inf es 1 o 0; debería ser (inf+sup)/2). Pero no parece que se pueda lograr si la división es algo tan sencillo como calcular el punto medio y la combinación de resultados es algo también muy sencillo como calcular un OR. ¿Podés formular la relación de recurrencia del tiempo de ejecución?

Saludos,
En respuesta a Fernando Fernandez

Re: Pr7 Ej1

de Agustín Marcio Ribeiro García -
Buenas! quería saber si este algoritmo para el ejercicio seria correcto. Desde ya muchas gracias!
Adjunto imagen_2024-10-10_215723514.png
En respuesta a Agustín Marcio Ribeiro García

Re: Pr7 Ej1

de Fernando Fernandez -
Hola Agustín.

Hay un problema similar al del algoritmo de Bruno. En las llamadas recursivas no se hace nada con los resultados de las subinstancias.

¿Podés explicar cómo intentarías demostrar que el algoritmo es correcto?

Saludos
En respuesta a Fernando Fernandez

Re: Pr7 Ej1

de Juan Tomás Chimaylov Beloqui -

Buenas, quería saber si puedo rescatar algo de esto para seguir con el ejercicio:

Para el caso de que exista una solución creo que acá se cubren todos las posibilidades. (Ver imagen de abajo).
Las x marcadas son tarjetas que pertenecen a la misma clase de equivalencia.
(H):Tiene que pasar que al menos en el unos de los subconjuntos halla |x| >= (n/2.2^j) + 1 siendo j el nivel del árbol.



Entonces supongo que para negar la existencia de (n/2) + 1 tarjetas equivalentes basta con que ambos subconjuntos no cumplan (H). (Linea 27 del código).
Y si se cumple (H) (linea 21) en un conjunto, hay que ver el otro para encontrar tarjetas equivalentes a x (linea 22) de forma que sumando ambos subconjuntos sean |x|>=(|L|/2) +1.
Para el algoritmo de abajo  use como guía Sort-and-Count del libro y tuve que hacer una función para contar las equivalentes.



(a) y (c). Como (creo) que aplique la forma de divide y vencerás de manera correcta, la funcíon de contar tarjetas del subconjunto se aplica en A y B, luego |A|=n/2 , |B|=n/2 entonces esta función seria O(n). Y por ser un árbol balanceado la profundidad es de Θ(log⁡n).
Luego O(n.logn) el tiempo de ejecución.

(b) Corrección del algoritmo:

La función cuenta la cant. de equivalencias en el conjunto que se le pasa a la llamada recurisva,  de un representante perteneciente al subconjunto invocado por la llamada.

Existen (n/2) +1 tarjetas equivalentes en L <=> returno un representante.
(=>) Si se cumple el if de la linea 23 el algoritmo encontró un representante tal que el cardinal de su clase de equivalencia digamos x, cumple que |x| > (n/2) y el algoritmo devuelve una tarjeta representante de esa clase.

(<=) Por contra reciproco. No se retorno un representante, el algoritmo termino todas las llamadas recursivas y nunca se cumplio if de la linea 21 entonces  nunca se cumplió (H),  nunca se cumplió el if de la linea 23 por lo cual para cada una de las tarjetas y su clase respectiva de equivalencia digamos x, se tuvo que |x|<= (n/2). Entonces no existen (n/2) +1 tarjetas equivalentes en L.

ojala se entienda algo saludos.
 

En respuesta a Juan Tomás Chimaylov Beloqui

Re: Pr7 Ej1

de Guillermo Apollonia -
Hola Juan, la idea está bastante bien.
Sin embargo, veo algún detalle en el algoritmo.

Se llama correctamente de forma recursiva para el conjunto A. Esa llamada recursiva de la línea 19 retorna una tarjeta si hay más de la mitad de tarjetas que pertenecen a la misma clase en ese subconjunto A. Y podría devolver la cantidad para que no sea necesario hacer la llamada a contar de la línea 20. Y el if de la línea 21 es simplimente verificar que t_j no sea null. Este es un detalle de implemtanción digamos.

Ahora, en la llamada de la línea 26 tenés que hacer lo mismo que a la salida de la llamada de la recursión para el conjunto A. Tenés que contar para saber si llegas a la mitad + 1 del total. Lo que está en las líneas 21-24 tenés que adicionarlo luego de la llamada recursiva del paso 26.