miércoles, 2 de octubre de 2013

Sobre punteros y cajas de zapatos


Una característica esencial de la programación en C es la existencia de punteros. Recuerdo que la primera vez que me los explicaron me quedé con cara de “¿y esto para qué sirve?”.

Pongamos que la memoria de un ordenador se divide en celdas del mismo tamaño, como cajas de zapatos. Cada caja tiene una etiqueta que la identifica, pongamos las letras de la A a la Z (vamos a trabajar con un ordenador con muy poca memoria, pero para el caso será sufciente) y dentro de esas cajas se guardan los valores de las variables que vamos declarando.
(Aquí estamos haciendo una pequeña trampa. En un ordenador todo son números, de modo que decir que usamos letras para etiquetar las cajas es engañoso. En puridad las etiquetas de las cajas deberían numerarse con 1, 2, 3, etc. pero eso podría hacer algo difícil de entender las explicaciones que siguen. Por ejemplo, es menos lioso decir que en la dirección de memoria (caja de zapatos) “A” se almacena un 1, que decir que en la dirección de meoria 1 se almacena un 1. De modo que me voy a permitir la siguiente convención: para los números de las cajas de zapatos vamos a usar el sistema “abecedarial”, en el cual la A equivale al entero 1, la B al entero 2, etc. Es decir, A y 1 son la misma cosa, pero usaremos el sistema abecedarial para las cajas de zapatos y el natural para los valores que guardamos dentro de esas cajas.)
También, y en aras de la simplicidad, vamos a hacer que todas las cajas de zapatos sean del mismo tamaño, y que en ellas sólo vamos a guardar números enteros.
En tal caso, si en un programa “a la C” escribiéramos algo como esto:

int val;
val = 12;
val = val+2;;

En nuestra analogía lo que ocurriría al ejecutar el código es:
  1. Hemos declarado la variable “val”, por lo que necesitaremos asignarle a esta variable una de las cajas de zapatos en la que guardar los valores que le vayamos asignando. Por simplificar vamos a poner que el valor de “val” irá en la caja de zapatos con la etiqueta “A”.
  2. Le asignamos a val el valor 12, de modo que en la caja A, que es la que hemos asignado a val, metemos un 12.
  3. Si ahora fuéramos a la caja de zapatos con la etiqueta “A” encontraríamos un 14.

La manera de saber cuál es la dirección de memoria en la que se guarda el valor de “val” es por medio del operador “&”. Es decir, podemos decir que “&val” vale “A”.

Ahora vamos con los punteros. Los punteros son variables que almacenan la dirección de otra variable, es decir; las etiquetas con que identificamos las cajas de zapatos. En el lenguaje C si queremos declarar un puntero a un entero (es decir, una variable que almacene la dirección de memoria de un entero) debemos escribir;

int *pVal;

Ahora mismo se dice que el puntero pVal no apunta a ninguna parte, es decir, no le hemos dicho la dirección de memoria de qué variable queremos que almacene (sería el caso análogo a cuando declaramos una variable “normal” pero aún no le hemos asignado un valor). O dicho de otro modo, aún no hemos dicho a pVal a qué variable debe apuntar. Si queremos que pVal almacene la dirección de memoria de val, debemos escribir:

pVal = &val;

El operador “&” se llama operador “dirección” (“address” en inglés), y como hemos comentado antes, nos dice la dirección de memoria en la que se está almacenando una variable. Es decir, ahora el valor del puntero pVal es por tanto “A”.

Hay otro operador fundamental cuando trabajamos con punteros, el operador “*” o de “indirection” (me niego a escribir “indirección”... ¡ups!), y nos da el valor de la variable a la que apunta nuestro puntero. O en notación de caja de zapatos: el operador “*” nos dice el contenido de la caja de zapatos de la que nuestro puntero guarda la dirección. Es decir:

int val; // Los valores de val se van a guardar en la caja de zapatos “A”
val = 12; // En la caja de zapatos A metemos un doce
val = val+2; // Ahora hemos cambiado el contenido de la caja A a 14
int *pVal; // Declaramos un puntero a enteros
pVal = &val; // El valor de pVal ahora es “A”, la caja en la que guardamos el valor de “val”

Entonces ahora *pVal vale 14; lo que hay en la caja de zapatos con etiqueta “A” es un 14.

Aquí hay que tener en cuenta algo importante. El operador “*” funciona en ambos sentidos. Es decir, si ahora hacemos:

*pVal = 13;

Lo que hemos hecho es meter un 13 en la caja de zapatos a la que apunta pVal, que es la A, y por lo tanto ahora val valdrá 13. Es decir, por medio del puntero pVal hemos podido cambiar de manera indirecta el valor de la variable val.

Y ahora era cuando venía mi cara de “Todo estoy es muy interesante, pero ¿para qué sirve?”. Uno de los ejemplos clásicos del uso de punteros es el de la creación en C de una función “swap(val1,val2)” que simplemente intercambia el valor de las variables val1 y val2. Es decir, si val1 vale 2 y val2 vale 5 entonces swap(val1, val2) hace que val1 pase a valer 5 y val2 pase a valer 2. La manera más inmediata en que se nos ocurriría hacer esta función sería la siguiente:

#include <stdio.h>

void swap(int i, int j) {
   int tmp = i;
   i = j;
   j = tmp;
}
int main(){
   int val1 = 23;
   int val2 = 47;

   printf("Before. val1: %d, val2: %d\n", val1, val2);
   swap(val1, val2);
   printf("After.  val1: %d, val2: %d\n", val1, val2);

   return 0;
}
Sin embargo, si usáramos esta función para intercambiar el valor de dos variables, nos llevaríamos la sorpresa de que no habría pasado nada. El problema es que en C los argumentos se pasan a las funciones “por valor”. Esto significa que cuando llamemos a una función, se hacen copias de los argumentos, y dentro de la función se trabaja con esas copias.
En notación de cajas de zapatos; si usamos la variable val como argumento de una función, entonces se mirará el contenido de la caja “A”, y se hará una copia de eso en la caja “B” (o la primera caja que esté vacía). Dentro de la función, cada vez que se haga algo sobre val, “en realidad” se estará haciendo sobre el contenido de la caja “B”. De modo que cuando la función haya terminado, cuando queramos volver a comprobar el valor de val, veremos que no ha cambiado nada, ya que el contenido de la caja A no se ha modificado durante todas las operaciones que se han hecho dentro de la función.
Eso es exactamente lo que ocurre con la función “swap” escrita arriba; su lógica es correcta, pero el problema es que el intercambio de valores se hace entre las cajas de zapatos que no nos interesan en este caso.

Por supuesto, ahora viene la pregunta, ¿entonces cómo se definiría una función swap que funcionase? Bien, tenemos que pensar que lo que queremos cambiar es el contenido de las cajas en las que se guardan los valores de “val1 ” y “val2”, y para eso usaremos punteros. La idea de lo que debe hacer la función es:
Tomar las direcciones de las cajas en los que se guardan los valores de las variables val1 y val2, e intercambia los valores que hay en dichas cajas.

Es decir, lor argumentos de la función han de ser sendos punteros a las variables cuyos valores queremos intercambiar, hacer el intercambio del contenido de las cajas a las que hacen referencia, y ¡voi la!

#include <stdio.h>

void swap(int *i, int *j) {
   int tmp = *i;  
   *i = *j;
   *j = tmp;
}
int main(){
   int val1 = 23;
   int val2 = 47;
   int *p1 = &val1;
   int *p2 = &val2;

   printf("Before. val1: %d, val2: %d\n", val1, val2);
   swap(p1, p2);
   printf("After.  val1: %d, val2: %d\n", val1, val2);

   return 0;
}

Ahora todo funciona correctamente. Sin embargo el código anterior está un tanto “sobreactuado”. Si nos fijamos, no necesitamos definir los punteros p1 y p2, y podemos llamar a la función swap simplemente como swap(&val1, &val2), es decir, dando directamente como argumentos las etiquetas de las cajas de zapatos en las que se guardan los valores de las variables val1 y val2.

martes, 20 de agosto de 2013

Bitboards, operadores bitwise y engines de ajedrez


Bitboards, operadores bitwise y engines de ajedrez

“Eso de que el número de casillas del tablero de ajedrez sea una potencia de 2 tiene que ser aprovechable desde el punto de vista de la programación”

Un engine de ajedrez se compone de tres partes principales:
  1. Un generador de movimientos
  2. Una función de búsqueda que nos permite movernos por el árbol de variantes usando el output del generador de movimientos
  3. Una función de evaluación que nos dé un criterio para asignar una puntuación a una posición

De modo que el primer paso es el generador de movimientos. Como una primera aproximación, el generador de movimientos se puede separar en:
  1. GenMove: la función/es que, dada una cierta posición, crea la lista de movimientos posibles, y por otro lado
  2. MakeMove: la función/es que recoge esa lista de movimientos y los ejecuta de hecho sobre el tablero

Por ejemplo, es habitual codificar un movimiento en un entero de 16 bits (en los 6 primeros se guarda la casilla inicial, en los 6 siguientes la casilla de destino y en el resto otro tipo de información, como por ejemplo si se trata o no de una captura). De modo que que nuestra función GenMove devolvería un array de enteros de 16 bits y de longitud el número de movimientos legales (suponiendo que nuestro generador de movimientos devolviera sólo movimientos, lo que suele ser habitual, pero no necesario). Luego la función MakeMove iría ejecutando estos movimientos uno a uno para moverse por el árbol de variantes.

A la hora de desarrollar un engine de ajedrez uno de las principales decisiones que se han de tomar es la de cómo representar la posición que tenemos en el tablero. Y en concreto, cómo representar la información sobre cada pieza.
Los bitboards son básicamente la representación de la información de la posición del tablero por medio de enteros de 64 bits. Por ejemplo, podemos usar un entero de 64 bits para representar la posición de los caballos blancos en la posición inicial, usando un bit por cada casilla; el bit que representa una casilla vale 0, y vale y 1 si en la casilla hay un caballo blanco:


























































n




n



0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0



Es decir, la posición inicial de los caballos blancos viene representada por el entero 1000010. O puesto en forma de entero de 64 bits:
00000000 00000000 00000000 00000000 00000000 00000000 00000000 01000010

y si ahora lo ordenamos convenientemente para que se asemeje a un tablero de ajedrez:

00000000
00000000
00000000
00000000
00000000
00000000
00000000
01000010

Evidentemente, habría que hacer lo mismo para cada pieza. De este modo, nuestro programa podría tener una clase/estructura Tablero, con los miembros peonesBlancos, caballosBlancos, etc. O podemos preferir guardar esta información en un array de enteros de 64 bits de dimensiones [2][6]: 2 bandos con 6 piezas diferentes cada uno.

Bien, hasta ahora, aparte de que hemos almacenado la información de la posición del tablero de una manera bastante compacta y económica (lo que por otro lado en los ordenadores actuales tampoco es de gran utilidad), no parece que hayamos hecho gran cosa, de modo que vamos a ver qué nos ofrece el uso de nuestros amigos los bitboards, en concreto en lo relacionado con la generación de movimientos.

Pongamos que tenemos la posición inicial y queremos saber a qué casillas se puede mover el caballo blanco de b1. En nuestro entero de 64 bits caballosBlancos tenemos la información sobre la posición de nuestros caballos, y queremos calcular los posibles destinos de esta pieza, que en principio serían las casillas a3, c3 y d2. Aquí nos podemos dar cuenta de una cosa; cuando un caballo blanco (o para el caso de cualquier color) se encuentra en la casilla b1, las casillas a las que potencialmente puede saltar son siempre las mismas: a3, c3 y d2, de modo que ¿por qué no crear un array de 64 enteros de 64 bits (al que podríamos llamar algo así como uint64 saltosCaballos[64]) que en cada elemento tenga un bitboard que represente las casillas a las que puede saltar un caballo desde dicha casilla? Es decir, el elemento que se corresponde con la casilla b1 (saltosCaballos[b1]) puesto en binario y bien ordenadito sería:

00000000
00000000
00000000
00000000
00000000
10100000
00010000
00000000

Excelente; ahora se presenta un problema. En la posición inicial, el caballo de b1 no puede saltar a d2, ya que ahí se encuentra un peón blanco (si fuera un peón negro no habría problema: el hecho de que se tratara de una captura en vez de un movimiento “normal”, de momento lo dejaríamos de lado: añadiríamos esta información en el entero de 16 bits que codifica el movimiento y luego el MakeMove se encargaría de gestionar esa información a la hora de hacer el movimiento sobre el tablero). Muy bien, ahora es cuando entran en juego nuestros amigos los operadores bitwise. Si generamos un entero de 64 bits (al que podríamos llamar piezasBlancas) en el que cada bit valga 1 si en la casilla que representa hay una pieza blanca y un cero en caso contrario, es decir, para la posición inicial:

00000000
00000000
00000000
00000000
00000000
00000000
11111111
11111111

entonces ya casi lo tenemos: sólo tenemos que hacer una operación AND a nivel de bits entre el bitboard saltosCaballos[b1] y el complementario del entero de 64 bits que hemos llamado piezasBlancas, que en jerga de operadores bitwise se obtendría como “~piezasBlancas” y tendría la pinta

11111111
11111111
11111111
11111111
11111111
11111111
00000000
00000000

Ahora sí que lo tenemos: si hacemos la operación saltosCaballos[c1] & (~piezasBlancas) obtendríamos las casillas a las que podría saltar un caballo en la posición inicial desde b1. Puesto en forma de binarios ordenaditos:

saltosCaballos[c1]
&
~piezasBlancas
=
casillasDestino
00000000
00000000
00000000
00000000
00000000
10100000
00010000
00000000
AND
11111111
11111111
11111111
11111111
11111111
11111111
00000000
00000000
EQUAL
00000000
00000000
00000000
00000000
00000000
10100000
00000000
00000000


Por cierto, en este momento puede ser interesante comentar que, por lo que dicen los sabios del lugar, una de las ventajas de trabajar con operaciones bitwise es que estas son ultra-rápidas.

Ahora debemos recordar que nuestra finalidad es la de crear una lista de movimientos, de modo que ahora tendríamos que ingeniárnoslas para, con la información obtenida en los pasos anteriores, crear dos movimientos que irían a nuestra lista de movimientos posibles para la posición actual:
  1. La pieza que está en b1 se mueve a a3
  2. La pieza que está en b1 se mueve a c3

Una pista: para esta parte de la generación de movimientos es necesario tener una función que encuentre el “least significant bit” de un entero. Pero esta es otra historia y, quizás, será contada en otro momento.

¿Y qué ocurre con el resto de las piezas?
Para el caso del movimiento de los reyes la cosa es prácticamente idéntica: simplemente se pueden mover a cualquier posición de destino con tal de que no esté ocupada por una pieza del mismo bando.

Con las denominadas “slide pieces”, la cosa se complica algo, ya que las reglas no son tan sencillas como para el caso de los caballos y los reyes, pero con ayuda de los operadores bitwise se acaba obteniendo un generador de movimientos muy rápido.

Hasta aquí sobre los bitboards en lo relacionado a la generación de movimientos, pero hay otra parte del diseño de un engine de ajedrez en la que estos animalitos son la mar de útiles: la evaluación.
Los bitboards son una manera muy manejable de almacenar la información de lo que tenemos en el tablero, y además las operaciones lógicas con operadores bitwise son muy rápidas. Esto nos permite responder con una gran eficiencia a preguntas tales como “¿está esta torre en una columna abierta?”, “¿este es un peón pasado?”, “¿tiene el blanco peones en e4 y d4?”.
Hay que tener en cuenta que una vez que tenemos un engine de ajedrez funcionando, el 99% del tiempo de cpu se gasta en la función de evaluación, de modo que el uso de bitboards mata dos pájaros de un tiro: nos proporciona un generador de movimientos muy rápido (que evidentemente es el primer cuello de botella a la hora de desarrollar un engine: lo más rápido a lo que puede “ir” nuestro engine está limitado por la velocidad a la que puede hacer movimientos sin evaluación), y nos da una estructura de datos que nos permite llevar a cabo operaciones muy rápidas en la función de evaluación.

sábado, 9 de febrero de 2013

Deconvolucióname esa miopía.

Como todo el mundo sabe, cuando se lanzó el telescopio Hubble tenía un defecto en el espejo. Algo que posteriormente se solucionó con lo que la prensa denominó unas "gafas", es decir, un conjunto de espejos accesorios que contrarrestaban los errores del espejo principal.

Pero eso no quiere decir que mientras tanto el Hubble no estuviera operativo. Algo que es menos conocido es que las imágenes con aberración se procesaron con programas que eran capaces de reconstruir, con bastante precisión, la imagen real.

La técnica usada se denomina deconvolución que, como su nombre indica, es una forma de deshacer el efecto de una  convolución.

La convolución se suele definir en términos de integrales del producto de dos funciones cualesquiera; sin embargo, en la práctica, las dos funciones suelen ser distintas cualitativamente. Una suele ser una señal y la otra una "máscara". En el caso que nos ocupa (imágenes), un caso típico de convolución podría ser sustituir cada píxel de una imagen con la media de ese píxel y los ocho que lo rodean. En ese caso, una de las funciones es la propia imagen, la otra un cuadrado formado por nueve píxeles y el resultado de la convolución, un simple suavizado.

Por supuesto, la convolución no tiene por qué ser un suavizado/desenfocado, pero en este artículo voy a suponer que sí.

Como vemos, la convolución descrita más arriba es una operación lineal, que puede expresarse como el producto de una matriz por un vector que representa a la imagen:

\begin{aligned} b=Ax \end{aligned}

En ese caso, \(b\) representa la imagen desenfocada y \(x\) la imagen original.

En principio parece posible obtener la imagen original a partir de la desenfocada simplemente haciendo:

\begin{aligned} x=A^{-1}b \end{aligned}

En realidad, las cosas no son tan sencillas porque la matriz \(A\) es singular, sin embargo es posible convertirla en no singular haciendo ciertas suposiciones sobre el comportamiento de la imagen en los contornos.

Esto último es mucho más sencillo en el caso de imágenes del espacio ya que éstas tienen una estructura más o menos conocida (puntos luminosos sobre negro).


Hasta aquí nada realmente nuevo. Cualquiera con interés puede echarle un vistazo al paquete de procesado de señal de Matlab.

Lo que quiero contar en esta entrada es otra cosa. Hace tiempo tuve la idea de que quizás fuese posible hacer lo contrario, es decir, aplicar una deconvolución a una imagen y luego aplicarle una convolución para recuperar la imagen original.

En principio, no existe ningún problema y estoy seguro de que aquellos que tengan Matlab (yo no) pueden probarlo fácilmente. Lo interesante de mi idea es que la parte de la convolución la harían mis propios ojos con la ayuda de unas pocas dioptrías.

Uno de los problemas de esto es que al deconvolucionar una imagen enfocada obtenemos otra "imagen" que incluye números negativos. Puesto que no parece posible hacer una imagen real con intensidades negativas (quizás con láseres...), es necesario desplazar las intensidades "hacia arriba", de forma que todos los valores sean positivos. Eso implica que la imagen final no va a tener negros bien definidos.

Hoy, finalmente, creí haber encontrado en Google un artículo sobre el tema. Resultó ser una inocentada (el artículo trata de unas gafas virtuales); pero creo que las imágenes que usan son reales. Aquí están:


Lo llamo "Bodegón deconvolucionado"


Lenna

No se ven perfectas, pero a cierta distancia y sin gafas, las veo muchísimo mejor que con gafas. Evidentemente, es necesario probar con diferentes tamaños de imagen y distancias.

Ahora sólo falta mejorarlo un poco y podré volver a ver la tele sin gafas.

miércoles, 30 de enero de 2013

¡Esqueuomorfo!

Pues no, no es un insulto del capitán Haddock. Un esqueuomorfo es la conversión en ornamento de un elemento que anteriormente era necesario.

Ejemplos típicos son superficies plásticas imitando madera o metal, bolsillos o botones que no funcionan en la ropa o relojes digitales con LCD simulando manecillas.

Barato, barato jefe.
En el mundo digital los esqueuomorfos están por todas partes. Los "archivos" se guardan en "carpetas" que, en la mayoría de programas, se representan con dibujos de una hoja de papel y una carpeta de cartulina respectivamente. Para grabar hacemos clic en un botón que tiene un dibujo de un disquette y para enviar un mensaje pulsamos otro que muestra un sobre. Los smartphones siguen incluyendo dibujos de auriculares de sus versiones antiguas, no tan smart.


En parte, la existencia de estos esqueuomorfos es natural. No es tanto una cuestión ornamental como utilitaria. En el proceso de cambio de un sistema a otro es normal que se mantengan ciertos usos y convenciones para facilitar el proceso.

Sin embargo parece que muchos esqueuomorfos sobreviven a la que debería ser su fecha de caducidad. Hace años que casi nadie tiene teléfonos del tipo representado en la imagen y muchos jóvenes pueden no haber tenido nunca uno en sus manos.

No me parece mal. Palabras como colgar el teléfono se siguen usando, aunque hace muchos años que los teléfonos no se cuelgan. De hecho, los únicos que se colgaban en el sentido estricto eran estos:


Pero la palabra nos sigue sirviendo más de un siglo después. En realidad, la etimología de muchas palabras suele esconder sorpresas como esta, así que no debe extrañarnos que pueda existir una etimología ("estudio del verdadero origen") de los iconos y otros elementos de las interfaces digitales.

El problema surge cuando esos esqueuomorfos (también conocidos como metáforas visuales) interfieren con el funcionamiento de las cosas. Apple es conocida por abusar de estos elementos: los IPad muestran libros en una estantería de madera en los que, una vez abiertos, las "páginas" se "pasan" con un movimiento que imita al de su versión de papel.


En realidad, el propio concepto de página es en teoría innecesario aunque, por el momento, útil. Pero no le veo utilidad ni gusto a la librería ni al paso de páginas. Hay muchas formas más eficientes de conseguir el mismo efecto.

Parece ser que en Apple, el gusto por lo esqueuomorfo provenía de Jobs y era obra de uno de sus acólitos, Scott Forstall. Este último fue despedido poco después de la muerte del primero y Jonathan Ive, declarado antiesqueuomorfo, ha extendido su influencia al diseño de las interfaces, así que es de esperar que las cosas cambien. Para bien, desde mi punto de vista.

La tendencia entre los que usamos ordenadores unas doce horas al día me parece que es la opuesta. Generar usos y convenciones puramente digitales, que no sean contrapartidas de sus versiones analógicas (si las hubiera). De hecho pienso que hay quien se pasa y acaba teniendo en sus pantallas esqueuomorfos de ordenadores de los 60, pero esa es otra historia.

vi
Poco a poco, editores de texto basados en WYSIWYM empiezan a sustituir a los WYSIWYG (es decir, editores que dan importancia al contenido y no al formato final en una página de papel). Formatos de dibujo como SVG son concebidos directamente como algo que va a ser representado en una pantalla y no impreso en una hoja de papel.

Para los interesados en el tema recomiendo el artículo "La interfaz antimac", que no es tanto una crítica a la interfaz de los Mac como una serie de ideas para pasar de la infancia a la madurez de las interfaces de usuario.


viernes, 18 de enero de 2013

¿Cómo funciona Google?

En esta entrada voy a explicar como funciona PageRank, el algoritmo que puso a Google en cabeza de los buscadores de Internet.

Lo primero que debemos de saber es que lo que diferencia Google de otros buscadores no es la cantidad de páginas que indexa (aunque es posible que también sea el mejor en eso), ni en cómo encuentra páginas que contienen los términos de búsqueda. Esas cosas se sabían hacer antes de que Google apareciera.

La diferencia clave reside en cómo ordena los resultados. Más concretamente, Google ordena todas las páginas por importancia cada cierto tiempo y cada vez que realizamos una búsqueda, los resultados aparecen siguiendo ese mismo orden.

De hecho esto último probablemente no es del todo cierto. Google ha ido haciendo cambios y mejoras al algoritmo base, y es posible que al final los resultados incluyan variaciones respecto al orden general, quizás dando mayor relevancia a noticias recientes, resultados con imágenes, vídeos o cosas por el estilo.

Tampoco voy a entrar en cómo se las arregla para trabajar con páginas dinámicas y otras muchas cosas, ya que lo desconozco. En lo que sigue voy a suponer que Internet es como era en el 1992, cuando el porno consistía en páginas escaneadas de revistas.

En esta entrada me voy a centrar en el algoritmo básico y en como usa los autovectores de una matriz para realizar la ordenación (esto es también un aviso para los que no sepan lo que es un autovector).

3º premio en el certamen de chistes visuales de Cuenca.
La idea básica del método consiste en pensar lo siguiente: supongamos que en cierto momento hay varias personas viendo cada página de Internet. En ese instante y cada segundo, cada persona hace clic en un enlace al azar. Al cabo de cierto tiempo habrá ciertas páginas que tengan más personas que otras. La idea de PageRank es que las páginas en las que haya más personas son más interesantes y deben colocarse primero en la lista.

Veamos cómo es el algoritmo:

El primer paso es construir una lista ordenada de ellas, de forma que a cada página le asignamos un número natural.

El siguiente paso consiste en construir una matrix C de "clics". Esta matriz simula el proceso de que una persona en cierta página haga un clic al azar en un enlace.


Para ello supongamos que tenemos a una persona en la página web de índice uno. Esa página contiene sólo dos enlaces, uno a la página web de índice 45 y otro a la de índice 371.

Lo más sencillo es suponer que la persona tiene una probabilidad de 0.5 de ir a cada enlace. En lo que sigue voy a suponer que todos los enlaces son igualmente probables, aunque este es un punto claramente mejorable y estoy seguro de que Google lo ha hecho.

Para modelar una persona en la página 1 vamos a utilizar un vector de dimensión N, donde N es el número total de páginas indexadas. En este caso el vector b tiene la forma:

\begin{aligned}  \left( \begin{array}{ccc} 1 \\  0 \\  0 \\  \vdots \\ 0 \\


\end{array} \right) \end{aligned}

Donde el 1 en la primera entrada significa que hay una persona en la página uno.

Ahora queremos construir una matriz que represente el hecho de que, hay una probabilidad de 0.5 de que esa persona acabe en la página 45 y la misma de que acabe en la página 371. En realidad, esto sólo define la primera columna de la matriz, que será:

\begin{aligned} \left( \begin{array}{ccc} 0 \\ \vdots \\ 0 \\ 0.5 \\ 0 \\ \vdots \\ 0 \\ 0.5 \\ 0 \\ \vdots \\ 0 \end{array} \right) \end{aligned}

Donde los 0.5 están colocados en las filas 45 y 371.

Si suponemos por un momento que el resto de columnas de C están formadas por ceros, el resultado de multiplicar C por el vector anterior es igual a la columna anterior, es decir, tras el primer paso, la mitad de la personas que estaban en la página 1 estarán ahora en la página 45 y la otra mitad en la página 371.

Supongamos que hacemos lo mismo para el resto de páginas, rellenando el resto de columnas de C (en el caso de páginas sin enlaces supondremos que saltamos a una página cualquiera al azar).

El resultado de multiplicar esta nueva C por el vector b será el mismo, ya que el resto de columnas están multiplicadas por los ceros de b.

Pero si b tuviese otros elementos distintos de cero, veríamos cómo a la página 45 (por poner un ejemplo) podría venir gente desde la página uno, pero también desde distintas páginas.

Si pensamos que el vector b contiene la probabilidad de que una persona esté en cualquiera de las páginas, el vector resultado del producto Cb contendrá las probabilidades después de que pulsen al azar cualquiera de los enlaces en sus respectivas páginas.

Cláramente, el vector CCb contendrá las probabilidades tras dos clics y, en general, \(C^nb\) las probabilidades tras n clics.

Nosotros (o mejor dicho, Google) estamos interesados en saber el comportamiento tras muchos clics, es decir, estamos suponiendo que con el tiempo la situación se estabiliza y las probabilidades tras un clic no cambian, es decir:

\begin{aligned} C^{n+1}b = C^nb, ~~~~n \rightarrow \infty \end{aligned}

O:
\begin{aligned} Cb' = b' ,~~~~ b' = \lim_{~n \rightarrow \infty} C^nb  \end{aligned}

Dicho de otra forma, buscamos el autovector b' que corresponde al autovalor 1 de la matriz C. Ese autovector contiene las probabilidades de que haya una persona en cada una de las páginas indexadas. El paso final consiste en ordenar las páginas según esa probabilidad (que no es otra cosa que su PageRank).

No voy a entrar en los algoritmos que existen para encontrar autovalores de matrices. Hay varios, pero seguro que Google tiene sus métodos propios. En cualquier caso, seguro que les lleva días llegar a una solución aproximada.



sábado, 12 de enero de 2013

BREVES: Hackerspaces

Esta semana he estado en el hackerspace de Rochester, NY.

¿Qué es un hackerspace? pues un espacio para que los hackers se reúnan y hagan sus cosas. Pero ¿qué es un hacker?

Normalmente, algo así
Supongo que la mayoría lo sabéis, pero por si hay algún despistado, Wikipedia dice:

  • Gente apasionada por la seguridad informática. Esto concierne principalmente a entradas remotas no autorizadas por medio de redes de comunicación como Internet ("Black hats"). Pero también incluye a aquellos que depuran y arreglan errores en los sistemas ("White hats") y a los de moral ambigua como son los "Grey hats".
  • Una comunidad de entusiastas programadores y diseñadores de sistemas originada en los sesenta alrededor del Instituto Tecnológico de Massachusetts (MIT), el Tech Model Railroad Club (TMRC) y el Laboratorio de Inteligencia Artificial del MIT.2 Esta comunidad se caracteriza por el lanzamiento del movimiento de software libre. La World Wide Web e Internet en sí misma son creaciones de hackers.3 El RFC 13924 amplia este significado como "persona que se disfruta de un conocimiento profundo del funcionamiento interno de un sistema, en particular de computadoras y redes informáticas"
  • La comunidad de aficionados a la informática doméstica, centrada en el hardware posterior a los setenta y en el software (juegos de ordenador, crackeo de software, la demoscene) de entre los ochenta/noventa.

También existen hackers fuera del ámbito de la informática, aunque en casi todos los casos tienen alguna relación con la electrónica.

Volviendo a los hackerspaces, se trata de clubes donde los hackers se reúnen, construyen aparatos, programan cosas y se sientan en sillones a hablar de sus cosas mientras comen chocolatinas.

Sin embargo, cuando llegué allí no tenía muy claro lo que era. Tras unos cuantos minutos buscando el sitio (unas oficinas sin ningún tipo de cartel en una especie de centro tecnológico antiguo) entré en lo que parecía ser un taller de carpintería: trozos de madera por el suelo, herramientas, lijas, un torno...

En una mesa en el centro había una impresora 3D, lo que me demostró que no me había equivocado de sitio.

En otra habitación había una sala de reuniones y allí, por fin, estaban los hackers de Rochester. Me estuvieron contando qué hay que hacer para ser socio ($50 al mes te dan acceso a cualquier hora del día al recinto) y me mostraron las instalaciones. Aparte de lo ya dicho tenían todo tipo de ordenadores en varios estados de evolución, un pequeño clúster, un osciloscopio, generadores de ondas, otra impresora 3D y diversos objetos impresos, un plotter...

¡Mujeres!
Después nos sentamos un buen rato a hablar de ordenadores de 8, 12 y 16 bits, programación en ensamblador y muchas otras cosas divertidas. Al final me contaron que hay un hackerspace de nueva creación en Ithaca, así que voy a poder librarme de las 4 horas de viaje (2+2), porque sino me iban a tener allí todas las semanas.

sábado, 5 de enero de 2013

BREVES: Al filo de la noticia

De nuevo una entrada insipirada en una noticia. El País de hoy incluye una noticia sobre Tizona, la espada de El Cid.

La Tizona de El Cid es indivisible
Una sentencia reconoce la titularidad parcial de la histórica espada a favor de las legatarias de un marqués que desheredó a sus parientes quienes, no obstante, la vendieron en Burgos.
La noticia describe la historia de la espada desde la muerte de El Cid y cómo llegó a sus actuales dueños. No obstante, el autor tiene el cuidado de llamarla en un momento "supuesta Tizona". Un detalle de saludable escepticismo que no se extiende al resto del artículo.

La espada en cuestión es esta:


Parte de la larga descripción que se hace de sus características dice:
El acero, que cuenta con una acanaladura en el interior de su filo para acelerar la muerte de los estoqueados mediante la introducción de aire desde la herida, formaba parte del ajuar de Rodrigo Díaz de Vivar [...]
La supuesta utilidad de la acanaladura me pareció sospechosa. Primero porque hace años había escuchado otra explicación (facilitar la salida de la sangre) y siempre hay que sospechar de cosas que tienen más de una explicación. Segundo porque la acanaladura sólo ocupa la mitad del filo,  precisamente la mitad que no lo necesita si creemos esa explicación.

Una búsqueda rápida me llevó a Wikipedia:
A fuller is a rounded or beveled groove or slot in the flat side of a blade (e.g. a sword, knife, or bayonet). A fuller is often used to lighten the blade, much in the way that an I-beam shape allows a given amount of strength to be achieved with less material. Longer knives or bayonets intended as offensive weapons may employ fullers (also incorrectly known as 'blood grooves' or 'blood letters') to lighten the blade while maintaining its strength. When combined with proper distal tapers, heat treatment and blade tempering, a fullered blade can be 20% to 35% lighter than a non-fullered blade without any sacrifice of strength or blade integrity. This effect lessens as the blade is reduced in length. Short bladed knives may employ fullers simply for their aesthetic effect.

En resumen, que esas acanaladuras (fullers) sirven para reducir el peso de las espadas y cuchillos largos (entre un 20% y un 35%) sin disminuir su rigidez. Teniendo en cuenta que el peso es un factor de enorme importancia en las espadas, la explicación tiene mucho más sentido.

El párrafo también afirma que las acanaladuras en cuchillos cortos sólo tienen utilidad estética, aunque otras páginas dicen que también en ellos se hace por cuestiones de peso. Todas ellas coinciden en negar la explicación de dejar salir la sangre o facilitar la entrada de aire.

Otra razón que se me ocurre para el caso de los cuchillos cortos es reducir la cantidad de hierro usado. Esto puede ser importante cuando hablamos de grandes cantidades en tiempos de guerra, cuando el hierro es un recurso escaso.