lunes, 20 de enero de 2014

El problema de la suma de los subconjuntos

En esta ocasión vamos a hablar de un problema que es muy sencillito de entender, pero que resulta muy complicado resolver. Lo normal en informática, vamos. Se trata del problema de la suma de los subconjuntos: dado un conjunto de números enteros tenemos que encontrar un subconjunto cuya suma sea 0, en el caso de que dicho subconjunto exista. Por ejemplo, si tenemos el conjunto formado por los números {−7, −3, −2, 5, 8}, tendríamos que devolver {−3, −2, 5}, ya que éstos suman 0. El problema de la suma de subconjuntos es importante porque se trata de un problema NP-Completo. Es decir, es muy fácil verificar si una solución es correcta (tan sólo hay que sumar los valores y ver si da 0), pero al día de hoy no se conoce ningún algoritmo que lo resuelva de manera eficiente (en un tiempo que sea del orden de un polinomio).
En esta ocasión vamos a resolver el problema utilizando la fuerza bruta, y mediante un algoritmo basado en la programación funcional, porque no sólo de algoritmos imperativos vive el hombre. Y más concretamente, utilizando el entorno de cálculo estadístico R, que para esto de manejar conjuntos de datos se apaña muy bien.
En primer lugar vamos a definir nuestro conjunto de enteros:
c <- c(−7, −3, −2, 5, 8, 9, 15, 6, 4, -11, -13, -1, 1, -14, 2, 3, 5, -14)
En este caso, formado por 18 enteros. No pongáis muchos más, porque el algoritmo de la fuerza bruta que vamos a utilizar tiene un tiempo de ejecución del orden de 2^n, donde n es el número de enteros, y con 18 ya nos llevará un rato.
A continuación calculamos todos los subconjuntos posibles de nuestro conjunto inicial, excepto el conjunto vacío, por razones obvias (en esta entrada expliqué un algoritmo muy bonito que resuelve cómo hacer esto):
combinaciones <- lapply(1:length(c), function(x) combn(c, x))
Para cada uno de estos subconjuntos calculamos su suma:
suma <- lapply(1:length(combinaciones), function(x) apply(combinaciones[[x]], 2, sum))
Y de estas sumas nos quedamos aquellas que valen 0:
cierto <- lapply(1:length(suma), function(x) ifelse(suma[[x]] == 0, TRUE, FALSE))
A continuación miramos qué subconjunto es el que corresponde a las sumas que valen 0:
soluciones <- lapply(1:length(combinaciones), function(x) combinaciones[[x]][,cierto[[x]]])
Y finalmente, limpiamos un poquito el resultado para que quede mono:
soluciones[sapply(soluciones, function(x) length(x)==0)] <- NULL
En futuras entradas veremos otros algoritmos más eficientes que la fuerza bruta para resolver este problema.
Como ejercicio dejo propuesto escribir un programa que nos diga si dado un conjunto es posible dividirlo en dos subconjuntos que sumen lo mismo. Y para aquellos lectores a los que no les guste la programación funcional, les dejo como ejercicio que escriban el mismo algoritmo utilizando un lenguaje imperativo, por ejemplo, C. ¡Ánimo!

miércoles, 15 de enero de 2014

Algoritmo para calcular los subconjuntos de un conjunto

A veces, para resolver un problema, nos encontramos con la necesidad de calcular todos los subconjuntos posibles de un conjunto. En esta entra de blog vamos a ver un algoritmo que realiza este cálculo. Si tenemos el conjunto {a, b, c}, el conjunto de todos los subconjuntos posibles sería {{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}} (ocho elementos, o 2^3, tal y como esperábamos). Nuestra amiga la recursividad nos puede dar una solución muy bonita a este problema.
Primero vamos a definir una función F que dado un conjunto de subconjuntos, y un elemento, añada ese elemento a todos los subconjuntos. El cómo trabaja esta función es más fácil de entender con un ejemplo: si tenemos el siguiente conjunto de conjuntos X={{},{a},{b}} y el elemento c, tendríamos que F(X, c) = {{c},{a,c},{b,c}}. Es decir, hemos añadido c a cada uno de los subconjuntos contenidos en X.
Lo segundo que necesitamos es una condición de parada de la recursividad. En este caso vamos a parar cuando nos pregunten los subconjuntos del conjunto vacío, que sólo tiene un elemento (2^0 es 1, ¿verdad?), a saber, el conjunto formado por el conjunto vacío. Ojo, no es lo mismo el conjunto vacío {}, que el conjunto formado por el conjunto vacío {{}}, ya que F({}, a) = {} y F({{}}, a) = {{a}}.
Ya tendríamos todo lo necesario para dar el algoritmo recursivo:
función subconj(S)
    si S = {} entonces
        retorna {{}}
    si no
        T  ← S menos e
        PT ← subconj(T)
        retorna PT unión F(PT, e)
Si lo que tenemos es el conjunto vacío {}, retornamos el conjunto formado por el conjunto vacío {{}}, tal y como habíamos dicho. Y si lo que tenemos es un conjunto no vacío, lo que hay que hacer es quitarle un elemento e cualquiera (S menos e), calcular los subconjuntos de este nuevo conjunto más pequeño (PT), y retornar estos subconjuntos junto con otra copia de ellos mismos a los que les habremos añadido el elemento e. Así si PT := {{},{a}} tenemos que PT unión F(PT, b) = {{},{a},{b},{a,b}}.
Yo creo que todo este galimatías que se forma cuando hablamos de conjuntos se debe fundamentalmente a un problema de notación, o a que no entendemos bien el concepto de conjunto. A modo de ejemplo tenemos la paradoja de Bertrand Russell, que define M como el conjunto de todos los conjuntos que no son subconjuntos de sí mismos, y a continuación se pregunta si M pertenece a sí mismo. Si respondemos que sí tenemos que no debería pertenecer, pero si respondemos que no, sí que debería pertenecer. Luego aquí hay algo que no está funcionando bien.

jueves, 2 de enero de 2014

Una explicación divertida del problema de la parada

El otro día estaba haciendo una toma de requisitos para un cliente, una empresa de seguridad en informática. Mi cliente dispone un producto de seguridad muy interesante: tu le envías el binario de tu programa, y él te dice si el programa es seguro o presenta vulnerabilidades. La plataforma es muy modular, y tiene una serie de plugins, programas independientes, que realizan los análisis. Así, el plugin1 realiza un tipo de análisis sobre el programa, el plugin2 realiza otro tipo de análisis diferente, etc. El problema es que ciertos plugins pueden requerir mucho tiempo de cálculo. Y lo que es peor, a veces puede incluso que no terminen nunca. Así, si un análisis concreto lleva una semana ejecutándose, no sabemos si es porque está tardando mucho, o simplemente porque se ha atascado y nunca terminará. Y si tenemos en cuenta que mi cliente cobra por hora de cálculo, son muchos los usuarios de su plataforma que se quejan, y que preferirían tener la seguridad a priori de que el análisis terminará en algún momento.

Así que mi cliente lo que quería es que escribiese un nuevo módulo, llamado Parada(A, P), que dado un plugin de análisis A y un programa P, devolviera CIERTO si el análisis iba a terminar, o FALSO si no (no era necesario hacer ningún tipo de estimación del tiempo que iba a requerir el análisis, soló saber si iba a terminar). El problema es que el cliente me pedia también que el modulo Parada() fuese lo suficientemente genérico, no sólo para poder trabajar con los plugins de análisis existentes acualmente, sino también sobre cualquier otro plugin que incorporase en el futuro, sin que fuera necesario modificar el códogo de Parada(), lo cual es, simplemente, imposible. Ya que nos encontramos con el famoso Problema de la Parada.

Supongamos que conseguimos implementar el módulo Parada(A, P) genérico que nos piden. Parada recibiría dos argumentos: el análisis o plugin a aplicar A, y el programa P a analizar (recordemos que los análisis se aplican sobre los programas, es decir A(P)). Y escribimos un nuevo plugin de análisis llamado C que intentará forzar la contradicción. A diferencia de los demás plugins, C recibe como argumento uno de los otros plugins, y no un programa, y simplemente lo que hace es llamar a Parada(A, A), es decir, lo que C se plantea es si un plugin concreto se parará si analizara la seguridad de su propio binario A(A). Pero C es muy travieso, y si Parada(A, A) retorna FALSO, C retorna CIERTO, y si Parada(A, A) es CIERTO, C se mete en un bucle infinito y no para nunca.

Ahora nos preguntamos ¿cual sería el resultado de C aplicado sobre sí mismo C(C)? ¿Se parará? Supongamos que C(C) no se para nunca, en este caso Parada(C, C) retorna FALSO, y C debería retornar CIERTO, es decir, sí que se para. Pero si C(C) se para, tendremos que Parada(C, C) es CIERTO, pero en este caso C se metería en un bucle infinito y no debería parar. Esta contradicción de que C(C) se para sí y sólo si si no se para nos lleva a la conclusión de que nuestra hipótesis, la existencia de la función Para(A, P) genérica, es falsa.

Al final mi cliente le contrató el proyecto a un programador chino que le prometió que se lo hacía por 500 dólares.