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.

jueves, 12 de diciembre de 2013

¿Qué es esa cosa llamada Información?

La palabra Informática, esa disciplina que tanto nos gusta, proviene de la contracción de las palabras “Información” y “Automática”. Por tanto, se trata de un término que sugiere que a lo que nos dedicamos los informáticos es a automatizar el procesamiento de la información. Informática es un término que no me gusta excesivamente (¿acaso no es más correcto decir que nos dedicamos a procesar símbolos?), pero aun así, es mucho mejor que el término anglosajón “computer science”, o “ciencia de los ordenadores”. Como en su día dijo el maestro Dijkstra (http://es.wikipedia.org/wiki/Edsger_Dijkstra) , llamar “ciencia de los ordenadores” a la informática es como llamar “ciencia de los cuchillos” a la cirugía. Pero a todo esto, ¿sabemos qué es esa cosa llamada información? La verdad es que tampoco tenemos una idea muy clara al respecto. Según con qué disciplina tratemos, información se define de una manera u otra, como vamos a ver en esta entrada de blog.
La estadística, una de las disciplinas que primero abordó la cuestión, considera que la cantidad de información contenida en un mensaje es máxima si este es capaz de describir las principales características de una población. La información, por tanto, se estudia en relación a una población de individuos. La estadística lo que busca son los valores medios, la desviación sobre dichos valores, etc. que, a su entender, es lo que más información nos aporta. Así, la frase “En Córdoba hace mucho calor” es una frase que contiene gran cantidad de información, ya que es capaz de resumir en unas pocas palabras cual es el tiempo que generalmente hace en Córdoba.
Por otro lado, la teoría de la información de Shannon, considera justo lo contrario, que los valores medios no nos aportan ninguna información. Así al mensaje “En Agosto de 2013 hizo mucho calor en Córdoba” le asignaría un cantidad de información muy baja, ya que es lo normal, lo esperado, lo que tiene una gran probabilidad de que suceda. Sin embargo el mensaje “En Agosto de 2013 nevó en Córdoba” es un mensaje que contiene gran cantidad de información, ya que es un hecho altamente improbable, y por tanto, nos está aportando mucho. La teoría de la información de Shannon se desarrolló en el contexto de la transmisión de mensajes (por líneas de teléfono), y por tanto, trata de dar una respuesta a un problema de naturaleza muy diferente al que aborda la estadística. Sin embargo, son muchos los investigadores que se olvidan de este detalle, y tratan a la teoría de la información como la “definición canónica” de información, algo que está muy lejos de ser así.
Pero es que aun hay más definiciones. También tenemos a la Complejidad Kolmogoroviana, que se olvida por completo del contexto en el que se encuentra un mensaje y se limita a estudiarlo en términos de sí mismo para asignarle un valor de “información”. Así, a la complejidad Kolmogoroviana le da igual la población que estemos describiendo, o la probabilidad de que suceda cierto hecho. A la complejidad Kolmogoroviana lo que le interesa es saber es “la aletoriedad” del contenido de un mensaje, y define aletoriedad como la longitud mínima con la que puede ser descrito dicho mensaje sin ambigüedad. Por ejemplo, podríamos definir la cantidad de información contenida en un mensaje como la longitud de un programa de ordenador que pueda mostrarnos en pantalla el mensaje. Así, si lanzamos 1000 veces una moneda al aire, dicho programa lo único que podría hacer es escribir tal cual el resultado de los lanzamientos; se trata de un mensaje básicamente aleatorio, y por tanto, contiene gran cantidad de información. Pero si nuestro mensaje son 1.000 unos consecutivos, el programa que los imprime puede ser mucho más corto que el mensaje original, y por tanto, el mensaje contiene poca cantidad de información.
Y seguimos con más visiones de la información, porque también tenemos a la información cuántica, una descripción de la información desde el punto de vista de la mecánica cuántica. En este caso, nos dicen que la información no es un concepto abstracto que resida en nuestra mente, sino que la información es una magnitud física y real, como lo es la energía. Y por tanto, la información ni se crea ni se destruye, tan sólo se transforma. Cuando le das a borrar un documento en el procesador de textos, ¿piensas que realmente ha desaparecido, que lo has borrado? No, sólo se ha transformado, probablemente en un conjunto de celdas de memoria sin sentido. Pero lo más divertido es que dado que a partir de las celdas de memoria vacías no podemos recuperar el texto original, se ha producido una pérdida de información, y esto no es posible. ¿Qué sucede entonces? Pues que dicha información se transformado en calor que ha sido enviado al entorno.
En definitiva, muchas definiciones, algunas de ellas incompatibles, para tratar de entender qué es esto de la información. Y un concepto clave que hay que trabajar, porque al fin y al cabo, la vida, el universo y todo lo demás, se reducen a eso, a procesar información.

viernes, 1 de noviembre de 2013

Ordenación rápida quicksort

El algoritmo de ordenación rápida, o quicksort, fue desarrollado por Antony Hoare en 1960, mientras estudiaba en la Universidad de Moscú. Hoare tenía un gran interés en los sistemas automáticos de traducción, y uno de los principales problemas con los que se encontró fue el de cómo ordenar de manera eficiente las palabras a traducir, que podían llegar a ser muchas. De ahí su interés en los alogirtmos de ordenación.
Quicksort es un algoritmo recursivo que se basa en el paradigma divide y vencerás para ordenar los números. Quicksort se compone de los siguientes pasos:
  • Elegir un elemento del vector al azar, al que llamaremos pivote.
  • Reordenar el vector de tal manera que los elementos menores que el pivote se encuentren a su izquierda, y los mayores a su derecha. Nótese que en este momento el pivote se encontraría en su posición final.
  • Aplicar recursivamente los pasos 1 y 2 a las subvectores que se encuentran a ambos lados del pivote.
Como en todo algoritmo recursivo, tenemos que indicar una condición de salida. En nuestro caso, esta condición se daría cuando tenemos un vector con uno o ningún elemento, en cuyo caso no hay que hacer nada.
El algoritmo quicksort es el siguiente:
función quicksort(vector)

    l := longitud(vector)
    si l <= 1 entonces
        retorna vector
    fin si

    mayores := []
    menores := []
    ma := 1
    me := 1

    pivote := vector[aleatorio(l)]
    repetir desde i:=1 hasta l
        si vector[i] < pivote entonces
            menores[me] := vector[i]
            me := me+1
        si no
            mayores[ma] := vector[i]
            ma := ma+1
          fin si
    fin repetir

    mayores := quicksort(mayores)
    menores := quicksort(menores)
    vector := menores + pivote + mayores
    retorna vector

fin función
Lo primero que hacemos en el algoritmo es comprobar si el vector que hemos recibido tiene uno o ningún elemento, en cuyo caso no hay que hacer nada, ya que se trataría de un vector ordenado; simplemente retornamos el mismo vector que hemos recibido (esta es la condición de parada de la recursividad). A continuación definimos dos vectores auxiliares, uno de ellos para almacenar los valores menores que el pivote, y otro para almacenar los valores mayores, y seleccionamos un elemento al azar del vector, que será nuestro pivote (suponemos para ello que disponemos de una función llamada aleatorio(), que recibe un número n como argumento, y nos devuelve un número aleatorio entre 1 y n). Mediante un bucle de tipo repetir vamos colocando en el correspondiente vector auxiliar aquellos valores que sean mayores o menores que el pivote. Una vez tengamos los vectores completos, lo que hay que hacer es aplicar recursivamente el mismo algoritmo a cada uno de estos vectores auxiliares. Y cuando cuando las llamadas recursivas al algoritmo hayan terminado su trabajo, tendremos otra vez que volver a concatenar los subvectores, que ya estarían ordenados, en un único vector (nuestro ordenador imaginario que ejecuta este pseudocódigo es tan chulo que el operador + aplicado a vectores lo que hace es concatenarlos uno detrás de otro).
La siguiente figura muestra un ejemplo de cómo trabaja el algoritmo. En gris están los pivotes que se seleccionan en cada llamada recursiva al algoritmo.

jueves, 24 de octubre de 2013

El algoritmo de la burbuja

El algoritmo de la burbuja es uno de los métodos de ordenación más conocidos. Sin embargo, no se trata de un algoritmo eficiente desde el punto de vista computacional, ni tampoco se trata de un algoritmo que sea fácil de entender, y por tanto, que pueda utilizarse con fines pedagógicos. Se trata, simplemente, de un algoritmo malo con un nombre divertido. El mundo es así. Veamos el algoritmo:
función burbuja(v, n)
    repetir desde i:=n hasta 1
        repetir desde j:=1 hasta i-1    
            si v[j+1] < v[j] entonces
                aux    := v[j]
                v[j]   := v[j+1]
                v[j+1] := aux
            fin si
        fin repetir
    fin repetir
fin función
El algoritmo se basa en dos bucles que están anidados uno dentro de otro. Al final de cada iteración del primer bucle nos aseguramos que el i-ésimo elemento es el mayor de los i-1 primeros elementos del vector, y el segundo bucle es el encargado de que esto sea así, mediante el intercambio de los números que sean necesarios. Imaginemos, por ejemplo, que tenemos que ordenar la siguiente secuencia de números:
    [12, 23, 14, 19, 3]
Cuando i vale 5, el bucle interior va desde 1 hasta 4, comparando cada elemento con su siguiente, y en el caso de que el siguiente sea menor, intercambiándolos. Primero comparamos el 12 con el 23, y como están ordenados no sucede intercambio; después comparamos el 23 con el 14, que al ser menor, hay que intercambiarlos; a continuación comparamos el 23 (que había sido intercambiado) con el 19, y también hay que intercambiarlos. Y finalmente comparamos nuevamente el 23 con el 3, y lo volvemos a intercambiar. Tal y como muestra la siguiente figura:


Como podemos comprobar, el 23 ya está situado en su posición (para i=5 nos aseguramos que la posición 5 contiene el valor correcto). En la siguiente iteración situaríamos el 19 en su posición correcta, y así sucesivamente hasta ordenar completamente el vector. Se llama algoritmo de la burbuja por la forma en que tienen los números mayores de subir hacia arriba en el vector, como si fueran burbujas flotando en un líquido.

lunes, 21 de octubre de 2013

Las ocho reinas y la vuelta atrás

En una entrada anterior vimos cómo solucionar el problema de las ocho reinas utilizando la fuerza bruta. En esta ocasión vamos a ver cómo se solucionaría el mismo problema utilizando una técnica diferente: la vuelta atrás.
El método de resolución de problemas de vuelta atrás (del inglés backtracking) se basa en la idea de que no siempre es necesario terminar de construir completamente una solución candidata para determinar que ésta no es válida. Para ciertos problemas es posible que con soluciones parcialmente construidas ya sea posible determinar que estas son incorrectas. En el caso concreto del problema de las ocho reinas, si por ejemplo colocamos la primera reina en la primera columna y primera fila, y la segunda reina en la segunda columna y la segunda fila, no es necesario colocar ninguna de las otras 6 reinas restantes (en cualquiera de sus combinaciones posibles), porque ya sabemos que esta solución no es válida, porque las dos reinas ya colocadas se atacan mutuamente. Si en este momento abortamos la búsqueda en esta línea, nos ahorraríamos de examinar 6! ó 720 soluciones candidatas. Una vez que hemos encontrado que una combinación es incorrecta, y hemos determinado que vamos a abortarla, lo que hacemos es volver un paso hacia atrás, hasta la última reina que colocamos, y continuamos la búsqueda por donde la dejamos.
A continuación vamos a estudiar el algoritmo que resuelve el problema de las ocho reinas utilizando la técnica de la vuelta atrás. Primero, y al igual que en el caso del algoritmo de la fuerza bruta, necesitamos una función que dada una posición nos indique si esta es válida o no.
función posición_válida(x, k)
    para i desde 1 hasta k-1
        si x[i]=x[k] ó |i-k|=|x[i]-x[k]| entonces
            retorna falso
        fin si
    fin para
    retorna cierto
fin función
La primera diferencia que observamos con respecto a la función de validación del apartado anterior es que ésta recibe dos argumentos, a saber, el tablero (x) y el número de reinas colocadas en el mismo (k). Esto es así porque las posiciones que les pasamos a la función son posiciones parcialmente construidas, es decir, que no todas las piezas están colocadas en el tablero, y por tanto, tenemos que decirle cuantas piezas hay. Otra gran diferencia es que la función sólo cuenta con un único bucle, en lugar de los dos bucles anidados del caso anterior. Esto es así porque no es necesario comprobar si cada reina ataca a todas las demás, ya que el algoritmo va construyendo progresivamente la solución, y por tanto, cuando es invocada la función con, por ejemplo, 4 reinas, sabemos que las tres primeras no se atacan entre sí: la función ya fue invocada anteriormente para el caso k:=3, y si alguna de las tres reinas se hubiese atacado, no habríamos llegado a este punto. Por tanto, nos bastaría con comprobar que esta nueva y última reina no ataca a las demás. Finalmente, y para no complicarnos la vida con las temidas permutaciones, nuestro algoritmo de búsqueda sólo nos garantizará que las reinas no comparten columna, y por tanto, la función de validación ha de comprobar explícitamente que las reinas no comparten filas (x[i]=x[k]).
Una vez que tenemos la función posición_válida(), podemos abordar el algoritmo:
x   := [0, 0, 0, 0, 0, 0, 0, 0]
k   := 1
fin := falso
mientras (fin = falso) hacer
    mientras no posición_válida(k, x) hacer
        x[k] := x[k] + 1
        si x[k] > 8 entonces
           k := k – 1
           si k = 0 entonces
               fin := cierto
               salir
           si no
               x[k] := x[k] + 1
           fin si
    fin mientras
    si k = 8 entonces
        escribir(x)
    si no
        k := k + 1
        x[k] := 1
    fin si
fin mientras
Aunque el algoritmo parezca muy complejo, la idea subyacente al mismo es muy sencilla. Básicamente lo que tenemos que hacer para calcular todas las combinaciones posibles de reinas, con una reina por columna, es contar desde la posición [1,1,1,1,1,1,1,1] hasta la posición [8,8,8,8,8,8,8,8], de la misma forma que hacemos cuando contamos números naturales (la única diferencia es que en lugar de contar desde 0 hasta 9 como hacemos habitualmente, contamos desde 1 hasta 8).
Sin embargo, hay que tener en cuenta que con el algoritmo de vuelta atrás, la cuenta se ve interrumpida cada vez que encontramos una posición que no es válida con las reinas que llevamos hasta el momento colocadas. Por ejemplo, de la posición [1,1,1,1,1,1,1,1] nos saltaríamos a la posición [1,2,1,1,1,1,1,1] sin necesidad de pasar por todas las posiciones intermedias [1,1,X,X,X,X,X,X] ya que sabemos que son todas inválidas independientemente de los valores que adopten las X, porque las dos primeras reinas se atacan (comparten la primera fila).
Es sorprendente que algo tan sencillo como contar requiera de un algoritmo tan complejo. Pero esto es una situación muy habitual en informática.