El efecto Mariposa

El jueves fui al cine a ver El efecto Mariposa. No esperaba que fuera nada del otro mundo, pero al final resultó ser una película buena. El argumento de la película se basa en una de las primeras consecuencias de la teoría del caos: «Un pequeño cambio en las condiciones iniciales de un sistema puede provocar grandes cambios al cabo del tiempo». La forma popular de decir lo mismo es conocido como Efecto Mariposa:

Si una mariposa agita con su aleteo el aire de Pekín, puede modificar los sistemas climáticos de Nueva York del mes que viene y provocar un huracán

El protagonista de la peli puede volver al pasado, realizar un pequeño cambio en sus actuaciones y volver al presente viendo que todo ha cambiado radicalmente. Ya no os cuento más sobre la película, id a verla 😉 ahora nos vamos a centrar en la base teórica de la película.

Efecto mariposa

En nuestra vida cotidiana estamos acostumbrados a observar intuitivamente sistemas No caóticos. Por ejemplo: si le das una patada a un balón, lo lanzas a 20m. Luego le das una patada un poco más fuerte llegará hasta los 25 m. Es decir, un pequeño cambio en las condiciones iniciales provoca un pequeño cambio en las condiciones finales. Toda la física clásica está basada en este principio, pensad en las 3 leyes de Newton por ejemplo, un pequeño cambio en una ecuación hará que tengamos un pequeño cambio en los resultados finales.

Pero también estamos acostumbrados a observar sistemas caóticos sin saberlo realmente. Por ejemplo el movimiento de las nubes donde un pequeño cambio puede provocar grandes cambios en el sistema. Veamos como se hicieron los primeros descubrimientos de sobre la existencia de sistemas caóticos, precisamente observando la atmósfera.

Hacia 1960, el meteorólogo Edward Lorenz se dedicaba a estudiar el comportamiento de la atmósfera, tratando de encontrar un modelo matemático, un conjunto de ecuaciones, que permitiera predecir a partir de variables sencillas, mediante simulaciones de ordenador, el comportamiento de grandes masas de aire, en definitiva, que permitiera hacer predicciones climatológicas.

Lorenz realizó distintas aproximaciones hasta que consiguió ajustar el modelo a la influencia de tres variables que expresan como cambian a lo largo del tiempo la velocidad y la temperatura del aire. El modelo se concretó en tres ecuaciones matemáticas, bastante simples, conocidas, hoy en día, como modelo de Lorenz.

Pero, Lorenz recibió una gran sorpresa cuando observó que pequeñas diferencias en los datos de partida (algo aparentemente tan simple como utilizar 3 ó 6 decimales) llevaban a grandes diferencias en las predicciones del modelo. De tal forma que cualquier pequeña perturbación, o error, en las condiciones iniciales del sistema puede tener una gran influencia sobre el resultado final.

Por eso es muy difícil hacer precciones del tiempo a largo plazo. Porque no podemos conocer exactamente cual es la situación actual de la atmósfera. Los datos que obtienen los satélites son aproximados, si el movimiento de las nubes no fuera caótico con una aproximación tendríamos suficiente; pero al ser un sistema caótico debemos saber la situación y estado exactos de cada masa de aire para poder hacer unas buenas predicciones.

Lorenz intentó explicar esta idea mediante un ejemplo hipotético. Sugirió que imaginásemos a un meteorólogo que hubiera conseguido hacer una predicción muy exacta del comportamiento de la atmósfera, mediante cálculos muy precisos y a partir de datos muy exactos. Podría encontrarse una predicción totalmente errónea por no haber tenido en cuenta el aleteo de una mariposa en el otro lado del planeta. Ese simple aleteo podría introducir perturbaciones en el sistema que llevaran a la predicción de una tormenta.

De aquí surgió el nombre de efecto mariposa que, desde entonces, ha dado lugar a muchas variantes y recreaciones. Por ejemplo, en las novelas de Isaac Asimov aparece muchas veces el dilema de que al viajar hacia el pasado no hay que tocar nada, ni provocar ningún cambio, porque podría tener consecuencias insospechadas en el presente. En otras novelas se considera que la teoría del caos no tiene validez en el caso de los viajes en el tiempo, ya que un pequeño cambio es algo inapreciable que sería eliminado por fuerzas mayores (Al igual que una pequeña piedra en un gran rio).

Se denomina, por tanto, «efecto mariposa a la amplificación de errores que pueden aparecer en el comportamiento de un sistema complejo. En definitiva, el efecto mariposa es una de las características del comportamiento de un sistema caótico, en el que las variables cambian de forma compleja y errática, haciendo imposible hacer predicciones más allá de un determinado punto, que recibe el nombre de horizonte de predicciones».

Para terminar, algo muy importante sobre la teoría del caos que os terminará de liar :

«El caos observa que realmente existen movimientos sin orden. Gracias a la teoría del caos, hemos comprendido que puede haber movimientos erráticos que no son aleatorios, sino que responden a reglas fijas. Sí, efectivamente son fenómenos sin orden aparente- como por ejemplo el clima planetario- cuya motivación causal puede ser incomprensible y cuyas leyes se nos escapan, pero en absoluto son fenómenos derivados del azar» – Feigenbaum

Un libro sobre el tema muy recomendado para comenzar: Caos de James Gleick, y un enlace clásico sobre el tema en castellano. Seguiremos hablando sobre el Caos en este blog, esto solo ha sido una introducción para ir calentando 😉

¿Si conociésemos la posición actual de todas las partículas de nuestro planeta, introdujéramos todos los datos en un gran ordenador junto con las leyes físicas concernientes a la interacción de las partículas seríamos capaces de predecir el futuro (Dejando aparte la mecánica cuántica , por si hay algún físico leyendo esto 🙂 )?

¿Pensáis que un pequeño cambio en algún momento de vuestra vida habría hecho que fuera totalmente diferente o pensáis que hay «fuerzas mayores» que hacen que todo fluya como debería al igual que al tirar una piedra a un rio no provoca grandes cambios?

Tened cuidado con lo que hacéis hoy, una pequeña decisión podría tener consecuencias que no podéis ni sospechar 😉

Delaunay y Voronoi

Vamos a comentar intuitivamente uno de los algoritmos más famosos y más útiles de la geometría computacional usando un ejemplo práctico. Aprenderemos a generar imágenes como esta:

Comenzamos la aventura. Imaginaros que tenemos una empresa de transporte con varias centrales de distribución, cada punto de la imágen representa uno de estos centros:

Ahora imaginaros que debemos determinar las zona que debe cubrir cada central de distribución de forma que tengamos que viajar lo mínimo posible. Es decir, debemos determinar las zonas del plano que están más cercanas a cada punto.

Para calcular estas zonas hay que seguir una serie de pasos. Primero debemos aplicar el algoritmo de Delaunay, que consiste en trazar triángulos entre los vértices con ciertas restricciones que ahora veremos. Veamos una posible triangulación:

Esta es una forma de triangular, pero para nuestro propósito no es válida. Debemos conseguir una triangulación de forma que Cualquier circunferencia trazada entre los 3 vértices de cada triángulo no tenga ningún otro punto dentro. Lo veremos más claro con una imágen que demuestra que la triangulación anterior no era válida:

¿Cómo solucionamos el problema? Pues probando diversas triangulaciones (Hay un método complicado de explicar que lo hace muy bien) hasta que no haya ninguna circunferencia que toque más de 3 vértices. En nuestro caso solo tenemos que cambiar una arista:

Fijaros que hemos cambiado un poco la triangulación y ahora al trazar la circunferencia ya no tenemos ningún otro vértice interior. Si hacemos lo mismo con el resto de triángulos vemos que hemos conseguido que no tengan otros vértices dentro, en este momento hemos conseguido la Triangulación de Delaunay a partir de los vértices/centrales de distribución iniciales. En la siguiente imagen trazamos todas las circunferencias posibles, fijaros que ninguna toca más de 3 vértices.

Pufff, un poco lioso pero lo que queda es cuesta abajo. A continuación debemos calcular las regiones más cercanas a cada punto (A estas regiones las llamaremos Regiones de Voronoi). Para ello nos apoyaremos en la Triangulación de Delaunay que ya hemos calculado. Marcamos el punto central de cada circunferencia y trazamos Perpendiculares a las aristas de los triángulos. Vamos a verlo con dos de los círculos para no liar (Los puntos amarillos son los centros de las circunferencias y las líneas naranjas son perpendiculares a las aristas de los triángulos):

Si seguimos aplicando el mismo método (y eliminamos del dibujo los circulos para no liar) obtendremos lo siguiente:

Si además eliminamos la Triangulación de Delaunay, tendremos la imagen definitiva donde se definen las zonas más cercanas a cada centro de distribución:

Por ejemplo, la zona coloreada de verde es la Región de Voronoi del punto A. Esto quiere decir que todo lo que está pintado de verde está más cerca de A que de cualquier otro punto del dibujo. Lo podéis comprobar con una regla si no os convenzo 😉

Si habéis llegado hasta aquí, tenéis premio: Un applet donde haciendo clicks podéis ir colocando las sedes de vuestra empresa y vais viendo en tiempo real la triangulación de Delaunay y las regiones de Voronoi. También podéis generar muchos puntos dándole al botón Generar, con el que conseguiréis una imagen similar a la mostrada al inicio de este artículo. A los programadores os pongo el código fuente por si quieren trastear algo, os aviso que está muy poco documentado.

Resumiendo, en geometría computacional las regiones de Voronoi son las zonas del plano más cercanas a un conjunto dado de puntos. Esto a nivel práctico lo utilizan muchas empresas para definir sus zonas de cobertura. Por ejemplo, McDonalds lo utiliza para decidir donde tiene que poner una nueva sede. También se utiliza en planes de prevención de riesgos para saber a que zonas afectaría un escape de una central nuclear.

También se utiliza en aplicaciones más artísticas, como en la primera imágen de este artículo, la creación de cristaleras etc. También podéis generar vuestras regiones de voronoi utilizando Photoshop: Filtro -> Textura ->Vidriera . Para aplicar ese filtro Photoshop internamente realizar la Triangulación de Delaunay que hemos aprendido y posteriormente calcula las Regiones de Voronoi. Todos a crear Vidrieras y si no os queda algo claro preguntad 🙂

Patentes absurdas

En esta web se muestran algunas de las patentes que un tal Paul Pedrick parió en los años 60. La mayoría de sus patentes muestran inventos absurdos e inútiles pero realmente imaginativos.

La patente que más me ha llamado la atención es la solución para eliminar el desierto Australiano. Consiste en lanzar bolas de hielo desde la Antártida para que aterricen en Australia. Aquí tenéis el esquema de funcionamiento del invento 🙂

Parece ser que Paul Pedrick tiene el honor de tener el mayor número de patentes consideradas como absurdas.

¿Cómo funciona un buscador? – Capítulo 3

En el Capítulo 1 aprendíamos las diferencias entre los diversos tipos de buscadores. En el Capítulo 2 aprendíamos como se pueden buscar cosas de forma muy rápida cuando tenemos mucha información. En este capítulo vamos ver el último paso de funcionamiento de un buscador, no por ello menos importante. Se trata de la ordenación de los resultados de una búsqueda. Para esta tarea existen cientos de algoritmos y métodos de los cuales vamos a ver una pequeña introducción intuitiva. Según la eficacia de estos métodos el usuario obtendrá una satisfacción mayor o menor. ¿Os molesta que el Google no encuentre lo que buscáis? ¿Os molesta encontrar el mejor resultado en la segunda página?

El primer método que nos viene a todos a la cabeza es el de poner antes las páginas web donde más veces aparezca la palabra que buscamos. Supongamos que buscamos «Albert Einstein», aplicamos los métodos descritos en el Capítulo 2, y solo exisen 3 páginas en Internet que contienen alguna de las dos palabras:

-Página web 1: » Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.»

-Página web 2: » Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.»

-Página web 3: «Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.»

Si aplicamos el método de contar las palabras clave y poner antes las páginas web en las que más aparezcan las palabras buscadas obtendríamos la siguiente ordenación:

-PRIMERA POSICIÓN (Las Palabras Albert y Einstein aparecen 5 veces): » Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.»

-SEGUNDA POSICIÓN (Las Palabras Albert y Einstein aparecen 4 veces):»Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.»

-TERCERA POSICIÓN (Las Palabras Albert y Einstein aparecen 3 veces): «Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.»

Fijaros que si el Google nos diera este resultado no estaríamos muy satisfechos con la primera página obtenida ya que no habla de Albert Einstein. Debemos mejorar nuestro algoritmo de ordenación de resultados. ¿Qué es mejor GENERALMENTE, una web con 50.000 palabras donde aparece Albert Einstein una vez, o una web con 50 palabras donde aparece Albert Einstein una vez? Yo creo que todos escogeríamos la segunda web. Veamos como podemos mejorar nuestro método para tener en cuenta este factor.

Además de tener en cuenta el número de apariciones de las palabras clave, vamos a contar el número de palabras de cada web. Calculamos el número de palabras de cada web y lo dividimos entre el número de apariciones de las palabras para obtener la puntuación final. Cuanto más palabras tenga la web menor será la puntuación a no ser que la palabra clave aparezca muchas veces.

-PRIMERA POSICIÓN (Número de palabras:21. Número apariciones: 3 . Puntuación: 3/21=0.14): «Albert Einstein murió en 1955. Uno de los mayores logros de Einstein fue la formulación de la teoría de la relatividad.»

-SEGUNDA POSICIÓN (Número de palabras:38. Número apariciones: 4 . Puntuación: 4/38=0.10 ):»Uno de los grandes fallos reconocidos de Einstein fue la introducción de la constante cosmológica. Aunque últimamente se está viendo que Albert Einstein no estaba tan equivocado. Albert era nunca aceptó plenamente las teorías de la mecánica cuántica.»

-TERCERA POSICIÓN (Número de palabras:53. Número apariciones: 5 . Puntuación: 5/53=0.09): » Albert es un niño muy juguetón. Siempre está dando la tabarra. Pero Albert también tiene una mente brillante con la que podría rivalizar con el mismísimo Einstein. Puede que algún día Albert nos sorprenda. Albert tiene una gran imaginación. Podríamos educarlo para que llegue a ser un genio que gane el premio Nobel.»

Fijaros que hemos conseguido que las páginas con mayor Densidad de palabras clave aparezcan primero. Seguramente hayáis notado esta característica al buscar con Google, generalmente los primeros resultados muestran webs donde las palabras que hemos buscado están muy cercanas y aparecen muchas veces.

Tened en cuenta que ésta es una pequeña descripción del método de forma intuitiva. La fórmula completa tiene en cuenta otros factores importantes, ya que según lo descrito una web que pusiera «Albert Einstein» a secas sería la ganadora. Este no es un método definitivo ni mucho menos, hay muchos algoritmos que utilizan técnicas muy avanzadas para intentar darnos los mejores resultados. Una mejora sería aplicar este método para cada frase, e ir sumando la puntuación de cada frase para obtener una puntuación final.

A este método se le pueden encontrar muchos defectos, pero por lo general funciona bastante bien. Además, debéis tener en cuenta que la ordenación de los resultados finales es algo muy subjetivo. Quizás un resultado no le sirva para nada a la persona X, pero a la persona Y le sea de mucha utilidad. Por ello Google, además de utilizar algoritmos básicos de ordenación como el que acabamos de explicar, usa también el famoso PageRank para mejorar aún más a disposición de los resultados.

PageRank asigna una puntuación a cada página según una fórmula que explicaremos en el siguiente capítulo. El valor del PageRank se utiliza junto con el valor obtenido por el Algoritmo de Ordenación «similar» al explicado en este artículo para obtener la posición final de cada web en los resultados de un búsqueda.

Wifibloging

¿Que se supone que es esto? ¿Mobloging, Wifibloging? Pues aquí estoy posteando usando la conexión wireless a 11 Mbps de la Universidad de Alicante. Es impresionante estar conectado a tal velocidad sin cables, parece que esté soñando. Esto baja a 500 KBYTES/s sin despeinarse.


Un Geek tomando el Sol mientras baja cosas de Internet a 30 MBytes por minuto


Vista panorámica del posteo. La pantalla no sale en la foto por el reflejo del Sol 🙁

Espero que en el futuro esto se pueda disfrutar fuera de las universidades.

Cosas malas del wifibloging: el Sol refleja en la pantalla, caen flores de olivos en el teclado y los patos me quieren quitar mi portátil xD