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.

jueves, 17 de octubre de 2013

Las ocho reinas y la fuerza bruta

El problema de las ocho reinas es muy fácil de describir, sólo hay que colocar ocho reinas del juego del ajedrez en un tablero estándar de 8x8 de tal manera que no se ataquen entre ellas. Recordemos que las reinas pueden desplazarse cualquier número de casillas en horizontal, vertical, o diagonal. Por tanto, para que que el problema esté resuelto, las reinas no pueden compartir ni filas, ni columnas, ni diagonales. A modo de ejemplo, y para asegurarnos de que todos estamos hablando de lo mismo, la siguiente figura muestra la solución al problema para un caso más simple, el de 4 reinas en un minitablero de 4x4 casillas.
Una técnica de resolución de problemas para la que los ordenadores están especialmente bien dotados es la conocida como fuerza bruta. Básicamente la idea cosiste en dado un problema, intentar de manera sistemática todas las soluciones candidatas hasta dar con la solución buscada. El método de la fuerza bruta aplicado al problema de las reinas consistiría en calcular todas las formas posibles de colocar las ocho piezas en el tablero, y para cada una de ellas comprobar si se trata de una posición legal, es decir, no hemos colocado más de una reina en la misma casilla, y que las reinas no se atacan entre sí (no hay dos reinas situadas en la misma fila, columna, o diagonal). De esta manera, la primera pieza la podríamos colocar en cualquiera de las 64 casillas; la segunda, también se podría colocar en cualquiera de las 64 casillas (y después ya comprobaremos si las hemos colocado en la misma), con lo que tendríamos 64x64 posibilidades; con la tercera pieza tendríamos 64x64x64 posibilidades; y cuando coloquemos la última, tendríamos 64x64x64x64x64x64x64x64 posibilidades, que nos da el astronómico número de 281.474.976.710.656 posiciones a examinar, algo que está fuera del alcance de la mayoría de los ordenadores de hoy en día.
Llegados a este punto, lo que tenemos que hacer es aplicar algunas técnicas heurísticas, para ver hasta dónde podemos reducir el número de soluciones candidatas a calcular. La primera mejora, y la más evidente, es evitar colocar dos piezas en la misma casilla. La primera reina la podemos poner en cualquiera de las 64 casillas, la segunda en cualquiera de las 63 restantes, y así sucesivamente, por lo que tendríamos un total de 64x63x62x61x60x59x58x57 posiciones, que nos da el número 178.462.987.637.760.
A continuación vamos a añadir la restricción de que sólo puede haber una reina en cada columna, ya que de lo contrario se atacarían. En este caso, la primera reina podría ir a cualquiera de las 8 casillas de la primera columna, la segunda reina a cualquiera de las 8 casillas de la segunda, y así sucesivamente. Para este caso lo que tenemos son 8x8x8x8x8x8x8x8 combinaciones, que hace un total de 16.777.216 posibilidades, un número bastante más asequible para un ordenador.
La siguiente mejora que podemos añadir es la de no permitir que dos reinas estén en la misma fila. En este caso, la primera reina puede ocupar cualquiera de las 8 casillas de la primera columna como estudiamos en el caso anterior, pero ahora la segunda reina sólo puede ocupar una de las 7 casillas libres, es decir, puede estar en cualquier lugar de la segunda columna excepto en la fila que ya está ocupada por la primera reina. De igual manera, a la tercera reina le quedarían 6 casillas libres para ocupar, y así sucesivamente. Es decir, tendríamos que evaluar 8x7x6x5x4x3x2x1 u 8! combinaciones, lo que nos da 40.320 posibles posiciones.
Veamos, por tanto, el algoritmo que soluciona el problema de las ocho reinas mediante la fuerza bruta, al que le añadiremos las mejoras de evitar colocar dos reinas en la misma columna y en la misma fila.
En primer lugar vamos a implementar una función que dada una posición determinada (una configuración concreta de reinas) determine si es una solución válida o no al problema. Dado que nuestro algoritmo de búsqueda se encarga de eliminar todas aquellas posiciones en las que dos o más reinas ocupan la misma casilla, la misma columna, y la misma fila, a la función de validación sólo le quedaría por comprobar que no ocupen la misma diagonal.
Para poder trabajar, nuestra función de validación necesita conocer en qué posición se encuentra cada reina, es decir, necesitamos algún mecanismo que nos permita codificar los tableros. Para ello enumeraremos por orden a las reinas, de tal manera que la reina número 1 es la que ocupa la primera columna, la reina 2 la segunda, etc. Y a continuación creamos un array con las filas que ocupan cada una de las reinas dentro del tablero. De esta manera, si la primera reina está en la fila 4, tendremos que el array en su posición 1 contendrá el valor 4, es decir, x[1]:=4. Así por ejemplo el siguiente array:
[5, 7, 8, 4, 2, 7, 3, 1]
se correspondería con el siguiente tablero:
Para que dos reinas, i y j, ocupen la misma diagonal se debe cumplir que la distancia (número de casillas) que hay entre sus respectivas columnas (valores de i y de j) sea igual a la distancia que hay entre sus respectivas filas (valores x[i] y x[j]). Y dado que la distancia entre dos números cualesquiera es el valor absoluto de la diferencia entre ambos, tenemos que para que dos reinas ocupen la misma diagonal se debe cumplir que |i-j| = |x[i]-x[j]|.
Por tanto, nuestra función para el cálculo de posiciones válidas sería:
función posición_válida(x)
    para i desde 1 hasta 7
        para j desde i+1 hasta 8
            si |i-j| = |x[i]-x[j]| entonces
                retorna falso
            fin si
        fin para
    fin para
    retorna cierto
fin función
Finalmente, lo que necesitamos es otra función que genere los distintos tableros a examinar. Dicho de otra manera, que genere todas las combinaciones posibles de reinas. Dados los números del 1 al 8, queremos calcular todas las formas posibles que existen de ordenarlos, sin que se repitan. A esto en matemáticas se le conoce con el nombre de permutaciones. Supondremos la existencia de una función llamada permutaciones() que nos devuelve un array con todas las permutaciones posibles.
Una vez tenemos disponible la función que comprueba la validez de un tablero, y una función para la generación de permutaciones, podemos implementar el algoritmo que soluciona el problema de las ocho reinas:
p := permutaciones(8)
para i desde 1 hasta longitud(p) hacer
    k := perm[i]
    si posición_valida(k) entonces
        escribir(k)
    fin si
fin para
Se trata de un algoritmo muy sencillito, que simplemente genera la totalidad de las permultaciones, y después va comprobando una a una si se trata de una solución válida.

lunes, 14 de octubre de 2013

Búsqueda Binaria

¿Quién no ha jugado alguna vez al juego de adivinar un número? Se trata de un juego muy sencillo: el primer jugador piensa un número al azar, por ejemplo, desde 1 hasta 100, y el segundo jugador tiene que adivinarlo. Para ello va diciendo en voz alta distintos números, y el primer jugador le dice si el número que ha pensado es mayor, o menor. La pregunta es ¿cual es la mejor estrategia que podemos utilizar para adivinar el número secreto en el menor número de intentos posibles? Una posible estrategia, que funciona muy bien, sería decir como número el punto intermedio del intervalo que nos queda por buscar. Si hablamos de números desde 1 hasta 100, nuestro primer intento debería ser el 50; supongamos que el número buscado es menor, en este caso, y dado que el intervalo de búsqueda se ha reducido desde 1 hasta 50, nuestro segundo intento debería ser el 25, y así sucesivamente.
Imaginemos ahora que el departamente de recursos humanos de una determinada empresa tiene almacenadas en un ordenador las fichas de todos sus empleados, ordenadas alfabéticamente, y que desde la dirección necesitan una ficha concreta. En este caso, ¿cual es el mejor algoritmo para buscar la ficha deseada? A poco que pensemos un poco nos daremos cuenta de que se trata exactamente del mismo problema que en el caso anterior, y por tanto, ya tendríamos una estrategia de búsqueda válida. Supongamos que lo que buscamos es la ficha del señor Fernández, y que tenemos en total 1.000 fichas; por tanto seleccionamos la ficha 500 (el punto intermedio) y vemos que corresponde a la señora Jiménez, que según el orden alfabético es mayor; el siguiente paso sería continuar con la búsqueda utilizando las fichas desde la 1 hasta la 500. El algoritmo que implementa esta estrategia se llama búsqueda binaria.
Veamos nuestro algoritmo de búsqueda binaria:
función búsqueda(A, x)
    p := 1
    r := longitud(A)
    mientras p <= r hacer
        q := int((p+r)/2)
        si A[q] = x entonces
            retorna q
        si no
            si A[q]> x entonces
                r := q-1
            si no
                p := q+1
            fin si
        fin si
    fin para
    retorna NO_ENCONTRADO
fin función
La función de búsqueda recibe como primer parámetro un array de números enteros que han de estar necesariamente ordenados, y como segundo parámetro el valor que queremos encontrar en el array. Como salida nos devuelve la posición (o índice) en la que dicho valor se encuentra dentro el array, o la constante NO_ENCONTRADO si es que el elemento no se ha encontrado. Lo primero que hacemos es establecer los límites del intervalo en los que empieza nuestra búsqueda, siendo p la variable que contiene el valor menor (1 al empezar), y r la variable que contiene el valor mayor (que al empezar es la longitud del array, que viene determinada por la fución longitud()). La función siguiría iterando mientras el intervalo de búsqueda tenga una longitud mayor o igual que 1 (p<=r).
Para cada iteración del bucle lo que hacemos es calcular la posición intermedia del intervalo y comparamos su valor allí almacenado con el valor buscado. Si ambos valores son iguales, hemos encontrado lo que buscábamos y por tanto retornamos el índice. Si el valor es menor modificamos el extremo inferior del intervalo, y si es mayor, el extremo superior.

jueves, 10 de octubre de 2013

Los Conejos de Fibonacci

Nuestro siguente algoritmo trata sobre dinámica de poblaciones, pero no se asuste el lector, porque se trata de un algoritmo muy sencillito. La dinámica de poblaciones se encarga del análisis de las poblaciones biológicas, y entre otras cosas, estudia como varía el tamaño de una población con el tiempo. Uno de los primeros modelos matemáticos de cómo crece una población fue propuesto por Leonardo Pisano (también conocido como Fibonacci) en el año 1202, en su libro Liber Abaci.
Fibonacci propuso el siguiente modelo para la cría de conejos:

  • Empezamos con una pareja de conejos recién nacidos,
  • los conejos nacen de dos en dos, y de sexo opuesto,
  • los conejos alcanzan la madurez sexual al mes de vida, y 
  • el tiempo de gestación es de 1 mes.

De acuerto con este modelo en el primer mes tendremos una única pareja de conejos, la pareja de conejos con la que partimos, luego:

    F[1] = 1

En el segundo mes, tendremos nuevamente a nuestra pareja de conejos. Pero en este caso ya están maduros sexualmente, y por tanto, pueden reproducirse:

    F[2] = 1

En el tecer mes tendremos a nuestra pareja original, junto con una nueva pareja de conejos recién nacidos:

    F[3] = 1+1 = 2

En el cuarto mes nuestra pareja original vuelve a tener otra descendencia, y la primera descendencia ya estarán maduros sexualmente. Es decir:

    F[4] = 2+1 = 3

En el quinto mes, las cosas se empiezan a complicar un poco. Tenemos a la pareja original que vuelven a tener descendencia, a los primeros conejos que acaban de tener su primera descendencia, y a los segundos conejos que ya están maduros sexualmente. Simplificando:

    F[5] = 3+2 = 5

Los lectores más atentos, y aquellos que ya conociese la sucesión de Fibonacci, habrán notado que F[5] = F[4] + F[3], al igual que F[4] = F[3] + F[2], y en general, podemos decir que en el mes N tenemos:

    F[N] = F[N-1]+F[N-2]

Lo cual se puede razonar diciendo que en un mes dado, habrá tantos conejos como en el mes anterior (F[N-1]) a los que habrá que sumarle los nacimientos de la generación de hace dos meses (F[N-2]). El algoritmo que calcula la sucesión de Fibonacci es muy sencillo:

leer(N)
f1 := 1
escribir(f1)
f2 := 1
escribir(f2)
para i desde 3 hasta N hacer
    f := f1 + f2
    escribir(f)
    f2 := f1
    f1 := f
fin para

El algoritmo empieza leyendo el número de elementos de la sucesión que queremos calcular. A continuación incializa y muestra los dos primeros términos de la sucesión, que como hemos dicho, ambos son la unidad. Y finalmente, entramos en un bucle de tipo para que va calculando sistemáticamente cada nuevo valor de la sucesión, mediante la suma de los dos valores anteriores (almacenados en las variables f1 y f2), y actualizando los valores de f1 y f2 con los nuevos términos de la serie recién calculados.
La serie de Fibonacci ha sido ampliamente estudiada tanto por matemáticos como por informáticos, y son muchas las propiedades interesantes que se le han encontrado, como su relación con el número áureo, o sus aplicaciones prácticas, que van desde la generación de números pseudoaleatorios, hasta los algoritmos de ordenación. También se han encontrado numerosos ejemplos de la serie de Fibonacci en la naturaleza, como en la ramificación de los árboles, o la distribución de las hojas de una alcachofa. El interés por la serie de Fibonacci ha llegado tan lejos como los mercados financieros, donde son muchos los traders que creen que los precios de los activos financieros evolucionan según la serie. Pero lo más curioso de todo es que seguramente Fibonacci nunca llegó a imaginar que uno de los ejercicios propuestos en su libro, algo a lo que él no le dio la mayor importancia, iba a despertar tanto interés.

viernes, 4 de octubre de 2013

El Algoritmo de Euclides

En la entrada enterior vimos un sencillo algoritmo para el cálculo del máximo común divisor de dos números enteros. En esta ocasión vamos a ver el Algoritmo de Euclides, que es una manera fácil, elegante, y rápida de calcular el máximo común divisor. El algoritmo de Euclides se basa en la siguiente propiedad:

Si a y b son dos números enteros cualesquiera, entonces MCD(a, b) = MCD(a-b, b).

Podríamos hacer unos cuantos ejemplos a mano (¡ánimo, hágalo!) para convencernos a nosotros mismos de que esta propiedad es cierta, y aquellos lectores que sean más hábiles con las matemáticas, podrían incluso intentar dar una demostración formal. Pero en realidad no hace falta complicarse la vida tanto. Sólo tenemos que pensar un poco qué es lo que realmente significa esta propiedad para darnos cuenta de que la idea es trivial.
Imaginemos que tenemos dos barras de acero de longitudes a y b respectivamente, y que queremos medirlas utilizando para ello una pequeña regla de madera. Si la regla de madera nos da un número entero de medidas en una de las barras es porque la regla es un divisor de dicha barra. Si después de medir nos sobra un poquito de barra, es porque la regla no es un divisor. De entre todas las reglas que miden a ambas barras a y b nos quedamos con la que tenga una longitud mayor, que será precisamente el máximo común divisor (véase la siguiente figura).

Ahora bien, si encontramos una regla que divide a la barra b, para ver si también divide a la barra a bastaría con comprobar que divide a aquella parte de la barra a que sobresale de la barra b (es decir b-a), ya que la otra parte ya ha sido medida. Si ahora cortamos lo que sobresale de la barra a, podríamos repetir de nuevo el proceso pero utizando la barra cortada b-a y la barra b. Se trataría de resolver el mismo problema pero invertidos los papeles de las barras.
Basándonos en esta idea, podemos escribir el siguiente Algoritmo de Euclides: la idea consiste en ir cortando alternativamente de la barra más larga la parte que sobresale de la barra más pequeña, hasta que ambas barras tengan exactamente la misma logitud, que será el máximo común divisor. El algoritmo puede ser mejorado todavía un poco más, utilizando para ello la función módulo que hemos en una entrada anterior, pero esta mejora se la dejo propuesta al lector como ejercicio.

A diferencia del algoritmo anterior donde conocíamos a priori el número de iteraciones que teníamos que realizar sobre el bucle (desde 1 hasta min), en este caso no conocemos cuantas iteraciones serán necesarias antes de dar con el máximo común divisor, ya que depende de los cortes que realicemos, por eso utilizamos un bucle de tipo mientras. La condición es que mientras las barras tengan longitudes diferentes tenemos que seguir cortando, y en el momento que sean iguales paramos (nos salimos del bucle), porque ese es el máximo común divisor.

leer(a)
leer(b)
mientras a != b hacer
    si a < b entonces
        a := a - b
    sino
        b := b - a
    finsi
fin mientras
escribir(a)

La genalidad del algoritmo de Euclides quizás no sea tan geneial si la vemos desde un punto de vista histórico. Me explico. No es que quiera restarle mérito al que es, probablemente, el primer algoritmo de la historia. Pero en la época de Euclides los matemáticos dedicaban gran parte de su tiempo a estudiar las razones entre las cosas, sobre todo entre figuras geométricas (recordemos que la razón entre dos cosas es el número de veces que contiene la una a la otra). Así, el máximo común divisor era entendido en términos geométricos, como la razón máxima común a dos segmentos dados. En este contexto es más natural que surga este algoritmo. Hoy en día, las razones (en ambos sentidos de la palabra) ya no son tan importantes, somos más dados a la solución algebráica de los problemas, y en este contexto, la idea subyacente al alogritmo de Euclides nos resulta más complicada de entender.

viernes, 27 de septiembre de 2013

Máximo Común Divisor

En esta entrada vamos a ver un sencillo algoritmo para el cálculo del máximo común divisor de dos números dados. Recordemos que el máximo común divisor de dos números enteros positivos a y b, escrito como MCD(a, b), es el mayor de los divisores comunes de a y de b, es decir, el mayor de aquellos números que dividen a la vez a ambos. Por ejemplo MCD(6, 4) = 2, MCD(9, 6) = 3, y MCD(11, 9) = 1. El cálculo del máximo común divisor resulta muy útil a la hora de simplificar facciones, por ejemplo la fracción 60/18 podríamos simplificarla como 60/18 = (6*10) / (6*3) = 10 / 3.
En el siguiente algoritmo podemos encontrar un método para el cálculo del máximo común divisor. El algoritmo recibe como parámetros de entrada dos números, a y b, y como resultado nos muestra en pantalla el MCD(a, b). Para ello, el algoritmo se basa en un procedimiento muy simple: primero calcula cual es el menor de los números a y b, a continuación recorre todos los números que van desde 1 hasta el menor de a y b, y para cada uno de ellos comprueba si divide a la vez a ambos, utilizando la ya conocida función módulo(), que recordemos nos devuelve el resto de la división entera entre dos números x e y. Al final del bucle repetir, tendremos en la variable mcd el mayor de los números que han dividido a la vez a a y b, es decir, su máximo común divisor.

leer(a)
leer(b)
min := mínimo(a, b);
repetir desde x := 1 hasta x := min
    si (módulo(a, x) = 0) y 
           (módulo(b, x) = 0) entonces
        mcd := x
    fin si
fin repetir
escribir(mcd)

Existen muchas formas de mejorar el algoritmo anterior. Por ejemplo, no haría falta comprobar cuales son los divisores de a y b desde 1 hasta mínimo de a y b, bastaría con comprobar desde 1 hasta la raiz cuadrada del mínimo (¿podría explicar el lector por qué?). Otra manera más refinada de calcular el MCD sería mediante la factorización de los números a y b, aunque este procedimiento no es necesariamente más eficiente.
En la siguiente entrada de este blog veremos una forma muy sencilla, y muy eficiente, de calcular el máximo común divisor de dos números, el conocido como Algoritmo de Euclides.

viernes, 13 de septiembre de 2013

Números Primos

En una entrada anterior de este blog vimos un algoritmo que calculaba números factoriales. En esta entrada vamos a ver otro ejemplo de algoritmo, que determina si un número es primo o no. Este segundo algoritmo nos permitirá introducir nuevos conceptos sobre programación.
Recordemos que un número primo es aquel que sólo es divisible por sí mismo y por la unidad; y recordemos también que decimos que un numero es divisible por otro cuando el resto de la división entera es 0. Veamos algunos ejemplos. El 4 es divisible por 2 porque al hacer la división de 4 entre 2 nos da como resultado 2 y de resto 0. De igual manera decimos que 5 no es divisible por 2, ya que la división nos da 2 junto con un resto de 1. Por otro lado, el número 4, al ser divisible por 2, no es un número primo. En cambio, el número 5, que no es divisible ni por 2, ni por 3, ni por 4, es un número primo (sólo es divisible por sí mismo y la unidad).
A modo de ejemplo, los diez primeros números primos serían (no, el número 1 no es un número primo, por definición):

2, 3, 5, 7, 11, 13, 17, 19, 23, y 29

Los números primos juegan un papel muy importante, no sólo en matemáticas, sino también en informática. En matemáticas, existen libros enteros dedicados a los números primos: historia, propiedades, aplicaciones, curiosidades, etc. Y en informática, los números primos son utilizados por los algoritmos de cifrado basados en claves públicas, que son básicos en áreas como la telefonía móvil o las transacciones bancarias.
Ahora, básicamente, lo que queremos es escribir un sencillo algoritmo que, dado un número, nos diga si es primo o no es primo. Antes de seguir leyendo, es conveniente que el lector le eche un vistazo rápido al siguiente algoritmo, a ver qué puede entender. Si no lo entiende en su totalidad, no se preocupe, que para eso estamos aquí, para explicar las cosas en detalle. Este nuevo algoritmo es muy parecido al algoritmo para el cálculo del factorial de un número que ya hemos visto. Recordemos que para calcular el factorial de un número n lo que hacíamos es utilizar un bucle que recorriese todos los valores desde 1 hasta n multiplicándolos. En este nuevo caso lo que necesitamos es un bucle que recorra todos los valores desde 2 hasta n-1, y para cada uno de ellos compruebe si dividen a n.

leer(n)
primo := CIERTO

repetir desde i:=2 hasta i:=n-1
    si modulo(n, i) = 0 entonces
        primo := FALSO
    fin si
fin repetir

si primo = CIERTO entonces
    escribir(“¡Es primo!”)
fin si

si primo = FALSO entonces
    escribir(“No es primo”)
fin si

Para saber si un número divide a n tendríamos que ver el resto de la división de n entre ese número. Sin embargo, esta división, que a simple vista no tiene mayor complicación, puede llegar a convertirse en un problema. Si le decimos a un ordenador que calcule 5/2 nos va a dar como resultado 2.5, que no es lo que queremos, ya que lo que queremos saber es el resto de la división sin recurrir a decimales. La mayoría de los ordenadores proporcionan algún mecanismo, o bien para conocer el cociente de las divisiones enteras, o bien para conocer directamente el resto de dichas divisiones. En nuestro caso, y por no complicar innecesariamente las cosas, supondremos que nuestro ordenador tiene un mecanismo llamado módulo(x, y) que nos devuelve el resto de la división enterea de x por y. Así por ejemplo:

módulo(4, 2) = 0
módulo(5, 2) = 1

En realidad el algoritmo descrito es muy simple y puede ser mejorado enormemente, vamos a ver cómo.
La primera mejora es bastante obvia, una vez que hemos encontrado un número que divide a n ya tenemos la seguridad de que n no es primo, y por tanto, no tiene sentido que sigamos calculando si es divisible por otros números. En este caso, simplemente lo que tendríamos que hacer es terminar el bucle tan pronto encontremos el primer divisor de n, y así no le hacemos perder el tiempo a nuestro usuario. La segunda mejora, quizás no tan obvia, consiste en lugar de repetir el bucle desde 2 hasta n-1, es mejor, y suficiente, con hacerlo desde 2 hasta la raíz cuadrada de n. Dejo al lector como ejercicio que explique por qué es esto así.

leer(n)
primo := CIERTO

repetir desde i:=2 hasta i:= raiz(n)
    si módulo(n, i) = 0 entonces
        primo := FALSO
        salir
    fin si
fin repetir

si primo = CIERTO entonces
    escribir(“¡Es primo!”)
si no
    escribir(“No es primo”)
fin si

A aquellos lectores con un poco más de experiencia, les propongo como ejercicio, que extiendan el algoritmo para que en lugar de decirnos si n es un número primo, lo que haga es mostrarnos todos los números primos existentes menores que n. Lo que tendría que hacer el lector es utilizar dos bucles anidados, es decir, uno dentro de otro: un primer bucle que recorra todos los números desde 1 hasta n-1, y un segundo bucle que compruebe si dichos números son, o no son, primos.

martes, 3 de septiembre de 2013

Números Factoriales

A veces, cuando voy al cine con mi mujer y mis dos hijos, tenemos ciertas dificultades para decidir cual es la mejor manera de sentarnos. Podríamos simplemente sentar a los niños en las butacas centrales, y nosotros dos en las laterales, pero si hacemos esto, seguramente acaben peleándose en mitad de la película. Quizás lo mejor sea sentarlos lo más alejados posible, cada uno en una butaca lateral, y mi mujer y yo en las centrales, pero claro, existe el riesgo de que la pequeña acabe molestando a otros espectadores. O quizás podríamos optar por sentar al mayor en un extremo, a su lado mi mujer, después la pequeña, y finalmente yo. Pero no, esto tampoco vale, el mayor acabaría protestando porque la pequeña está entre papá y mamá, y él no. En fin, un problema, que al día de hoy, sigue pendiente de solución.
Al hilo de esto me gustaría plantear al lector otro problema, mucho más fácil de resolver, que consiste en contar de cuántas maneras posibles se pueden sentar cuatro personas en cuatro butacas de cine (lo que en matemáticas se conoce como el nombre de permutaciones). Centrémonos primero en la primera butaca. ¿Quiénes nos podríamos sentar en ella? Pues cualquiera de nosotros, es decir, cuatro. Supongamos ahora que alguien (da igual quién porque ya hemos tenido en cuenta que se puede sentar cualquiera de nosotros), ya se ha sentado en la butaca uno. ¿Cuantos de nosotros se pueden sentar en la butaca dos? Pues cualquiera de los tres que quedamos. Igualmente, cuando alguien se sienta en la segunda butaca, en la tercera quedan dos para sentarse. Y finalmente, cuando alguien se sienta en la tercera butaca, sólo queda uno, que ha de sentarse necesariamente en la cuarta butaca. En resumen, nos podemos sentar de 4*3*2*1=24 maneras diferentes. O dicho de otra forma, nos podemos sentar de 4! formas distintas. Lo que me da pie a introducir el concepto de factorial de un número, que es a lo que vamos.
El factorial de un número entero positivo n, escrito como n!, es el producto de todos los números enteros positivos menores o iguales que n. Por ejemplo:

5!=1*2*3*4*5=120

El concepto de factorial es muy útil en matemáticas, entre otras cosas, como hemos visto, para el cálculo de permutaciones. También son muy útiles para pasar el rato en el cine mientras empieza la película. Pero en realidad lo que ahora nos interesa es que los factoriales nos van a permitir introducir nuestro primer algoritmo.

leer(n)
x := 1
repetir desde i:=1 hasta i:=n
    x := x*i
fin repetir
escribir(x)

Para finalizar, a aquellos lectores que se animen a escribir este algoritmo en un ordenador real, les recomiendo que tengan un poco de cuidado con el valor que escogen para n. Hay que tener en cuenta que el cálculo de factoriales pueden dar como resultado números muy grandes, incluso para valores de n pequeños. Por ejemplo, el factorial de 10 es 3.628.880, y el factorial de 20 nos da ya el increíble valor de 2.432.902.008.176.640.000. Aquellos lectores que no les apetezca programar un algoritmo tan simple, también pueden divertirse hallando factoriales con una calculadora. La mayoría de las calculadoras de sobremesa son capaces de llegar hasta 69!. Esto es así porque las calculadoras nos muestran el resultado utilizando notación científica con dos dígitos para el exponente, y 70! requeriría ya de un exponente de tres dígitos.

sábado, 24 de agosto de 2013

¿Qué es un algoritmo?

La Real Academia Española define la palabra algoritmo como conjunto ordenado y finito de operaciones que permite hallar la solución de un problema. Aunque quizás no seamos conscientes de ello, es muy normal que nos ayudemos de algoritmos en nuestra vida cotidiana, y no sólo cuando utilizamos ordenadores o realizamos cálculos matemáticos. Por ejemplo, cuando compramos una estantería de bajo coste, de esas de móntela usted mismo, junto con las tablas de madera encontramos un folleto con instrucciones, o mejor dicho con un algoritmo, que nos indica cómo montarla; cuando nos subimos en nuestro coche seguimos un algoritmo preciso que nos permite conducir (introducir la llave, girarla a la posición de contacto, volverla a girar hasta la posición de arranque, soltar la llave cuando el motor arranque, pisar el embrague, introducir la marcha primera, etc); o cuando invitamos a unos amigos a cenar a casa y queremos sorprenderlos con un menú especial, consultamos nuestro libro de recetas de cocina, que en definitiva no es otra cosa que un libro lleno de algoritmos culinarios.
Veamos uno de estos ejemplos con más detalle. Imaginemos que queremos hacer una tortilla de patatas pero, como nos ha pasado a todos en algún momento de nuestra vida, no sabemos cómo se hace. Así que cogemos nuestro libro de recetas de cocina para hijos recién emancipados, y buscamos la receta correspondiente a la tortilla. Seguramente el libro encontraremos algo parecido a:

Trocear las patatas en taquitos de medio centímetro cuadrado, y freirlas en una sartén con aceite abundante y no muy caliente. Al poco rato, añadir la cebolla y dejar que se fría junto con las patatas. En un cuenco batimos los huevos, le echamos sal, y añadimos las patatas y cebolla ya fritas, mezclándolo todo bien. Dejamos un poco de aceite en la sartén y echamos la mezcla. Esperamos a que se cuaje un poco, le damos la vuelta, y la dejamos a fuego lento hasta que termine de cuajar.

Evidentemente el párrafo anterior, aunque resulta fácil de entender para cualquier ser humano, es totalmente incomprensible para un ordenador. Podríamos reescribir la receta de manera algo más formal y precisa, intentando darle apariencia de programa de ordenador (véase el "algoritmo" de más abajo), pero aun así seguiría siendo un galimatías ininteligible para las máquinas. De hecho, aun contando con instrucciones tan precisas de cómo se hace una tortilla de patatas, es normal que a cada uno de nosotros nos salgan tortillas completamente diferentes (yo personalmente, aun no consigo entender qué hace mi mujer para que a ella le salgan las tortillas mucho más ricas que a mi). El problema es que nuestro algoritmo “Tortilla de Patatas” contiene todavía muchos elementos que, o bien tienen interpretaciones subjetivas (¿a qué temperatura se entiende que el aceite no está muy caliente?), o bien están descritos de manera demasiado vaga (¿qué se entiende por cuajar?), y por tanto, no son directamente interpretables por un ordenador. Las recetas, tal y como nos las encontramos en los libros de cocina, no entrarían dentro de lo que en informática se conoce como procedimientos computacionalmente bien definidos, y por tanto, no son directamente interpretables por los ordenadores. Los algoritmos utilizados en informática tienen que ser bastante más precisos que nuestro ejemplo de la tortilla, y basarse en pasitos mucho más pequeños.
1  Cortar patatas en tacos
2  Calentar aceite en sartén
3  Añadir patatas a sartén
4  Añadir cebolla a sartén
5  Freir patatas y cebolla
6  Batir huevos en cuenco
7  Añadir patatas y cebolla al cuenco
8  Quitar aceite sartén
9  Echar la mezcla de cuenco a sartén
10 Cuajar un poco
11 Dar la vuelta
12 Terminar de cuajar
Por tanto, los algoritmos para ordenador deben estar compuestos de sucesiones de pasos muy simples y muy bien definidos. Ejemplos típicos de posibles pasos son: sumar dos números dados, comparar si un número es mayor que otro, comprobar si la tercera letra de la palabra “ejemplo” es una “e”, etcétera. Estos pasos suelen venir agrupados en bloques que se pueden repetir varias veces, también existen pasos en los que es posible tomar decisiones, o incluso se pueden crear grupos de pasos comunes para utilizarlos más de una vez. Además, para que el algoritmo esté completo, es fundamental indicar cuales son los valores de entrada del mismo, y cuales son los resultados o valores de salida. Por ejemplo, un algoritmo podría tener como entrada un conjunto de diez números (17, 1, 5, 13, 15, 9, 21, 2, 4, 8), y como salida devolver el mismo conjunto de números pero ordenados de mayor a menor (21, 17, 15, 13, 9, 8, 5, 4, 2, 1).
Pero no se preocupe el lector si por ahora no entiende del todo cómo son los algoritmos que utilizan los ordenadores, ya que todas estas cuestiones irán quedando más claras a lo largo de las próximas entradas de este blog.

sábado, 17 de agosto de 2013

El Arte de Programar

La mayoría de las ciudades de hoy en día funcionan gracias a los ordenadores. Sea cual sea el lugar a donde vayamos siempre encontraremos un ordenador cerca. Son ya tan comunes que ni siquiera nos damos cuenta de que están ahí, pero basta con detenemos un momento y fijamos con atención para verlos, puede incluso que los encontremos en los lugares más insospechados. En la oficina tenemos ordenadores que nos ayudan a hacer nuestro trabajo; en casa tenemos un ordenador como centro de ocio, para juegos, música y video, o miniordenadores empotrados dentro de los más variados electrodomésticos, como la televisión, el equipo de alta fidelidad, e incluso en el microondas; en el supermercado de la esquina hay unos cuantos ordenadores más, las cajas registradoras, los equipos de inventario; en nuestro coche está el famoso ordenador de abordo, que vigila que todo funciona correctamente; y así un largo etcétera. Y también están aquellos ordenadores que llevamos todo el día de un lado a otro con nosotros, como el teléfono móvil, la agenda electrónica, o el reloj. Hemos llegado a una situación de dependencia tal que nos resulta muy difícil concebir el mundo sin la existencia de los ordenadores (otra cuestión muy distinta es si realmente en todos los casos el ordenador nos hace la vida más fácil).
Lo que nunca hacemos, a menos que uno sea un profesional que trabaja en el mundo de la informática, es pararnos a pensar cómo funcionan todos estos ordenadores. Nos han dicho muchas veces que los ordenadores son en realidad máquinas muy tontas, que para funcionar correctamente necesitan de un conjunto de instrucciones que les digan con todo lujo de detalles qué es lo que tienen que hacer en cada momento, y cómo lo tienen que hacer. También sabemos que estos conjuntos de instrucciones se llaman programas, y que los programas se escriben utilizando los llamados lenguajes de programación, que son muchos y muy variados. Seguramente nos suenen nombres como Visual Basic, Java o C++. Pero en realidad sabemos muy poco sobre la forma y contenido de estos programas, lo cual es perfectamente comprensible, porque a priori parece un tema irrelevante y sumamente aburrido. ¿A quién se le ocurriría estudiar en su tiempo libre el programa que controla un aparato de aire acondicionado? Sin embargo, los programas no son tan aburridos como parece. En el corazón de los programas se encuentran los algoritmos. La mayoría de las veces, estos algoritmos son simples sucesiones de pasos triviales que conducen a la solución de un problema. Por ejemplo, si la temperatura de la habitación ha superado los 25º centígrados, entonces enciende el compresor del aire acondicionado. Pero otras veces, los algoritmos que implementan los programas de ordenador son verdaderas obras de arte del intelecto humano. Quién sabe, a lo mejor el funcionamiento de nuestro aparato de aire acondicionado está basado en una interesantísima teoría matemática de lógica difusa, donde las cosas no son sólo ciertas o falsas, sino que pueden ser medio ciertas o tres cuartos falsas.
El presente blog es precisamente eso, un apasionante viaje por el mágico mundo de los algoritmos. No se necesita nada para poder acompañarnos, no es necesario saber programar, ni saber de matemáticas; tan sólo se necesita curiosidad y muchas ganas de aprender. Así que abróchense los cinturones, que despegamos.