Hola buenas, con un compañero pensamos una solución a este ejercicio, comparando con otras soluciones, vimos que no es similar a las demás y estamos en duda sobre si es correcta, gracias.
Hola.
¿El algoritmo da el resultado correcto si s=01, x=00, y=01?
¿Podés contarnos, en palabras, el razonamiento que lleva al algoritmo? Por ejemplo ¿cuáles son los subproblemas, cómo se relacionan entre sí, qué significa M[i,j]?
¿El algoritmo da el resultado correcto si s=01, x=00, y=01?
¿Podés contarnos, en palabras, el razonamiento que lleva al algoritmo? Por ejemplo ¿cuáles son los subproblemas, cómo se relacionan entre sí, qué significa M[i,j]?
Hola buenas, la idea de M(i,j) es la planteada en la sugerencia de la letra, en el ejemplo que mencionas, no me queda claro cual sería el resultado correcto ya que la secuencia de s equivale a y por lo cual es un prefijo de y (no estoy seguro si al ser la secuencia completa se sigue considerando como un prefijo), y además s(1) es prefijo de x. Por lo cual en este caso habrían dos valores de M verdaderos, estos serian M(1,1) y M(0,2).
Si no me equivoco, por la estructura y orden del algoritmo, lo primero que establece es que s(1) es igual a x(1), agrega 1 a la lista de indices, en la siguiente iteración entra al primer else y se verifica que s(2) = y(1), por lo cual se establece M(1,1) verdadero y finaliza el bucle while ya que i + j = n. Entonces el algoritmo devuelve M(1,1) (true), quizás el error es trivial y no lo estoy viendo, gracias de antemano
Si no me equivoco, por la estructura y orden del algoritmo, lo primero que establece es que s(1) es igual a x(1), agrega 1 a la lista de indices, en la siguiente iteración entra al primer else y se verifica que s(2) = y(1), por lo cual se establece M(1,1) verdadero y finaliza el bucle while ya que i + j = n. Entonces el algoritmo devuelve M(1,1) (true), quizás el error es trivial y no lo estoy viendo, gracias de antemano
Hola de nuevo.
Sí, el resultado en el ejemplo debería ser verdadero porque
es el entrelazado de la cadena vacía, que es prefijo de 
, e 
, que es prefijo de sí mismo.
Pero creo que no es lo que establecería el algoritmo. Comprueba que
es igual a 
, lo cual es correcto, pero luego compara 
primero con 
y luego con 
y en ambos casos es distinto (, que es 1, no es igual a , que es 0). Y entonces termina devolviendo falso.
En el ejemplo de la letra me parece que también fallaría al comparar
.
Entiendo que M[i,j] es lo que se sugiere en la letra, y estaría bien encaminado. Pero no se obtiene para cada par
, sino solo para 
de ellos. Al calcularlo no se usan los anteriores; de hecho se obtiene y no se hace nada con ellos (al final se devuelve M[i,j] pero podría devolverse verdadero, porque nunca se asigna falso). La razón de calcularlos podría ser para reconstruir la forma en que se debe hacer el entrelazado pero eso tampoco es necesario porque ese es el rol que le dan a listaIndices.
El valor de M[i,j] debería depender de los valores que se obtuvieron antes (para eso es la recurrencia que se sugiere en la letra). El ciclo, correctamente, crece según los valores de
. Por lo tanto M[i,j] debería depender de algunos M[i',j'] con 
.
¿Hasta acá estás de acuerdo?
Sí, el resultado en el ejemplo debería ser verdadero porque
es el entrelazado de la cadena vacía, que es prefijo de , e , que es prefijo de sí mismo.Pero creo que no es lo que establecería el algoritmo. Comprueba que
es igual a , lo cual es correcto, pero luego compara primero con y luego con y en ambos casos es distinto (, que es 1, no es igual a , que es 0). Y entonces termina devolviendo falso.En el ejemplo de la letra me parece que también fallaría al comparar
.Entiendo que M[i,j] es lo que se sugiere en la letra, y estaría bien encaminado. Pero no se obtiene para cada par
, sino solo para de ellos. Al calcularlo no se usan los anteriores; de hecho se obtiene y no se hace nada con ellos (al final se devuelve M[i,j] pero podría devolverse verdadero, porque nunca se asigna falso). La razón de calcularlos podría ser para reconstruir la forma en que se debe hacer el entrelazado pero eso tampoco es necesario porque ese es el rol que le dan a listaIndices.El valor de M[i,j] debería depender de los valores que se obtuvieron antes (para eso es la recurrencia que se sugiere en la letra). El ciclo, correctamente, crece según los valores de
. Por lo tanto M[i,j] debería depender de algunos M[i',j'] con .¿Hasta acá estás de acuerdo?
Bien, estoy de acuerdo, gracias por las respuestas, me había confundido un poco en como proceder con el ejemplo y lo hice mal, modifiqué algunas cosas tras tus observaciones, esto sería valido? Entiendo que no utiliza la recurrencia con i' y j' pero me queda la duda
Entrelazado (s,x,y,n) \{
Inicializar las variables i,j = 0
Inicializar lista listaIndices
Si s = x \{
Agregar los valores 1...n a listaIndices
Devolver true
\}
Si s = y \{
Devolver true
\}
Mientras i + j < n \{
pos = i + j + 1;
Si s(pos) = $x_{i+1}$ entonces
Incrementar i en uno
Agregar pos al final de listaIndices
Sino, si s(pos) = $y_{j+1}$
Incrementar j en uno
Sino
Terminar el programa y devolver falso
\}
Devolver true
\}
Entrelazado (s,x,y,n) \{
Inicializar las variables i,j = 0
Inicializar lista listaIndices
Si s = x \{
Agregar los valores 1...n a listaIndices
Devolver true
\}
Si s = y \{
Devolver true
\}
Mientras i + j < n \{
pos = i + j + 1;
Si s(pos) = $x_{i+1}$ entonces
Incrementar i en uno
Agregar pos al final de listaIndices
Sino, si s(pos) = $y_{j+1}$
Incrementar j en uno
Sino
Terminar el programa y devolver falso
\}
Devolver true
\}
El problema esencial sigue estando. Lo que este algoritmo incorpora es evitar el error en el caso particular en que se diera cuando ss es igual a xx o a yy. Creo que no corregiría el error en el ejemplo de la letra que te mencioné antes. Pero podemos modificar el pequeño ejemplo que puse antes. Agreguemos en elemento más y ahora s=010, x=00*, y=011 (el * significa que puede ser cualquiera). Ahora ss no es igual a xx ni a yy y se va a dar el mismo error que antes al procesar s2s2.
El problema es que este algoritmo es greedy, si el elemento de ss que está siendo tratado es igual al próximo elemento de xx decide emparejarlos y nunca cambia esa decisión. No puedo afirmar que este problema no se puede resolver con otro algoritmo greedy aunque me parece improbable. La idea, estando en el práctico correspondiente a Programación Dinámica es resolverlo mediante esta estrategia. Lo esencial es establecer un conjunto de subproblemas y entender como se relacionan entre sí, como dependen unos de otros, para resolverlos en orden.
En este caso las preguntas son ¿qué significa el subproblema (i,j)(i,j) del cual M[i,j] es su resultado?. ¿Qué subproblemas se necesita tener resueltos para resolver (i,j)(i,j), o sea, para calcular M[i,j]? (esto es muy parecido a uno de los problemas del teórico). Finalmente, una vez calculados todos los M[i,j], ¿cómo se usa esa información para resolver el problema planteado, esto es, si ss es el entrelazado de prefijos de xx e yy.
Empezando por la primera pregunta, ¿qué significa que M[i,j] sea verdadero? La sugerencia de la letra es una buena guía.
El problema es que este algoritmo es greedy, si el elemento de ss que está siendo tratado es igual al próximo elemento de xx decide emparejarlos y nunca cambia esa decisión. No puedo afirmar que este problema no se puede resolver con otro algoritmo greedy aunque me parece improbable. La idea, estando en el práctico correspondiente a Programación Dinámica es resolverlo mediante esta estrategia. Lo esencial es establecer un conjunto de subproblemas y entender como se relacionan entre sí, como dependen unos de otros, para resolverlos en orden.
En este caso las preguntas son ¿qué significa el subproblema (i,j)(i,j) del cual M[i,j] es su resultado?. ¿Qué subproblemas se necesita tener resueltos para resolver (i,j)(i,j), o sea, para calcular M[i,j]? (esto es muy parecido a uno de los problemas del teórico). Finalmente, una vez calculados todos los M[i,j], ¿cómo se usa esa información para resolver el problema planteado, esto es, si ss es el entrelazado de prefijos de xx e yy.
Empezando por la primera pregunta, ¿qué significa que M[i,j] sea verdadero? La sugerencia de la letra es una buena guía.
Bien, claro ahí lo entendí, muchas gracias