[Raul C]

Voy con otra duda. Esta vez de reducción de algoritmos.

Dados los siguientes problemas:
PARES IMPARES: Dado un vector de numeros enteros, devuelve CIERTO si la suma de los elementos de las posiciones pares es igual a la suma de los elementos de las posiciones impares, FALSO en caso contrario.
SUMA PARES: Dado un vector de enteros v y un entero k, devuelve CIERTO si la suma de todos los elementos en las posiciones pares de v es igual a k, FALSO en caso contrario.

voy a poner algunas funciones utilizadas en las funciones de reducción dadas.
La funcion append añade un elemento a un array.
La funcion MOD devuelve el resto de la división de dos números.
La funcion DIV devuelve el resultado de la división entera de dos números.

Donde tenemos que ver  si las siguientes son funciones de reducción polinomiales validas.
PARES IMPARES \leq{} SUMA PARES

Pego el algoritmo en foto.


Yo creo que es posible la reducción, PARES IMPARES ≤p SUMA PARES es válido puesto que son dos problemas polinomicamente equivalentes y cómo podemos ver el coste de ambos es de O(n).

¿Cómo lo ves?

[martiniano]

Hola Raul C.

Es mejor que cuando plantees un nuevo problema lo hagas en un hilo aparte. Así si alguien quiere hablar sobre el problema antiguo puede hacerlo manteniendo un cierto orden. He dividido yo el hilo por eso.

Voy con otra duda. Esta vez de reducción de algoritmos.

Dados los siguientes problemas:
PARES IMPARES: Dado un vector de numeros enteros, devuelve CIERTO si la suma de los elementos de las posiciones pares es igual a la suma de los elementos de las posiciones impares, FALSO en caso contrario.
SUMA PARES: Dado un vector de enteros v y un entero k, devuelve CIERTO si la suma de todos los elementos en las posiciones pares de v es igual a k, FALSO en caso contrario.

voy a poner algunas funciones utilizadas en las funciones de reducción dadas.
La funcion append añade un elemento a un array.
La funcion MOD devuelve el resto de la división de dos números.
La funcion DIV devuelve el resultado de la división entera de dos números.

Donde tenemos que ver  si las siguientes son funciones de reducción polinomiales validas.
PARES IMPARES \leq{} SUMA PARES

Pego el algoritmo en foto.

Yo creo que es posible la reducción, PARES IMPARES ≤p SUMA PARES es válido puesto que son dos problemas polinomicamente equivalentes y cómo podemos ver el coste de ambos es de O(n).

Cómo lo ves?

Más bien lo que demuestra que un problema se puede reducir en tiempo polinómico al otro es precisamente el algoritmo que adjuntas. En cuanto al mismo, yo lo veo bien, lo único que no veo necesario crear un nuevo array con los términos pares del otro. Diría que si aplicas el subprograma SUMA_PARES al vector original también funciona.

Otra cosa. El "cómo" que te pongo en rojo pregunta algo o lo enuncia. Si es lo primero la frase debería ir entre signos de interrogación. Si es lo segundo diría que le sobra la tilde al "cómo". He supuesto que era lo segundo.

Un saludo.

[Raul C]

Muchas gracias, yo también lo veo asi.