Matemáticas detrás de Google

Motor de búsqueda de Google

Los fundadores de Google Sergey Brin y Larry Page se conocieron en 1995 cuando Page visitó el Departamento de Informática de la Universidad de Stanford durante un fin de semana de reclutamiento [1]. Brin, a la sazón estudiante de doctorado, sirvió como guía de un grupo de potenciales estudiantes de doctorado del que Page era parte. Ellos discutieron de muchos asuntos durante su primer encuentro y discreparon sobre casi cada cuestión. Poco después de iniciar los estudios en Stanford, Page comenzó a trabajar sobre un proyecto de Web, al principio llamado BackRub, que explotaba la estructura de los enlaces en la Web. Brin encontró interesante el trabajo de Page sobre BackRube, y comenzaron a trabajar juntos sobre un proyecto que cambiaría drásticamente la búsqueda en la Web. Brin y Page se dieron cuenta que estaban creando un motor de búsqueda que se adaptaba al continuo incremento del tamaño Web, así que reemplazaron el nombre BackRub por Google (una escritura incorrecta común de googol, el número ). Incapaces de convencer a las empresas existentes de motores de búsqueda para adoptar la tecnología que habían desarrollado, pero con la certeza de que su tecnología era superior a cualquiera de las que se usaban entonces, Brin y Page decidieron iniciar su propia empresa. Con la ayuda financiera de un pequeño grupo de inversionistas iniciales, Brin y la Page fundaron la empresa de Web de búsqueda de motor Google S.A. en septiembre de 1998.
Casi inmediatamente, el público en general notó lo que Brin, Page, y otros en la comunidad académica sobre búsqueda en la Web ya sabían – el motor de búsqueda Google producía resultados de más alta calidad que aquellos producidos por otros motores de búsqueda en la Web. Otros motores de búsqueda confiaban completamente en el contenido de página web para determinar la clasificación de resultados, y Brin y Page comprendieron que los realizadores de páginas web fácilmente podrían manipular el ordenamiento de resultados de búsqueda colocando información oculta en las páginas web. Brin y Page desarrollaron un algoritmo de clasificación, llamado PageRank, que usa la estructura de los enlaces de la Web para determinar la importancia de las páginas web. Durante el proceso de búsqueda, el algoritmo de Google combina “pesos” previamente calculados por PageRank con valores del texto buscado para obtener un peso o valor total para cada página web.
Aunque muchos factores determinan los resultados de la clasificación general que hace el motor de búsqueda de Google, sus autores mantienen que el corazón de su motor de búsqueda es el software PageRank [2]. Tanto la comunidad académica como la empresarial tienen en gran estima a Google. El empresariado sabe que PageRank juega un papel sustancial en la orden en el cual las páginas web son mostradas. El maximizar el peso o valor que PageRank asigna a una página web se ha convertido es un componente importante de las estrategias de marketing de las compañías. La comunidad académica reconoce que PageRank tiene conexiones con numerosas áreas de matemáticas e informática como teoría de matrices, análisis numérico, recuperación de información y teoría de grafos. Por consiguiente, mucha investigación sigue siendo dedicada a la explicación y el mejoramiento de PageRank.

Las Matemáticas de PageRank

El algoritmo PageRank asigna un valor a cada una de las más de 25 mil millones de páginas web [3]. El algoritmo modela el comportamiento de un “navegador” idealizado arbitrario dentro de la Web [4, 5]. Este usuario de Internet escoge aleatoriamente de una lista de páginas web disponibles, una de ellas para verla. Luego, el usuario continúa el proceso de seleccionar enlaces aleatoriamente de sucesivas páginas web hasta decidir moverse a otra página web por algún otro medio diferente al de seleccionar un enlace. La elección de cuál página web visitar después no depende de las páginas web antes visitadas, y el usuario “idealizado” de Web nunca se “cansa” de visitar a páginas web. Así, el peso PageRank de una página web representa la probabilidad que un usuario arbitrario de Web escogería ver la página web.
En un próximo post presentaré un resumen de los detalles matemáticos de PageRank, así como de algunos aspectos teóricos de relevancia [6].

REFERENCIAS
[1] http://www.google.com/corporate/history.html

[2] http://www.google.com/technology/index.html

[3]http://www.webrankinfo.com/english/seo-news/topic-16388.htm, Increased Google Index Size?

[4] Sergey Brin and Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems 33 (1998), 107–117.

[5] Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd, The PageRank citation ranking: Bringing order to the web, Tech. report, Stanford University, 1998.

[6] Carlos Ferreiro, Matemáticas detrás de Google, en preparación.

Roma y las matemáticas

El periodo durante el cual los romanos figuran en la historia comprende los años que van desde aproximadamente el 750 a. C. hasta el 476 de nuestra era, más o menos el mismo tiempo durante el cual floreció la civilización griega. Además, a partir del 146 a. C. los romanos estuvieron en estrecho contacto con los griegos, tras haber conquistado Grecia propiamente dicha luego de la tercera guerra púnica.
Desgraciadamente, los matemáticos están sujetos a los designios de la historia, igual que el último labrador. Mientras la civilización greco-alejandrina estuvo gobernada por los Ptolomeos, floreció. El primer desastre fue el advenimiento de los romanos, cuyo único papel en la historia de las matemáticas fue el de agentes de destrucción, incluso física, como consecuencia del incendio provocado por César en el 46 a. C. para quemar la flota egipcia anclada en el puerto de Alejandría; el fuego se extendió a la ciudad y quemó la Biblioteca: dos siglos y medio de recolección de libros y medio millón de manuscritos, que representaban el esplendor de la antigua cultura, fueron borrados. El declive de la civilización griega, que durante cinco o seis siglos aportó contribuciones que sobrepasan en gran medida, tanto en extensión como en brillantez, a las de cualquier otra, comienza con el principio de la era cristiana, cuando estaba dominada políticamente por Roma. Las únicas contribuciones importantes de la nueva era fueron las de Ptolomeo y Diofanto, además de las interesantes recopilaciones de Pappus y Proclo.
Si bien es cierto que el declinar de la matemática griega viene acompañado con el predominio de la matemática aplicada desde los trabajos de Hiparco y Herón (los libros de éste parecen cuadernos de notas tomadas por un estudiante en lo que equivaldría a un instituto tecnológico en Alejandría) hasta los de Ptolomeo, con excepción de los trabajos de Diofanto, es más que probable que esa tendencia a las aplicaciones técnicas fuese el resultado de la decadencia más que su causa, pero en cualquier caso los dos fenómenos se dieron simultáneamente. No hay duda de que se llevaron a cabo importantes progresos en astronomía, geografía, óptica y mecánica, pero en cambio los avances en la matemática fueron poco significativos. Algunos historiadores como, B. L. van der Waerden, atribuyen esta decadencia a las insuficiencias y limitaciones del álgebra geométrica griega, pero otros, como E. T. Bell, M. Kline o C. Boyer, al devastador impacto de Roma. A veces se ha sostenido la tesis de que la matemática se desarrolla mejor y de una manera más eficaz cuando mantiene un estrecho contacto con las aplicaciones técnicas mundanas, pero el periodo que estamos estudiando apoyaría más bien la tesis opuesta. La pérdida del genio creador en religión y filosofía, que condujo a los griegos a dedicarse al misticismo y a los cultos esotéricos, se ve reflejado en las matemáticas por un persistente movimiento dirigido hacia las aplicaciones.
La muerte de Arquímedes a manos de un soldado romano pudo ser sólo una casualidad, pero el hecho es que resultó verdaderamente profética. A lo largo de su dilatada historia, la antigua Roma contribuyó poco a la ciencia o a la filosofía, y aún menos a la matemática. Tanto durante la República como en los días del Imperio, los romanos se vieron muy poco atraídos por las investigaciones del tipo lógico o especulativo. Los impresionantes proyectos de ingeniería y los grandes monumentos arquitectónicos tienen sin duda cierta relación con los aspectos más elementales de la ciencia, pero los constructores romanos se contentaban con simples recetas y maneras de proceder que bien poco requerían un conocimiento del gran corpus del pensamiento griego. Es como si pensaran, ante lo prolífico de la cultura griega, que ya “todo” estaba descubierto o inventado en matemáticas: ¡los griegos se habían encargado de ello! Incluso el grado de familiaridad de los romanos con la ciencia griega no fue profundo como se puede juzgar a partir de libro De Architectura de Vitruvio donde llega a resultados sobre perímetros, áreas, π y otros problemas relativos a medidas aproximadas en agrimensura, con peor grado de exactitud que en los trabajos de Arquímedes. Roma era un pueblo práctico y, más aún, hacían alarde de su practicismo.
Bien es verdad que estos siglos fueron testigos del desarrollo inicial de la trigonometría, pero esta materia que ahora forma parte de la matemática pura era entonces, en el mejor de los casos, una aplicación de la geometría elemental a las técnicas de medición, que respondía a las necesidades de la astronomía. En cualquier caso, esta época se caracterizó no sólo por una decidida ausencia de progreso, sino por una franca decadencia. Sin embargo, para apuntalar el dicho que reza “no hay mal que por bien no venga”, cabe decir que fueron precisamente estos aspectos de la matemática griega los que más interesaron a los sabios árabes e indios que, posteriormente, iban a servir de puente entre la matemática antigua y el mundo moderno.
Las matemáticas griegas destacaban en el campo de la geometría pero la matemática romana era básicamente contabilidad. El desarrollo de Roma es más importante desde un punto de vista estrictamente tecnológico (desarrollo de infraestructuras a una escala considerable). Los romanos carecieron casi por completo de creatividad matemática: durante cerca de ¡once siglos! no hubo ningún matemático (destacado) romano. La actividad romana acerca de las matemáticas viene dada por las palabras de Cicerón: “Los griegos dieron al geómetra el más alto honor; de acuerdo con esto, nada tenía un progreso más brillante que las matemáticas. Pero nosotros hemos establecido como límite de este arte su utilidad para medir y contar”.

Bibliografía

Boyer, Carl B. Historia de la matemática. Ed. Alianza, 1986.

Fractales en Informática

Un fractal es un objeto semi-geométrico cuya estructura básica, fragmentada o irregular, se repite a diferentes escalas. El término fue propuesto por el matemático francés Benoît Mandelbrot [1] en 1975 y deriva del Latín fractus, que significa quebrado o fracturado. Muchas estructuras naturales son de tipo fractal.
A un objeto geométrico fractal se le atribuyen las siguientes características:
i) Es demasiado irregular para ser descrito en términos geométricos tradicionales.
ii) Posee detalle a cualquier escala de observación.
iii) Es autosimilar (exacta, aproximada o estadísticamente).
iv) Su dimensión de Hausdorff-Besicovitch es estrictamente mayor que su dimensión topológica.
v) Se define mediante un simple algoritmo recursivo.
Un fractal natural es un elemento de la naturaleza que puede ser descrito mediante la geometría fractal. Las nubes, las montañas, hojas de árboles, el sistema circulatorio, las líneas costeras o los copos de nieve son fractales naturales. Esta representación es aproximada, pues las propiedades atribuidas a los objetos fractales ideales, como el detalle infinito, tienen límites en el mundo natural.
Dentro de las aplicaciones de los fractales, las que se presentan en la Informática son verdaderamente impresionantes y creativas, permiten el desarrollo de muchas cosas distintas (técnicas) y se considera pionera en el campo de sus aplicaciones.
La aplicación más común es la de la Transformación Fractal, proceso que se utiliza en el tratamiento de imágenes para reducir su espacio "físico" (o peso en bytes) mediante esta técnica, que explota la característica que tienen estos objetos que conservan su esquema básico independientemente de cuantas veces se amplíen, es decir, contienen una imagen de sí mismos en cada una de sus partes (autosimilaridad)
La primera vez (o mejor dicho, la primera "conocida" vez, ya que se hacía desde antes) que el público pudo observar esta forma de utilización del proceso fractal fue en las imágenes incluidas en la Enciclopedia Multimedia Encarta. Aunque ello ahora se aprecia más frecuentemente, y no sólo en imágenes estáticas, sino en complejas animaciones de videojuegos y también en algunas cintas de cine muy populares (especialmente de ciencia ficción).
Este proceso es en cierta forma "simple". Imagínese que tiene una fotografía o dibujo cualquiera en la pantalla de su ordenador. Como sabrá, cada imagen o fotografía se representa en la pantalla mediante pixeles o "puntos" que unidos todos y en determinados colores, forman la imagen. Pues bien. Se habla muchas veces de "resoluciones de pantallas", que son números bastante conocidos, especialmente si usted navega mucho por internet. Estas resoluciones de pantallas son la "capacidad" de pixeles que puede mostrar simultáneamente el monitor de su ordenador. Entonces, mientras más pixeles sea capaz de mostrar su PC, mayor será la "resolución de imagen" de la foto o dibujo que este observando.

Por ejemplo, una alta resolución de pixeles nos permitirá ver la primera imagen de arriba. Por el contrario, una baja resolución de pixeles nos permitirá ver una imagen como la que está debajo (que es bastante confusa e indescifrable por lo demás). Pero notemos algo importante: informáticamente, es decir, si medimos en "bytes", la primera imagen "pesa" (o contiene mayor cantidad de información) más que la segunda. He aquí la primera diferencia importante del proceso.
Como sabemos, los Fractales se forman por una "repetición" de una imagen geométrica (no es una definición rigurosa, sino una simplificación del concepto). Notaremos que, sea como sea, un pixel sigue siendo un pixel bajo cualquier circunstancia dentro del mundo de nuestro ordenador. La técnica de compresión, en este caso, es una que toma como patrón geométrico el pixel y toma esa gran cantidad de pixeles para convertirlos en uno sólo, muy especial, que va acompañado por una expresión matemática que el ordenador interpretará cuando abra la imagen para que, ese pixel especial, pueda distribuir los demás pixeles en torno a la pantalla para dar forma a la imagen.
Algunos ejemplos claros de este proceso se ven perfectamente en Internet. Si su conexión no es muy rápida (lo que suele pasar) podrá notar que en determinados browsers (los programas que se usan para navegar, como IE o Netscape) las imágenes se van cargando mediante este proceso, que nos entrega en primer plano una imagen "cuadriculada" que luego se va "barriendo" y tomando mejor definición. Ese podría ser perfectamente un ejemplo de lo que mencionamos.
Esto ha permitido incluir gran cantidad de imágenes en enciclopedias como la mencionada, que posean una gran cantidad de pixeles (o sea, de gran calidad gráfica) y que ocupen poco espacio (algo muy preciado en el mundo de la informática). Pero además, este mismo proceso ha permitido crear increíbles efectos en muchas películas de ciencia ficción y lo mismo en videojuegos de todo estilo. Las campañas cinematográficas están aplicando técnicas fractales para crear escenarios naturales. Los fractales están allí donde la imaginación apenas llega. Por ello la geometría fractal forma parte de la geometría computacional. Los ordenadores solían estar limitados a las figuras regulares y geométricas clásicas, pero los fractales han dado paso en el campo de las matemáticas a formas irregulares naturales como por ejemplo hojas, nubes y líneas costeras. Estos recursos gráficos tienen aplicación en el arte tanto como en la tecnología. El secreto parece estar en entregar una fórmula y una dosis de creatividad y que el ordenador se encargue del resto.
Por medio de programas computarizados se pueden representar fractales a fin de describir los flujos de lava, la distribución de galaxias y otros fenómenos más complejos. Es aquí donde aparecen los modelos de simulación digital tan en boga. Un modelo de simulación digital es un conjunto de instrucciones que traducido a un lenguaje computarizado permite obtener datos del comportamiento del fenómeno que se desea estudiar con el fin de predecir y a veces prevenir fenómenos que resultarían costosos o destructivos si se trataron de experimentar. Como por ejemplo: Estudiar el comportamiento de un reactor nuclear, el crecimiento poblacional de colonias de bacterias o fenómenos sociales. Estudiar problemas ambientales como factores climáticos, un tornado, el flujo turbulento de un río, incendios de bosque, etc. Estudiar aerodinámica en el diseño de aviones, autos y lanchas. Por citar algunos.
Por último quisiera decir que hay programas como el Fractint que permiten a cualquier entusiasta construir fractales a su antojo. Puede obtenerse sin costo alguno en http://spanky.triumf.ca/www/FractInt/getting.html. Un curso en español puede leerse en http://areafractal.tierradenomadas.com/fctint.html. ¡Hágalo Vd. mismo!

REFERENCIAS

[1] Benoît Mandelbrot, La Geometría Fractal de la Naturaleza, Ed. Tusquets.

[2] http://www.dmae.upm.es/cursofractales/

Una paradoja geométrica

Figura 1

Figura 2

Las pérdidas aparentes de superficie ofrecen un ejemplo de desaparición geométrica. En el primer rectángulo de la figura 1 aparecen 65 cuadrados (5 por 13). Si se recorta este rectángulo siguiendo las líneas marcadas y, con los trozos se reconstruye un cuadrado como se indica, al calcular el área de la nueva figura, es de 8 unidades por 8, es decir, hay sólo 64 cuadrados.
¿Dónde ha quedado el que falta? La aparente pérdida de superficie es debida al reajuste de los trozos. De hecho, en la última figura, los bordes no coinciden exactamente, sino que forman un pequeño paralelogramo, casi imperceptible, y no un cuadrado perfecto. Esto sería evidente si la figura fuera más grande y estuviera construida con sumo cuidado. Las sorpresas de este tipo se llaman paradojas de Hooper.
Desde un punto de vista más teórico, debe notarse que las desapariciones de superficie hacen intervenir, en muchas ocasiones, segmentos de recta cuyas longitudes forman una serie de Fibonacci, es decir, una sucesión en la que cada término es la suma de los dos precedentes:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,...

En nuestro ejemplo, las figuras tienen lados de 5, 8 y 13 unidades, formando así una serie de Fibonacci. Y una de las propiedades fundamentales de esta serie es que, si uno de los números que la constituye se eleva al cuadrado, este número será igual al producto de los dos números situados delante y detrás de él, más o menos una unidad. Así 8 x 8 = 64 y 5 x 13 = 65.
Hoy en día, el matemático y mago P. Curry ha combinado las desapariciones de línea y superficie para realizar su famosa paradoja del conejo.

Figura 3

El primer rectángulo de la figua 3, de 6 unidades sobre 3 comprende 78 casetas, cada una de las cuales contiene la silueta de un conejo. Si se corta este rectángulo según las líneas indicadas, se obtiene, una vez redispuesto un nuevo rectángulo, de 6 por 13 pero sólo con 77 conejos y una caseta vacía... ¿Dónde ha quedado el conejo que falta? Solución

Números Congruentes

Reciben este curioso nombre aquéllos que son el área de un triángulo rectángulo de lados racionales. Ya merecieron la atención de los griegos, perplejos por la forma tan imprevisible con que se presentan.
Uno de estos números se nos ocurre de forma inmediata: 6, que es el área del famoso triángulo rectángulo pitagórico, de lados (3,4,5). También son congruentes 5, que es área del triángulo de lados (3/2,20/3,41/5), y 7 de (35/12,24/5,337/60), pero no son congruentes 1, ni 2, ni 3, ni 4.
No es fácil averiguar si un número es o no congruente. Por ejemplo, 157 lo es, pero el triángulo más sencillo de esta área es:

Recordemos que los triángulos rectángulos de lados enteros vienen dados por los valores:

Siendo (m,n) parámetros enteros cualesquiera primos entre sí, uno par y el otro impar. Los múltiplos de los valores obtenidos proporcionarán más triángulos pitagóricos.
La investigación de los números congruentes está relacionada con la resolución del Gran Teorema de Fermat. Por ejemplo, la demostración de que 1 no es congruente, debida a Fermat, equivale a la imposibilidad del famoso teorema para el exponente 4. Tunnell enunció un teorema que casi equivale a una demostración. Falta para ello que fuera cierto su recíproco, y así sería si se acepta la llamada conjetura débil de Birch-Swinnerton- Dyer sobre la función de Hasse-Weil para las curvas elípticas de tipo

No exponemos este teorema por excesivamente abstruso, sólo remarcamos el hecho de que esta demostración requiera, como requirió la demostración de Wiles del Gran Teorema de Fermat, la utilización de técnicas sofisticadas, avanzados y potentes de geometría algebraica que se enmarcan dentro de la teoría aritmética de curvas elípticas.

Quien desee más detalles puede consultar el libro Horizonte científico de España, de Círculo de Lectores, donde el matemático Alberto Galindo analiza éste y otros sorprendentes temas de matemáticas.

Fractales en la naturaleza

Clip sobre los patrones fractales en la naturaleza. Gran parte del conocimiento científico que tenemos sobre los fractales se lo debemos al matemático Benoît Mandelbrot, al que Eduard Punset ha entrevistado en http://www.eduardpunset.es/charlascon...

Prest's Conference

| View | Upload your own