PDF de programación - Divertimentos Informáticos

Divertimentos Informáticos

Informática recreativa para programadores inquietos

Alberto García Serrano <alberto.garcia AT agserrano.com>

by

This work is licensed under the Creative Commons Attribution-
NonCommercial-NoDerivs 3.0 Unported License. To view a copy of
this license, visit http://creativecommons.org/licenses/by-nc-
nd/3.0/.

Divertimentos Informáticos

Contenido

Introducción.................................................................4

1. Razonando como un niño..............................................5

2. El juego de la vida.....................................................20

3. Caos infinito............................................................24

4. Tráfico, cervezas y autómatas celulares ..........................33

5. Secretos inconfesables ...............................................39

6. Atrapado en las redes de Dijkstra ..................................48

7. La máquina invencible ...............................................59

8. La máquina invencible II .............................................70

9. ¿Sueñan los ordenadores con imitar a Cervantes? ...............82

10. La leyenda de los “predictores” perfectos ......................90

11. La máquina predictora de estados de ánimo ..................101

12. De la cola del cine a la danza estelar ..........................111

13. ¿Cuántas palabras caben en una imagen? ......................120

14. Naturaleza matemática ...........................................131

15. Secretos compartidos .............................................138

16. Comerciales viajeros y colinas peligrosas ......................146

Alberto García Serrano

3

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

Introducción

C

uando comencé a escribir el blog Divertimentos informáticos
(http://divertimentosinformaticos.blogspot.com.es/) lo hice por una
necesidad propia de explorar y descubrir los entresijos tras la ciencia de la
computación, y poco a poco se transformó en una aventura apasionante.
Quizás buscaba volver a revivir la curiosidad que A.K. Dewdney me hizo
sentir en mi juventud explorando sus “mundos del ordenador” en el libro
“Aventuras Informáticas”.

Mi intención no es, ni ha sido nunca, tratar de transmitir un
conocimiento, que por otra lado, está recogido y bien documentado en
multitud de libros. Más bien tratar de despertar la curiosidad y quitar hierro
a temas de por sí bastante complejos. Lo que los ingleses llaman romper la
superficie (break the surface).

Cada capítulo se corresponde con un post del blog, en el que se
presenta un tema relacionado con la computación y el mundo de los
ordenadores. Temas como Inteligencia Artificial, Criptografía, Algoritmia,
etc. Los temas son tratados de forma accesible y lo más amena posible, en
forma de diálogos entre personajes imaginarios.

Animado por la propuesta de algunos lectores de reunir los artículos
en un sólo libro, me he decidido a crear este recopilatorio. Espero que lo
disfrutes.

!

Importante: El contenido de este libro está libremente disponible en
http://divertimentosinformaticos.blogspot.com.es.

Alberto García Serrano

4

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

1. Razonando como un niño

A

cababa de llegar a la oficina, y ahí estaba el señor Lego sentado en la
mesa de al lado. A pesar de ser mi compañero de trabajo (es
programador como yo) nos hablamos de usted y yo siempre lo llamo señor
Lego (su nombre real es Pascal Lego). Estaba ensimismado tratando de
resolver un rompecabezas para niños pequeños. Un rompecabezas lineal de
unas cuatro piezas grandes.

¿Difícil señor Lego? - Dije irónicamente.

Mucho, me respondió. Anoche estaba enseñando a mi hijo como resolver
operaciones matemáticas con el ordenador, y de pronto me espetó - "Este
ordenador es tonto, ni siquiera es capaz de resolver mi rompecabezas" - Y
aquí ando, viendo como podría hacer un programa para demostrar a mi hijo
que el ordenador si puede resolverlo. Quizás tu puedas echarme una mano.
La verdad es que tenía bastante trabajo acumulado, pero uno no es de
piedra y siempre está dispuesto a enfrentarse a nuevos desafíos.

Alberto García Serrano

5

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

Esta bien, señor Lego. Primero hay que buscar una forma de representar el
rompecabezas en el ordenador. Le propongo la siguiente representación:
A cada pieza le asignaremos un número, y la representaremos en una lista o
array de enteros. Consideraremos que dos piezas encajan si con
consecutivas y están ordenadas de menor a mayor. Por ejemplo [1234]
representaría el rompecabezas bien ordenado y en el que encajan todas las
piezas. Si estuvieran así [2134] significaría que las dos primeras piezas no

encajan (están bailadas) pero las dos últimas si encajan.

Sí, me parece bien -dijo el señor Lego con poca convicción.

Ahora tenemos que definir qué acciones vamos a poder realizar sobre sobre
las piezas. Si le parece, podemos definir estas:


D - Intercambiar las dos piezas de la derecha.

C - Intercambiar las dos piezas centrales.

I - Intercambiar las dos piezas de la izquierda.

De forma que si aplicamos la operación D a [2134] obtendríamos [1234].

Ya veo -dijo el señor Lego - entonces se trata de ir intercambiando piezas
contiguas hasta conseguir que el rompecabezas esté ordenado.

Eso es -respondí. Ahora nos falta decidir qué estrategia seguimos para ir
intercambiando las piezas. Si usted o yo quisiéramos ordenar las piezas

Alberto García Serrano

6

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

seguiríamos una serie de procesos mentales bastante complejos, pero el
ordenador, afortunadamente, no es tan inteligente como nosotros. Si fueras
tan tonto como un ordenador, ¿qué estrategia seguirías?


El señor Lego se quedó mirándome sin saber si yo esperaba realmente una
respuesta o era una pregunta retórica que estaba a punto de contestar yo
mismo.

Pues probaría cambios a ciegas hasta que finalmente obtuviera el
rompecabezas ordenado.

Muy bien, señor Lego. Me parece una buena estrategia -contesté como si
fuera un locutor de radio que acaba de dar un premio a un oyente.
Para entendernos, en lo sucesivo, llamaremos estado a como queda el
rompecabezas tras cada intercambio. Por lo tanto, partiremos de un estado
inicial, que es como se encuentra el rompecabezas antes de empezar.
Además iremos haciendo los cambios de forma sistemática para no dejarnos
ninguno atrás. Lo mejor es verlo como un árbol donde se despliegan todas
las posibilidades (estados). Cogí un bolígrafo e hice el siguiente esquema.

Alberto García Serrano

7

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

Fíjese señor Lego, He puesto arriba el estado inicial, y para generar los
siguientes estados aplico las tres operaciones que hemos definido antes (D,
C e I). Indico las operaciones aplicadas en cada caso en las flechitas para
que quede más claro. Esto es lo que llamaremos expandir un estado. Si
comprobamos que no hemos obtenido una ordenación correcta (a la que
llamaremos nodo solución) repetimos el procedimiento expandiendo cada
uno de los tres nuevos nodos que se han generado (a los que llamaremos
nodos hijos).

En rojo he marcado un posible camino que nos ofrece una solución.
Pero, puede haber varios caminos que lleven a la solución del rompecabezas
¿no? -dijo el señor Lego.

Efectivamente, pero por ahora, nos bastará con cualquiera de las
soluciones.

El Sr. Lego me miró desafiante y dijo: ¡Voy a probar a implemetarlo!
Mientras salía corriendo a sentarse en su ordenador.

Pasó un buen rato, y cuando suponía que ya lo había dejado por imposible y
que se estaría dedicando a mirar páginas en Internet, se levantó con unos
listados en Python y me los soltó encima del teclado.

Reproduzco aquí ambos listados.

Alberto García Serrano

8

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

Arbol.py

1. class Hoja:
2. def __init__(self, datos, hijos=None):
3. self.datos = datos
4. self.hijos = None
5. self.padre = None
6. self.set_hijos(hijos)
7.
8. def __str__(self):
9. return str(self.datos)
10.
11. def set_hijos(self, hijos):
12. self.hijos=hijos
13. if self.hijos != None:
14. for h in self.hijos:
15. h.padre = self
16.
17. def get_hijos(self):
18. return self.hijos
19.
20. def set_datos(self, datos):
21. self.datos = datos
22.
23. def get_datos(self):
24. return self.datos

backtracking_i.py

from arbol import Hoja

1.
2.
3. def buscar_solucion():
4.
5. global solucionado
6. global estado_inicial
7. global solucion
8. global hojas_expandidas
9. global hojas_no_expandidas
10. global nodo_solucion
11.
12. while (not solucionado) and len(hojas_no_expandidas)!=0:
13. nodo=hojas_no_expandidas[0]
14. hojas_expandidas.append(hojas_no_expandidas.pop(0))
15. if nodo.get_datos() == solucion:
16. solucionado=True
17. nodo_solucion = nodo
18. else:
19. # expandir nodos sucesores
20. dato_nodo = nodo.get_datos()

Alberto García Serrano

9

http://divertimentosinformaticos.blogspot.com

Divertimentos Informáticos

21.
22. # movimiento izquierdo
23. hijo_izquierdo = Hoja([d