Posts etiquetados ‘acertijos’


matematica[1]

a. Secuencia 1:
Qué numero viene a continuación?

0   2   6   14   ?

b. Cálculo 1:
Usando un “1”, cuatro “7” y las cuatro operaciones básicas (+, -, x, /), obtener el número 100. Cada dígito debe ser utilizado por separado (no se pueden unir dígitos para formar una cifra mayor como 17, 77, etc.)…

Seguir leyendo

Anuncios

En la primera parte de la nota comentábamos acerca de los sistemas complejos, de los cuáles el juego de la vida es también un ejemplo.

Un tipo de sistema complejo es aquél formado por muchos agentes que están interconectados, o interactúan. El resultado es lo del título, aún aplicando reglas muy simples, se obtienen resultados increíblemente complejos.

A esta altura es imprescindible un ejemplo. Todos hemos visto largas hileras de hormigas desde un hormiguero a alguna fuente de alimento. Cómo saben las hormigas para dónde ir?

La respuesta: En forma similar a la popular leyenda de Hansel y Gretel, sólo que en lugar de dejar piedras o migas de pan, las hormigas impregan el camino a su paso con feromonas. Esto explica fácilmente como todas las hormigas siguen el mismo camino, pero, quién fue la primera hormiga en fundar la “ruta de transporte”. Dejaremos esta segunda pregunta para un poco más adelante.

Antes de seguir, un ligero desvío del tema, para volver hacia el final al tema principal de esta nota.

Los comienzos de los años 80 vieron la explosión de los primeros ordenadores personales u hogareños. En esos tiempos, el software escaseaba y no era raro que el usuario se programara sus propias aplicaciones y juegos. Hubo muchos lenguajes de programación, y sobrevivieron los más aptos, por diversas razones, popularidad, precio, prestaciones o simple azar.

Por aquellos años, existía también un lenguaje pensado especialmente para la educación de infantes. La idea era conectar lo virtual con lo real. Los comandos que los niños introducían en sus programas debían controlar robots reales, que realizaran sobre el piso lo que sus amitos les ordenaban.

Esa era la idea original del Logo, lenguaje creado por Papert y  basado en el Lisp, y el robot era conocido popularmente como “tortuga”. La idea original era que tal tortuga tuviera un o varios lápices de colores, y los programas de los peques generaran dibujos en el piso.

Como era de esperarse, no fueron demasiados los lugares que pudieron permitirse o mantener una tortuga de piel y hueso, o mejor dicho de plástico y acero, para cumplir con la visión original de los diseñadores. La tortuga era generalmente también un simpático icono en la pantalla, encargado de dibujar los caprichos de los alumnos.

El Logo tuvo su época de gloria pero casi desapareció. Mientras pensaba en cómo dar ejemplos (como lo hicimos en el juego de la vida) sobre simulaciones de sistemas complejos, me encontré con una reencarnación del Logo, llamada StarLogo TNG*. Es un Logo creado por el MIT para instituciones educativas. La versión TNG incluye gráficos tridimensionales.

En próximas entregas comentaremos muchos problemas interesantes que pueden ser planteados y analizados en esta versión del Logo que dista mucho de ser un programito para infantes. En principio el programa viene también en castellano pero NO LO RECOMIENDO (lamentablemente) ya que tal versión en castellano no funciona bien.

La versión en inglés es bastante estable y desde ya que la recomiendo, la pueden ir bajando y probando los tutoriales y ejemplos que abundan para este paquete de Logo del MIT.

Por eso, esta nota es un final y un comienzo. Si Dios quiere, un comienzo de muchos ejemplos de sistemas complejos que iremos analizando con la ayuda del StarLogo TNG. Para la descarga, ir a la página del Star Logo TNG.

* TNG = The next generation. La nueva generación. Una sigla que fue popularizada, creo, por la serie Star Trek, Viaje a las Estrellas.


Si queremos comprender el funcionamiento de un sistema, a veces es recomendable analizar sus componentes.

Por ejemplo, si queremos saber cómo funciona nuestra computadora, es muy probable que los primeros pasos consistan en aprender sobre sus bloques básicos: el microprocesador, la memoria, los dispositivos de almacenamiento a largo plazo (tales como el disco duro), los dispositivos de entrada y salida (mouse, teclado, pantalla), los dispositivos de comunicaciones (conexión a la Internet), etc.

Pero hay sistemas que no admiten tal reduccionismo. Uno de los ejemplos más conocidos son los llamados sistemas caóticos. El ejemplo mostrado en el video a continuación es un sistema simétrico de imanes, sobre los que oscila un péndulo magnético. Los movimientos del péndulo, a pesar de ser la configuración simétrica, son sumamente  erráticos. La posición final del péndulo es impredecible.

Esta otra simulación por computadora muestra los movimientos de un péndulo doble, y nuevamente, a pesar de ser el sistema sumamente simple, los resultados son sumamente complejos (y para mí, interesantes por su belleza):

Un famoso proverbio chino dice:  “el aleteo de las alas de una mariposa se puede sentir al otro lado del mundo” . La meteorología se enfrenta, justamente, con este tipo de comportamiento denominado caótico. Un pequeño cambio en las condiciones en un lugar determinado pueden provocar una respuesta enorme y absolutamente impredecible en otro punto. Popularmente denominado efecto mariposa, los libros y las películas han jugado con este comportamiento real y su influencia en el espacio, y en el tiempo. En un conocido cuento de Ray Bradbury, “El ruido del trueno“, se analiza cómo un pequeño cambio en el pasado tiene una enorme influencia en un presente alternativo. Este cuento inspiró a la película homónima, del año 2005.

En los sistemas caóticos, un pequeño cambio en las condiciones iniciales (desde dónde suelto el péndulo magnético, o la muerte de una mariposa en el remoto pasado) tiene efectos enormes en el comportamiento y el estado final del sistema.

Hay otro tipo de sistemas complejos. Son sistemas formados por multitud de agentes que interactúan entre sí, sin que exista una dirección central que coordine a todos los agentes (o con una dirección central que fija determinadas condiciones iniciales, o líneas generales de comportamiento, pero no dirige cada acción del sistema).  El comportamiento de los agentes puede obedecer a reglas muy simples, pero en algunos casos, los resultados son sumamente interesantes.

Ejemplos y resultados de estos sistemas complejos son, los nidos de hormigas, las bandadas de pájaros, las redes de computadoras y las redes sociales.

El juego de la vida de Conway es otro ejemplo de sistemas complejos, y mientras buscaba más ejemplos para demostrar ésto me encontré con una perlita, de la que contaré en un próximo aporte.

Ver la segunda parte


Extractado de Wikipedia, contiene ejemplos del juego agregados por Locaciencia

Una de las consecuencias de la accesibilidad de las computadoras es la creación de simulaciones. Las simulaciones pueden ser desde una simple recreación, hasta una poderosa herramienta para comprender nuestro Universo. Una de las razones por las cuales se construyen supercomputadoras cada vez más potentes, es su capacidad de simulación de sistemas climáticos, reacciones nucleares, simulaciones moleculares, etc.

Una de las primeras simulaciones en aparecer en el mundo de la computación es el  juego de la Vida de Conway.

El juego de la vida es el mejor ejemplo de un autómata celular, diseñado por el matemático británico John Horton Conway en 1970.

Hizo su primera aparición pública en el número de octubre de 1970 de la revista Scientific American, en la columna de juegos matemáticos de Martin Gardner. Desde un punto de vista teórico, es interesante porque es equivalente a una máquina universal de Turing, es decir, todo lo que se puede computar algorítmicamente se puede computar en el juego de la vida.

Desde su publicación, ha atraído mucho interés debido a la gran variabilidad de la evolución de los patrones. Se considera que la vida es un buen ejemplo de emergencia y autoorganización. Es interesante para los científicos, matemáticos, economistas y otros observar cómo patrones complejos pueden provenir de la implementación de reglas muy sencillas.

El juego de la vida es en realidad un juego de cero jugadores, lo que quiere decir que su evolución está determinada por el estado inicial y no necesita ninguna entrada de datos posterior. El “tablero de juego” es una malla formada por cuadrados (“células”) que se extiende por el infinito en todas las direcciones. Cada célula tiene 8 células vecinas, que son las que están próximas a ella, incluso en las diagonales. Las células tienen dos estados: están “vivas” o “muertas” (o “encendidas” y “apagadas”). El estado de la malla evoluciona a lo largo de unidades de tiempo discretas (se podría decir que por turnos). El estado de todas las células se tiene en cuenta para calcular el estado de las mismas al turno siguiente. Todas las células se actualizan simultáneamente.

Las transiciones dependen del número de células vecinas vivas:

  • Una célula muerta con exactamente 3 células vecinas vivas “nace” (al turno siguiente estará viva).
  • Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por “soledad” o “superpoblación”).
<<< TEMAS RELACIONADOS >>>
El juego de la vida de Conway – Nuevos Desafíos
Acertijo de los cuatro sombreros
Trepando las dimensiones

Ejemplos de patrones

Existen numerosos tipos de patrones que pueden tener lugar en el juego de la vida, como patrones estáticos (“vidas estáticas“, en inglés still lifes), patrones recurrentes (“osciladores“, oscillators, un conjunto de vidas estáticas) y patrones que se trasladan por el tablero (“naves espaciales“, spaceships). Los ejemplos más simples de estas tres clases de patrones se muestran abajo. Las células vivas se muestran en negro y las muertas en blanco.

Patrones estáticos
Bloque Game of life block with border.svg
Colmena Game of life beehive.svg
Pan Game of life loaf.svg
Bote Game of life boat.svg
Oscilladores
Guiño(con período 2) Game of life blinker.gif
Sapo(con período 2) Game of life toad.gif
Faro(con período 2) Game of life beacon.gif
Pulsar(con período 3) Game of life pulsar.gif
Naves Espaciales
Planeador Game of life animated glider.gif
Nave espacial ligera Game of life animated LWSS.gif

Programas para el Juego de la Vida

Se encuentran disponibles muchísimos programas, tanto en línea como disponibles para ser bajados, que corren el Juego de la Vida con sus reglas originales y variaciones. Para más datos, se recomienda consultar los links de Wikipedia, en español y en inglés:

http://es.wikipedia.org/wiki/Juego_de_la_vida

http://en.wikipedia.org/wiki/Conway’s_Game_of_Life

Ejemplos de Locaciencia

De entre los programas disponibles utilicé éste:

http://www.granvino.com/jam/stuff/juegos/gamoliyas/spanish/index.htm

Una de las ventajas de este programa es su sencillez. Además, está en español, informa la población de la simulación y si ha entrado en un estado estable, y permite guardar y cargar tableros. A continuación varios tableros que hice en el programa (Al cliquear en la entrada se abrirá la simulación, lista para correr, en una ventana nueva):

Planeador

Pulsar

Nave espacial

Choque de naves espaciales

Transbordador (es interesante analizar qué función cumplen los bloques cuadrados en los dos extremos)

Pistola de planeadores (atención a ésta, que es muy interesante!, y que está basada en dos transbordadores en colisión)

A partir de estos ejemplos, quedan incontables desafíos para el lector: Encontrar osciladores distintos de aquellos mostrados, o con períodos más largos, patrones de continua expansión, explorar choques entre naves y planeadores, o entre naves y patrones estáticos, etc.

Como otra alternativa para explorar el Juego de la Vida, se puede jugar una simulación de guerra, donde comandamos una facción, la computadora es el enemigo, y el objetivo, obviamente, es conquistar el tablero.

El juego se encuentra disponible en:

http://www.ctrl-alt-dev.nl/Projects/LifeAsWar/LifeAsWar.html

En la página podrán ver también un video en youtube que contiene un corto tutorial con la estrategia para ganar el juego.

Si te gustaron los contenidos de Locaciencia, vení a visitar mi otra página: “La Botica de Claudio


Al parecer los abejorros saben resolver el problema del viajante. Una tarea difícil que en computación se cataloga como problema NP.

Foto
Aunque hay muchos algoritmos que encuentran una buena aproximación al problema del viajante, no existe ninguno que sea eficiente y que a la vez dé la mejor solución posible. La única manera de encontrar la mejor solución consiste básicamente en enumerar todas las posibilidades y escoger la mejor (la ruta más corta), algo sumamente ineficiente. Se sospecha que algunos de estos problemas, como el del viajante, nunca tendrán una solución eficiente, al ser problemas de tipo NP o NP completos.El problema del viajante consiste en salir de la sede de la empresa y volver a la misma visitando todas las ciudades una sola vez por el camino más corto posible. Matemáticamente se trata de encontrar un ciclo hamiltoniano sobre un grafo en el que los vértices del grafo representan ciudades unidas por aristas (las carreteras) con un peso dado (los kilómetros o el gasto en combustible del tramo en cuestión). Básicamente, para este problema no hay un algoritmo que lo resuelva de manera eficiente y se cree que no existe. Aquí se entiende por “eficiente” el que sea resoluble en un tiempo polinómico. Es decir, que el tiempo de resolución en relación al tamaño del problema (en nuestro caso al número de vértices del grafo que representa las ciudades unidas por carreteras) crezca polinómicamente y no exponencialmente.

Obviamente para unas pocas ciudades unidas por unas pocas carreteras es relativamente sencillo resolverlo a la fuerza bruta, incluso con sólo un lápiz y un papel. Pero si son muchas le lleva a un ordenador mucho tiempo resolver el problema.
Lo que buscamos con la resolución del problema del viajante es encontrar la ruta que cumple con nuestros objetivos con el menor gasto de energía y tiempo. Pero esto es precisamente lo que tienen que hacer algunos animales. Un abejorro, por ejemplo, necesita recolectar polen y néctar en diversas flores y de cómo lo haga dependerá su eficacia y, por tanto, su supervivencia. Esto debe de crear una presión de selección que haya hecho que los abejorros hayan evolucionado con el tiempo para que ser más eficientes y que inconscientemente recorran el menor camino posible.
Esto es lo debieron pensar científicos de varias instituciones británicas cuando se pusieron a investigar la optimización de los vuelos del abejorro en su tarea de recolectar néctar. Descubrieron que los abejorros resuelven el problema del viajante, siendo el primer ejemplo de este tipo en el reino animal. Y todo con un cerebro diminuto.
El equipo de investigadores usó flores artificiales controladas computacionalmente para ver si estos animalillos seguían una ruta marcada con anterioridad o si descubrían con la nueva disposición la ruta más corta. Después de explorar la nueva localización de las flores, los abejorros rápidamente aprendieron a encontrar el camino más corto, es decir, la solución del problema del viajante para esa configuración. Es de suponer que hagan lo mismo en el campo.

Según Nigel Raine, las “abejas” resuelven el problema del viajante todos los días. Visitan flores en múltiples lugares y como usan mucha energía en el vuelo necesitan optimizar la ruta para mantener el camino que vuelan al mínimo.
Comprender cómo los abejorros efectúan este tipo de cálculo puede que nos ayude a diseñar sistemas o algoritmos (quizás basados en redes neuronales), más eficientes y que necesiten escasos recursos, pues el cerebro de los abejorros es muy pequeño. Podrían usarse, por ejemplo, en el control del tráfico y en la regulación de semáforos.
Raine dice que “a pesar de sus pequeños cerebros las abejas son capaces de proezas extraordinarias. Necesitamos comprender cómo resuelven el problema del viajante sin la ayuda de un ordenador. ¿Qué tipo de atajos usan? ”
En el mundo de la computación ya se habían utilizado algoritmos inspirados en animales (en concreto en las hormigas) para resolver el problema del viajante, pero este caso constituye el primer caso real en la Naturaleza.

Fuente: http://neofronteras.com/?p=3281