Volver arriba
Agosto de 2013
Calendario de artículos de de 2013
2013-08-31
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Seguimos construyendo funciones para hacer una biblioteca de
autómatas celulares razonablemente general y práctica. Hoy vamos a
crear funciones para trabajar con autómatas elementales. Ya estamos a
punto de generalizar aquel
trabajito que hicimos sobre la regla 90. Un autómata celular
elemental es unidimensional (extendido de izquierda a derecha, por
ejemplo), sus celdas solamente tienen dos estados (0 y 1, digamos) y
sus vecindarios consisten en la celda inmdiatamente a la izquierda, la
propia celda y la celda inmediatamente a la derecha. Las normas
quedan escritas de forma muy compacta mediante lo que se conoce como
la notación de Wolfram. Parece que lo único que tenemos que preparar
es la extracción de los vecindarios (algo fácil gracias a la función
cyclic-cartesian- que creamos en el
anterior artículo) y la generación de normas (también fácil
gracias a la función deterministic-rule que creamos hace
unos pocos artículos). Antes de hacer eso, con el fin de
facilitarnos nun poco la vida, prepararemos unas pocas funciones
auxiliares más.
Función de repetición
En Python 2, podemos construir cómodamente una lista de tamaño
n cuyos elementos son todos un cierto objeto o
de la siguiente manera:
n * [o]
Scheme R5RS no tiene el equivalente a esto, pero nos convendrá
disponer de ello. Podemos improvisarlo de varias maneras; aquí
haremos uso de nuestra función unfold para crear una
función repeat que acepta un objeto object y el
número times de veces que aparecerá repetido en una lista:
(define (repeat object times)
(unfold (lambda (n) (< n 1))
(lambda (n) object)
(lambda (n) (- n 1))
times))
Paso de entero a lista de bits
Resulta que la operación de extracción de bits es similar a la
operación de paso de índices planos a índices multidimensionales
en un espacio en el que todas las dimensiones tienen tamaño 2 y el
número de dimensiones es igual al número de bits. En general, la
extracción de dígitos es igual que el paso de índices planos a índices
multidimensionales en un espacio en el que todas las dimensiones
tienen como tamaño la base y el número de dimensiones es igual al
número de dígitos a extraer. Podemos definir una función de
extracción de dígitos general integer->digits que acepta un
número number, una base base y el número de
dígitos a extraer number-of-digits; y devuelve la lista de
dígitos:
(define (integer->digits number base number-of-digits)
(flat->multidimensional (repeat base number-of-digits) number))
La extracción de bits es un caso particular:
(define (integer->bits number number-of-bits)
(integer->digits number 2 number-of-bits))
El número de dígitos a extraer es algo importante porque los ceros
a la izquierda sí son significativos en la especificación de las
normas de nuestros autómatas elementales.
El código anterior de Scheme tiene una traducción inmediata a
Python:
def integer_to_digits(number, base, number_of_digits):
return flat_to_multidimensional(number_of_digits * [base], number)
def integer_to_bits(number, number_of_bits):
return integer_to_digits(number, 2, number_of_bits)
Paso de lista de bits a entero
La operación inversa a la anterior puede ser útil. Es análoga al
paso de índices multidimensionales a índices planos. Definimos la
función digits->integer que funciona a la inversa de
integer->digits, pero no necesita que le pasemos el número
de dígitos:
(define (digits->integer digits base)
(multidimensional->flat (repeat base (length digits))
digits))
Como antes, el paso de bits a entero bits->integer es
una particularización:
(define (bits->integer bits)
(digits->integer bits 2))
La versión en Python de todo esto es similar:
def digits_to_integer(digits, base):
return multidimensional_to_flat(len(digits) * [base],
digits)
def bits_to_integer(bits):
return digits_to_integer(bits, 2)
Extracción de vecindarios
Vamos a construir la función extractora de vecindarios. Nuestros
vecindarios contendrán la celda situada a la izquierda, la celda
actual y la celda situada a la derecha. Esto es muy fácil de
conseguir gracias a la función
cyclic-cartesian-neighbourhoods que creamos en el
anterior artículo:
(define (cyclic-elementary-neighbourhoods cells)
(cyclic-cartesian-neighbourhoods cells
(list (length cells))
'((-1) (0) (1))))
Es igual en Python:
def cyclic_elementary_neighbourhoods(cells):
return cyclic_cartesian_neighbourhoods(cells,
[len(cells)],
[[-1], [0], [1]])
Los parámetros de la función
cyclic-cartesian-neighbourhoods son un poco engorrosos de
pasar cuando trabajamos con autómatas unidimensionales: la dimensión
va en una lista y cada posición relativa de los vecinos también va en
una lista. Es así como hicimos la función y hay que quererla igual,
pero este aspecto es mejorable con poco esfuerzo.
La función cyclic-elementary-neighbourhoods acepta como
argumento una lista de celdas cells y devuelve los
vecindarios de autómatas elementales correspondientes con la
restricción de que se supone que el autómata se repite periódicamente
y la lista de celdas contiene un periodo.
Generación de normas
El código de Wolfram establece una forma muy compacta para
describir reglas de autómatas celulares elementales. Cada norma está
caracterizada por un número entero entre 0 y 255. Si asociamos cada
uno de los 8 posibles estados de los vecindarios elementales de una
celda (dispuestos en un determinado orden que veremos más adelante)
con los bits de la expansión binaria de 8 bits del número de norma,
nos sale una tabla de correspondencias entre el estado del vecindario
y el próximo estado de la celda, es decir, la descripción de una norma
determinista. Podemos crear las normas de esta manera:
- Convertimos el número de norma en su expansión binaria de 8 bits.
Esto podemos hacerlo con integer->bits.
- Creamos una lista de 8 los posibles estados de los vecindarios
elementales:
((1 1 1) (1 1 0) (1 0 1) (1 0 0) (0 1 1) (0 1 0) (0 0 1) (0 0 0)).
Son las expansiones binarias de 3 dígitos de los números del 7 al
0, con lo que podemos generarlas aplicando integer->bits
sobre un rango generado con range.
Creamos una tabla en la que cada uno de los posibles 8 estados
de los vecinos está asociada con el bit correspondiente de la
expansión binaria del número de norma. Esto podemos hacerlo con
zip (o con zip sobre dict en Python).
Creamos la función norma mediante deterministic-rule.
Todo esto queda plasmado en el siguiente código de Scheme:
(define (wolfram-rule rule-number)
(define patterns (map (lambda (integer) (integer->bits integer 3))
(reverse (range 0 8 1))))
(define states (integer->bits rule-number 8))
(define table (zip patterns states))
(deterministic-rule table))
La versión en Python es igual.
def wolfram_rule(rule_number):
patterns = map(lambda integer: tuple(integer_to_bits(integer, 3)),
range(0, 8, 1)[::-1])
states = integer_to_bits(rule_number, 8)
table = dict(zip(patterns, states))
return deterministic_rule(table)
Esta función acepta un número de regla rule-number y
devuelve la regla correspondiente según el código de Wolfram.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/31/jugando-con-automatas-celulares-9/
Volver arriba
2013-08-29
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Seguimos construyendo funciones para hacer una biblioteca de
autómatas celulares razonablemente general y práctica. Nuestros
autómatas celulares pueden tener topologías muy diversas, pero una de
las más comunes es la de una malla cartesiana que a menudo es toroidal
o cíclica: al avanzar en una de las direcciones coordenadas, la malla
se repite periódicamente. Las funciones que hemos preparado para el
trabajo general funcionan con listas planas, pero aprovechamos el
último artículo para crear unas funciones que nos permiten pasar
de índices planos a los índices multidimensionales correspondientes y
también en el sentido opuesto. Hoy vamos a aprovechar estas funciones
para crear otras con las que extraer los vecindarios de las celdas,
que es algo fundamental para el funcionamiento de nuestros autómatas
celulares.
Aritmética de índices
Necesitamos una función para sumar índices multidimensionales.
Esta función es útil para obtener el vecindario de una celda. Nos
interesa trabajar en una topología toroidal o cíclica: si un índice
sobrepasa su límite por un extremo, vuelve por el extremo opuesto.
Esto lo hacemos con aritmética modular. La siguiente función,
cyclic-addition, hace el trabajo:
(define (cyclic-addition sizes indices1 indices2)
(map (lambda (size index1 index2)
(modulo (+ index1 index2) size))
sizes indices1 indices2))
La función admite como parámetros una lista sizes con
los tamaños de las diferentes dimensiones, una lista
indices1 con los índices que son el primer sumando y una
lista indices2 con los índices que son el segundo sumando.
El resultado es una lista con el conjunto de índices suma módulo cada
dimension del primer conjunto de índices y el segundo conjunto de
índices. El código en Python es similar:
def cyclic_addition(sizes, indices1, indices2):
def add_one_index(size, index1, index2):
return (index1 + index2) % size
return tuple(map(add_one_index, sizes, indices1, indices2)))
Acceso a las celdas mediante índices multidimensionales
Almacenamos los conjuntos de celdas en listas planas, pero
necesitamos acceder a celdas específicas mediante sus correspondientes
índices multidimensionales. Podemos hacer esto fácilmente porque ya
preparamos una función llamada multidimensional->flat que
convierte un conjunto de índices multidimensionales a un índice plano.
Ahora vamos a crear una función llamada matrix-ref que
acepta una lista plana matrix, una lista sizes
de tamaños de dimensiones y una lista indices de índices
multidimensionales y devuelve el elemento de la lista plana
matrix correspondiente a los índices especificados. Esta
función es así:
(define (matrix-ref matrix sizes indices)
(list-ref matrix
(multidimensional->flat sizes indices)))
En Scheme, estamos guardando los conjuntos de celdas en listas
simplemente enlazadas. Algo malo que tiene esto es que el coste del
acceso aleatorio es lineal. Si esto se convierte en un problema,
podemos pasar a trabajar con vectores y usar vector-ref en
vez de list-ref.
Tras el código de Scheme, toca el código de Python. En este caso,
no nos preocupamos del tipo de estructura de datos. El código es así:
def matrix_ref(matrix, sizes, indices):
flat_index = multidimensional_to_flat(sizes, indices)
return matrix[flat_index]
Extracción de los vecindarios
Llega la hora de crear una función para extraer vecindarios en
mallas cartesianas cíclicas. La función se llamara
cyclic-cartesian-neighbourhoods y aceptará una lista de
celdas cells, una lista de tamaños de las distintas
dimensiones sizes y una especificación de las posiciones
relativas de los vecinos offsets. Este último parámetro
nos da una forma muy compacta de especificar cómo son los vecindarios:
se trata de una lista cuyos elementos son a su vez listas con los
índices relativos al actual de los vecinos; por ejemplo, en un
autómata bidimensional en que el primer índice va según el eje
arriba-abajo (índices pequeños arriba, índices grandes abajo) y el
segúndo índice va según el eje izquierda-derecha (índices pequeños a
la izquierda, índices grandes a la derecha), la especificación
((-1 0) (1 0) (0 1) (-1 0)) daría como vecindario la
celda de arriba, la de abajo, la de la derecha y la de la izquierda.
Todo esto lo logramos con el siguiente código de Scheme:
(define (cyclic-cartesian-neighbourhoods cells sizes offsets)
(define (neighbour indices offset)
(matrix-ref cells sizes (cyclic-addition sizes indices offset)))
(define (neighbourhood indices)
(map (lambda (offset) (neighbour indices offset))
offsets))
(define indices
(map (lambda (flat-index) (flat->multidimensional sizes flat-index))
(range 0 (length cells) 1)))
(map neighbourhood indices))
Si este código es lento, la optimización más evidente consiste en
hacer que matrix-ref trabaje con vectores y hacer una
transformación list->vector para disfrutar de un tiempo de
acceso mucho más rápido.
Digamos que tenemos una lista de celdas
(11 12 13 21 22 23 31 32 33) con topología bidimensional
de dimensiones (3 3). Si queremos obtener la celda de la
misma columna y la fila inmediatamente superior y la celda de la misma
fila y la columna inmediatamente a la derecha, hacemos lo siguiente:
(cyclic-cartesian-neighbourhoods '(11 12 13 21 22 23 31 32 33)
'(3 3)
'((-1 0) (0 1)))
El resultado es el que sigue:
((31 12) (32 13) (33 11) (11 22) (12 23) (13 21) (21 32) (22 33) (23 31))
Tras el código de Scheme, toca el de Python, que es muy similar:
def cyclic_cartesian_neighbourhoods(cells, sizes, offsets):
def neighbour(indices, offset):
return matrix_ref(cells,
sizes,
cyclic_addition(sizes,
indices,
offset))
def neighbourhood(indices):
return map(lambda offset: neighbour(indices, offset),
offsets)
indices = map(lambda index: flat_to_multidimensional(sizes, index),
range(0, len(cells), 1))
return map(neighbourhood, indices)
Gracias a todo lo que hemos preparado hasta ahora, la función que
extrae vecindarios es muy cortita. El trabajo que hay detrás es algo
mayor que el que habríamos tenido que hacer si nos hubiéramos
conformado con hacer únicamente una función de extracción de
vecindarios llena de bucles explícitos, pero a cambio hemos conseguido
unas herramientas muy generales que podemos usar para otros fines.
Todo este código no es muy pythónico, eso sí; al fin y al cabo,
el diseño original está hecho en Scheme y la versión en Python es más
o menos una transcripción directa, así que el resultado es más bien
schémico y algo incómodo en Python.
Tenemos casi todo listo para empezar a trabajar.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/29/jugando-con-automatas-celulares-8/
Volver arriba
2013-08-27
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Seguimos construyendo funciones para hacer una biblioteca de
autómatas celulares razonablemente general y práctica. Nuestros
autómatas celulares pueden tener topologías muy diversas, pero una de
las más comunes es la de una malla cartesiana que a menudo es toroidal
o cíclica: al avanzar en una de las direcciones coordenadas, la malla
se repite periódicamente. Es muy interesante manejar autómatas con
esta topología tan frecuente, pero las funciones que hemos preparado
hasta ahora solamente trabajan con listas planas. Esto no ha de
preocuparnos en exceso, pues podemos establecer una correspondencia
sencilla entre los elementos de una lista plana y los elementos de una
malla multidimensional. Lo que vamos a hacer es almacenar las celdas
en una lista con un orden que se conoce en inglés como
row-major: en dos dimensiones, almacenamos los elementos de la
primera fila de izquierda a derecha, luego los elementos de la segunda
fila, luego los elementos de la tercera fila…; en más
dimensiones, generalizamos y vamos apilando siempre con incrementos en
los índices situados más a la derecha y luego sucesivamente los
índices más a la izquierda conforme los índices con más prioridad dan
la vuelta. Por ejemplo, si tenemos una malla tridimensional de dos
celdas por dos celdas por dos celdas con índices de 1 a 3 en cada dimensión
tales que denotamos una celda mediante la tripla (nivel, fila,
columna), la lista de celdas correspondiente sería la {(1,1,1), (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2),
(2,2,1), (2,2,2)}.
Paso de índices planos a índices multidimensionales
Lo más difícil que vamos a hacer hoy es el paso de índice plano a
índices multidimensionales. Usaremos la función unfold
que definimos hace unos días. Naturalmente, es posible hacer el mismo
trabajo con estructuras de control más explícitas como bucles y
funciones recursivas a medida.
El paso de un índice plano a los índices multidimensionales
correspondientes en orden row-major puede hacerse mediante
divisiones enteras sucesivas. El incremento de un índice a la
izquierda supone que han dado la vuelta todos los índices a su
derecha; el tamaño de la vuelta es el producto de los tamaños de las
dimensiones a la derecha del índice que queremos extraer. De lo
anterior se extrae que, dado un índice plano, el índice más a la
izquierda es la división entera del índice plano entre la vuelta
correspondiente al índice más a la izquierda; el siguiente índice
es la división entera del resto de la anterior división y la vuelta
correspondiente al siguiente índice… Esto queda plasmado en la
siguiente función flat->multidimensional que acepta una
lista sizes con los tamaños de las dimensiones desde la que
está más a la izquierda hasta la que está más a la derecha y un índice
plano index; la función devuelve una lista con los índices
multidimensionales desde el situado más a la izquierda hasta el
situado más a la derecha:
(define (flat->multidimensional sizes index)
(define strides
(reverse (cons 1 (if (= (length sizes) 1)
'()
(cumulative-product (reverse (cdr sizes)))))))
(define current-index car)
(define current-stride cadr)
(define strides-list cdr)
(unfold (lambda (index-and-strides)
(null? (strides-list index-and-strides)))
(lambda (index-and-strides)
(floor (/ (current-index index-and-strides)
(current-stride index-and-strides))))
(lambda (index-and-strides)
(cons (modulo (current-index index-and-strides)
(current-stride index-and-strides))
(cdr (strides-list index-and-strides))))
(cons index strides)))
Es así en Python:
def flat_to_multidimensional(sizes, index):
import math
if len(sizes) == 1:
strides = [1]
else:
strides = ([1] + cumulative_product(sizes[:0:-1]))[::-1]
def current_index(index_and_strides):
return index_and_strides[0]
def current_stride(index_and_strides):
return strides_list(index_and_strides)[0]
def strides_list(index_and_strides):
return index_and_strides[1]
def stop_p(index_and_strides):
return len(strides_list(index_and_strides)) == 0
def generate(index_and_strides):
return int(math.floor(current_index(index_and_strides) /
current_stride(index_and_strides)))
def update(index_and_strides):
return (current_index(index_and_strides) %
current_stride(index_and_strides),
strides_list(index_and_strides)[1:])
seed = (index, strides)
return tuple(unfold(stop_p, generate, update, seed))
Paso de índices multidimensionales a índices planos
El algoritmo es mucho más sencillo. Lo que hay que hacer es
multiplicar cada índice por su vuelta correspondiente y sumar los
resultados para obtener el índice plano. Podemos hacer esto con
la función cumulative-product de ayer para calcular las
vueltas (strides) igual que en
flat->multidimensional, luego hacer map para
multiplicar cada índice por su vuelta y finalmente hacer
fold para hacer la suma; en vez de esto, vamos a hacer un
único fold, lo que es posible gracias a la propiedad
distributiva del producto sobre la suma. El algoritmo queda plasmado
en la siguiente función flat->multidimensional de Scheme
que acepta una lista sizes de tamaños de las diferentes
dimensiones desde la primera (la del índice más a la izquierda) a la
última (la del índice más a la derecha) y una lista de índices
indices desde el primero (el que está más a la izquierda)
hasta el último (el que está más a la derecha):
(define (multidimensional->flat sizes indices)
(fold (lambda (index size accumulator)
(+ (* size accumulator) (modulo index size)))
0 indices sizes))
Es así en Python:
def multidimensional_to_flat(sizes, indices):
def accumulate(index, size, accumulator):
return size * accumulator + index % size
return fold(accumulate, 0, indices, sizes)
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/27/jugando-con-automatas-celulares-7/
Volver arriba
2013-08-26
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Seguimos construyendo funciones para hacer una biblioteca de
autómatas celulares razonablemente general y práctica. Hace unos días
creamos unas
pocas funciones útiles de propósito general. Estas funciones son
convenientes no solamente en un programa de autómatas celulares, sino
que son herramientas convenientes en muchas situaciones. Hoy
presentamos una que se nos había quedado en el tintero junto a dos
especializaciones: el mapa acumulativo y el producto acumulativo.
Mapa acumulativo
Vamos a necesitar generar listas de productorios parciales: listas
cuyos elementos son el primer elemento de una lista de entrada; el
producto del primer elemento y el segundo elemento; el producto del
primer elemento, el segundo elemento y el tercer elemento… Para
ello, primero definiremos una función llamada
cumulative-map que aceptará un operador operator
(una función) de dos argumentos, un valor inicial
initial-value (que sería normalmente el elemento identidad
del operador) y una lista sequence sobre la que aplicar el
operador desde el primer elemento hasta el último. Lo haremos con
fold:
(define (cumulative-map operator initial-value sequence)
(define (accumulate item accumulator)
(cons (operator item (car accumulator)) accumulator))
(reverse (fold accumulate
(list (operator initial-value (car sequence)))
(cdr sequence))))
Esto también funciona en Python:
def cumulative_map(operator, initial_value, sequence):
def accumulate(item, accumulator):
return [operator(item, accumulator[0])] + accumulator
return fold(accumulate,
[operator(initial_value, sequence[0])],
sequence[1:])[::-1]
Usamos fold para hacer el equivalente a una función que
crea una lista de forma recursiva. La función fold no
tiene por qué devolver un escalar cuando se le pasa una lista. Ahora
bien, como la llamada a fold va construyendo la lista de
salida de derecha a izquierda, tenemos que darle la vuelta al
resultado. Esta función cumulative-map falla si la
secuencia está vacía.
Producto acumulativo
Ahora que tenemos nuestra función cumulative_map, es
fácil generar listas de sumas parciales, listas de productos parciales
y otras cosas similares. Lo que nos interesa es el generador de
listas de productos parciales, cumulative-product. Tiene
este aspecto en Scheme:
(define (cumulative-product sequence)
(cumulative-map * 1 sequence))
Es casi igual en Python:
def cumulative_product(sequence):
return cumulative_map(lambda a, b: a * b, 1, sequence)
Otra posible aplicación interesante del mapa acumulativo
Digamos que tenemos un autómata celular cuya regla de evolución no
es autónoma, sino que depende de algún parámetro externo. Para fijar
ideas, supongamos que este autómata es un ecosistema de juguete en el
que la evolución de una celda depende de las celdas vecinas y de
parámetros externos que modelan las condiciones meteorológicas.
Podríamos usar cumulative-map para generar un conjunto de
generaciones sucesivas de nuestro autómata celular a partir de una
lista de condiciones meteorológicas y un estado inicial.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/26/jugando-con-automatas-celulares-6/
Volver arriba
2013-08-22
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Hace unos días creamos un
sencillo autómata de ejemplo. El código era específico de este
autómata, pero podemos ir creando funciones más generales con las que
trabajar. Hoy hacemos un pequeño desvío para construir unas pocas
funciones auxiliares que serán muy útiles más adelante. Casi todas
estas funciones son para Scheme R5RS, cuya biblioteca estándar es
deliberadamente pequeña y minimalista. Algunas de estas funciones
aparecen en los «casi estándares» SRFI.
Función para agrupar listas de elementos correspondientes
A menudo, tenemos varias listas y queremos construir una que agrupa
los elementos de forma que tenemos el grupo de los primeros elementos
de las listas de entrada, el grupo de los segundos elementos de las
listas de entrada, el grupo de los terceros elementos de las listas de
entrada… Esta operación suele llamarse zip. Existe
en Python 2 y en Scheme R5RS es así de sencilla:
(define (zip . lists)
(apply map (cons list lists)))
Usamos map para recorrer las listas de entrada. El
número de listas de entrada es variable y lo indicamos así con el
puntito delante del argumento lists. Esto de poner
un puntito es azúcar sintáctico en Scheme para indicar que lo que
sigue es una lista de argumentos de tamaño variable, lo que se conoce
muchas veces como varargs: aunque nosotros ponemos escribimos
los argumentos uno tras otro al llamar a nuestra función, los
argumentos llegan empaquetados en una lista. Luego usamos esta lista
de argumentos con apply para llamar a map, pero
empaquetamos algún argumento adicional con cons. ¡No es
tan difícil! Esta llamada
(zip a b c)
hace esto por debajo
(apply map (cons list (list a b c)))
que a su vez es equivalente a
(map list a b c)
Función de reducción o acumulación
Esto es lo que suele llamarse fold, reduce,
accumulate… Es un consumidor de listas. En Python2 hay
un equivalente llamado reduce que es algo incómodo porque
trabaja con solamente una lista; nosotros queremos usar varias. ¿Qué
hace fold? Lo que hace es ir aplicando un operador (una
función) a los elementos de una lista (o un conjunto de listas) y un
acumulador que va actualizando con el resultado de la última
aplicación de la función. Esta operación tan abstracta es tan
rematadamente útil que ni siquiera Guido van Rossum, dictador
benévolo de Python, pudo
librarse de ella por completo en Python 3.
Hay varias maneras de hacer fold. Nosotros vamos a usar una
variante que recorre la lista linealmente de izquierda a derecha (de
elemento en elemento desde el primero hasta el último) y aplica el
operador con el siguiente valor de la lista (o el siguiente elemento
de cada lista si pasamos varias) en primer lugar y el resultado de la
anterior aplicación del operador en último lugar.
Nuestra fold acepta un número arbitrario de listas
para trabajar. Para hacer esto, tenemos que hacer de nuevo una
función variádica, es decir, que acepta varargs. Nuestra
función acepta como primer argumento el operador operator
que vamos a aplicar, como segundo argumento el valor
inicial initial-value del acumulador, como tercer argumento
la primera lista list1 sobre la que trabajar y (si hay más
argumentos) las demás listas en listn. El código de Scheme
es así:
(define (fold operator initial-value list1 . listn)
(if (null? listn)
(if (null? list1)
initial-value
(fold operator
(operator (car list1) initial-value)
(cdr list1)))
(fold (lambda (lists accumulator)
(apply operator (append lists (list accumulator))))
initial-value
(apply zip (cons list1 listn)))))
No es muy complicado. Empezamos con una comprobación: si no hemos
pasado más que una lista (en cuyo caso listn tiene valor
nulo), hacemos nuestro trabajo directamente; si no, volvemos a llamar
a fold, pero esta vez con los argumentos modificados
para trabajar con los elementos del conjunto de listas de entrada
apareados con zip. El trabajo principal se hace de forma
recursiva. También podemos hacer lo mismo con iteración:
(define (fold operator initial-value list1 . listn)
(if (null? listn)
(do ((accumulator initial-value (operator (car lis) accumulator))
(lis list1 (cdr lis)))
((null? lis) accumulator))
(fold (lambda (lists accumulator)
(apply operator (append lists (list accumulator))))
initial-value
(apply zip (cons list1 listn)))))
Es un poco más compacto, pero más críptico.
Python tiene algo que es casi equivalente a fold:
la función reduce. El problema de reduce es que
solamente admite una lista. Queremos trabajar con varias, así que nos
inventamos una función fold que hace lo mismo que la
de Scheme, pero sin necesidad de reescribir la función
reduce. A cambio, la función reduce de Python
usa operadores cuyo primer argumento es el acumulador y cuyo segundo
argumento es el siguiente valor de la lista; esto es el orden inverso
al que se usa en el fold de Scheme, así que vamos a darle
la vuelta. La función es así:
def fold(operator, initial_value, list1, *listn):
if len(listn) == 0:
def operator_for_reduce(accumulator, new_value):
return operator(new_value, accumulator)
return reduce(operator_for_reduce,
list1,
initial_value)
else:
def apply_operator(lists, accumulator):
arguments = list(lists) + [accumulator]
return operator(*arguments)
return fold(apply_operator,
initial_value,
zip(*([list1] + list(listn))))
En Python 2 hay un equivalente a apply que, de hecho,
se llama igual, pero cuyo uso está desaconsejado a favor de la llamada
con un asterisco que hemos hecho. A veces, parece que Python trata de
recordar a Perl.
Función de generación de listas
Esto es más o menos lo opuesto a fold:
unfold. A partir de unas funciones que indican cómo operar
y un valor semilla, esta función crea una lista. La función
unfold acepta como argumentos un predicado stop?
que indica si hay que parar, una función generate que
genera el siguiente elemento de la lista a partir de la semilla, una
función update que actualiza el valor de la semilla para la
siguiente operación, un valor semilla seed que sirve para
dar comienzo al trabajo y una función opcional tail que
sirve para crear la cola de la lista si queremos.
(define (unfold stop? generate update seed . tail)
(if (stop? seed)
(if (null? tail) '() ((car tail) seed))
(cons (generate seed)
(if (null? tail)
(unfold stop? generate update (update seed))
(unfold stop? generate update (update seed) (car tail))))))
Esta función está bien y es muy compacta, pero podría dejarnos sin
pila si la lista generada creciera mucho. La siguiente versión es más
larga, pero más rápida y sin posibilidad de desbordamiento de pila:
(define (unfold stop? generate update seed . tail)
(define (accumulate current-seed current-list)
(if (stop? current-seed)
(reverse (if (null? tail)
current-list
(cons ((car tail) current-seed)
current-list)))
(accumulate (update current-seed)
(cons (generate current-seed) current-list))))
(accumulate seed '()))
Esta versión es un poquito más complicada que como podría ser.
Estamos haciendo recursión terminal o de cola (tail recursion)
con un acumulador porque Scheme da la garantía de que así nunca nos
quedaremos sin pila por muy profunda que sea la recursión. Aparte de
esto, también es interesante que volvemos a tener la técnica de
separar con un punto la lista de argumentos opcionales; como se trata
de una lista, para acceder a la propia función guardada en
tail hay que acceder al primer elemento (car) de
la lista. También podemos hacer una versión iterativa:
(define (unfold stop? generate update seed . tail)
(do ((current-seed seed (update current-seed))
(current-list '() (cons (generate current-seed) current-list)))
((stop? current-seed) (reverse (if (null? tail)
current-list
(cons ((car tail) current-seed)
current-list))))))
El equivalente en Python es así:
def unfold(stop_p, generate, update, seed, tail=None):
current_list = []
while not stop_p(seed):
current_list = current_list + [generate(seed)]
seed = update(seed)
if tail is not None:
current_list = current_list + [tail(seed)]
return current_list
Esta versión es así de imperativa porque Python no favorece, en
principio, la recursión. La ventaja es que el código es un poquito
más corto que el de recursión explícita, pero es más largo que el
iterativo. La función predicado stop_p se llama de esta
manera como guiño a Lisp. Todo el enfoque que estamos haciendo es
quizá poco Pythónico, con mucha definición de funciones de
orden superior y muy poca definición de interminables árboles de
clases.
Función para generar rangos de números
En Python 2, tenemos la función range para generar un
rango de números entre dos extremos (el primero incluido y el último
excluido) con un incremento que se pasa como argumento opcional y cuyo
valor por defecto es la unidad. De hecho, el primer argumento, que es
el comienzo del rango, también es opcional y toma por defecto el valor
0. Vamos a hacer algo similar en Scheme:
(define (range start end step)
(let ((comparator (if (> end start) >= <=)))
(unfold (lambda (n) (comparator n end))
(lambda (n) n)
(lambda (n) (+ n step))
start)))
Este código funciona parecido a como el range de Python
2, pero no comprueba si el paso step conduce a bucles
infinitos (si es nulo o apunta en sentido opuesto al que acercaría del
comienzo start al final end). Tampoco tiene
parámetros opcionales, sino que todos son obligatorios. Otra
diferencia está en que esta función no obliga a usar argumentos
enteros; podemos usar números racionales y números inexactos (de coma
flotante) sin problemas. El uso de unfold abstrae toda la
lógica iterativa o recursiva; sin duda, podríamos haber hecho el mismo
trabajo con bucles:
(define (range start end step)
(let ((comparator (if (> end start) >= <=)))
(do ((n start (+ n step))
(accumulator '() (cons n accumulator)))
((comparator n end) (reverse accumulator)))))
La sintaxis es algo críptica, pero el código queda más compacto,
sin duda. También podríamos haber usado una función recursiva:
(define (range start end step)
(let ((comparator (if (> end start) >= <=)))
(if (comparator start end)
'()
(cons start (range (+ start step) end step)))))
Igual que pasaba con la primera versión recursiva de unfold,
este código puede dejarnos sin pila. También podríamos hacer una versión
con recursión terminal:
(define (range start end step)
(define comparator (if (> end start) >= <=))
(define (accumulate position accumulator)
(if (comparator position end)
(reverse accumulator)
(accumulate (+ position step) (cons position accumulator))))
(accumulate start '()))
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/22/jugando-con-automatas-celulares-5/
Volver arriba
2013-08-20
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Hace un par de días creamos un
sencillo autómata de ejemplo. El código era específico de este
autómata, pero podemos ir creando funciones más generales con las
que trabajar. Hoy vamos a crear funciones para sacar por pantalla
nuestra lista de celdas de una forma compacta. Dividiremos el trabajo
en en dos funciones que actúan de nivel más bajo a nivel más alto:
convertir la lista de celdas en una cadena de caracteres e imprimir
la lista de celdas.
Convertir una lista de celdas en una cadena de caracteres
Inspeccionar una lista de celdas como una lista a veces no es lo
más deseable. Podemos tratar de hacer la conversión en una cadena
de caracteres. Los caracteres no tienen por qué ser los mismos
valores de los estados, sino que podemos hacer una correspondencia
entre estados y caracteres más agradable a la vista, pero quizá
poco interesante para el trabajo que no es de entrada y salida.
Si los estados de las celdas son enteros consecutivos desde 0 hasta
cierto valor, entonces podemos crear una cadena de caracteres tal
que cada estado numérico es una posición en esta cadena e indica
el carácter a mostrar. Tanto Scheme como Python permiten acceder
a los caracteres individuales de una cadena de forma muy sencilla.
Lo que podemos hacer es recorrer la lista con el estado de cada celda
y crear una lista de caracteres; después, usamos esta última lista
para construir una cadena. En Scheme, el código correspondiente
de una función translate que traduce una lista
de celdas cells a una cadena de caracteres de acuerdo
con una tabla de traducción translation-table puede ser
así:
(define (translate cells translation-table)
(list->string (map (lambda (cell) (string-ref translation-table cell))
cells)))
Usamos map para recorrer las celdas y consultar en la
tabla de una en una; después, usamos la función list->string
para convertir la lista de caracteres en una cadena de caracteres.
El código de Python correspondiente funciona de una forma similar:
def translate(cells, translation_table):
return ''.join(map(lambda cell: translation_table[cell],
cells))
El código es un poco más pintoresco por la manera que ofrece la
biblioteca estándar de Python de juntar una lista de caracteres con
el método join.
Si tenemos una lista de celdas cells con estados 0
y 1, podemos convertirla en una cadena de caracteres en la que
aparecen espacios por cada 0 y asteriscos por cada 1
de la siguiente manera:
(translate cells " *")
(en Scheme) o:
translate(cells, " *")
(en Python).
Función para imprimir listas de celdas unidimensionales
La función de traducción no imprime nada. Podemos hacer una que
traduzca la lista de celdas y la imprima. Esto es muy inmediato; lo
único que hay que hacer es llamar a la función translate
y luego a una de salida de caracteres. Nuestra función no
imprimirá una nueva línea al terminar. En Scheme, es así:
(define (translate-and-display-1d cells translation-table)
(display (translate cells translation-table)))
Los argumentos son los mismos que en la función de traducir,
translate. El código de Python es casi igual de corto:
def translate_and_display_1d(cells, translation_table):
import sys
sys.stdout.write(translate(cells, translation_table))
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/20/jugando-con-automatas-celulares-4/
Volver arriba
2013-08-19
Hace
varios artículos, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Ayer creamos un
sencillo autómata de ejemplo. El código era específico de este
autómata, pero podemos ir creando funciones más generales con las
que trabajar. Empezaremos con una función que servirá para generar
reglas.
Reglas deterministas vistas como consultas en tablas
Podemos modelar una regla determinista mediante una consulta en
una tabla. A cada posible conjunto de vecinos —clave en la
tabla— le corresponde un estado para la próxima generación
—valor en la tabla—. Podemos hacer una función llamada
deterministic-rule que acepta como entrada una tabla
de correspondencias entre vecindarios y estados futuros y devuelve
una función regla utilizable por apply-rule que internamente
consulta la tabla de correspondencias.
En Scheme R5RS, las tablas asociativas son listas con una estructura
especial. Estas listas son conocidas como association lists
o alists. Los elementos de las listas asociativas son a su vez
pares cuyo primer elemento (el car) es la clave. El valor
está de alguna manera accesible a través del cdr del
par, bien directamente con un par estilo (clave . valor),
bien con una lista propia (clave valor). Nosotros vamos a
usar este segundo esquema, que consume un poquito más de memoria, pero
queda más compacto por escrito. Para pedir la entrada correspondiente
a una clave, usamos la función assoc; esta función
devuelve la celda completa cuyo car guarda la clave y cuyo
cdr guarda de alguna manera el valor. La búsqueda de la
entrada es lineal, así que puede ser lenta en tablas muy grandes;
Scheme R5RS es minimalista y si quisiéramos tablas asociativas más
rápidas (hechas con árboles o con tablas hash), tendríamos
que hacérnoslas nosotros mismos, usar bibliotecas externas o usar
extensiones propias de nuestra implementación de Scheme. Si nos
conformamos con las listas, que no funcionan mal en tablas pequeñitas,
la solución es así:
(define (deterministic-rule table)
(lambda (neighbours)
(cadr (assoc neighbours table))))
Las tablas asociativas de Python se llaman diccionarios.
Entramos en un diccionario con una clave y volvemos con el valor
correspondiente. La clave puede ser muchas cosas, pero las listas
no son bienvenidas en principio. Podemos usar tuplas, que son como
listas no mutables. El código de Python es el siguiente:
def deterministic_rule(table):
return lambda neighbourhood: table[tuple(neighbourhood)]
La regla 90 del artículo anterior quedaría escrita de esta manera:
(define rule-90 (deterministic-rule '(((0 0) 0)
((0 1) 1)
((1 0) 1)
((1 1) 0))))
Es así en Python:
rule_90 = deterministic_rule({(0, 0): 0,
(0, 1): 1,
(1, 0): 1,
(1, 1): 0})
Esto no es especialmente más corto que lo que teníamos antes,
pero es prometedor, ya que podemos construir una regla a partir de
una sencilla estructura de datos. La notación de esta estructura
de datos es como un diminuto lenguaje especializado para construir
reglas deterministas. Si tenemos que construir muchas reglas o
generarlas dinámicamente, el mínimo esfuerzo que hemos hecho se
vuelve muy rentable.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/19/jugando-con-automatas-celulares-3/
Volver arriba
2013-08-18
En el
anterior artículo, planteamos un interesante proyecto: una pequeña
biblioteca para construir autómatas celulares. Los autómatas
celulares son unas estructuras matemáticas muy curiosas: retículos de
celdas que van cambiando de un estado a otro y que pueden, a partir de
reglas sencillas, exhibir complejísimos comportamientos emergentes.
Como práctica, nuestra biblioteca estará hecha en Scheme R5RS y en
Python 2. El enfoque es funcional porque el problema se presta mucho
a ello. No nos preocuparemos tanto por hacer un código especialmente
rápido como por hacerlo claro y conciso.
Antes de plantear la arquitectura completa de un sistema de
autómatas celulares más o menos versátil, vamos a construir nuestro
primer autómata elemental. Así podremos jugar un poco antes de entrar
en un terreno más árido.
Diseño del primer autómata celular elemental
Nuestro primer autómata consiste en una circunferencia de celdas
con dos estados posibles cada una: 0 y 1. Como la topología es la de
una circunferencia, todas las celdas tienen una celda vecina a la
izquierda y una celda vecina a la derecha; si la topología fuera la de
un segmento finito, a la celda de cada extremo le faltaría una vecina.
Nuestro primer autómata va a ser determinista y va a usar lo que
se conoce como la regla 90 o la de Martin—Odlyzko—Wolfram.
Esta regla solamente depende del estado de la celda de la izquierda y
el estado de la celda de la derecha: si la celda de la izquierda está
a 1 y la celda de la derecha está a 0, el nuevo estado es 1; si la
celda de la izquierda está a 0 y la celda de la derecha está a 1, el
nuevo estado es 1; en todos los demás casos, el nuevo estado es 0. En
Scheme, la regla es así:
(define (rule-90 neighbours)
(let ((left (car neighbours))
(right (cdr neighbours)))
(cond ((and (= 1 left) (= 0 right)) 1)
((and (= 0 left) (= 1 right)) 1)
(else 0))))
En este código, los vecinos, neighbours, vienen en
forma de un par cuyo primer elemento (el car) es el estado
de la celda de la izquierda (left) y cuyo segundo elemento
(el cdr) es el estado de la celda de la derecha
(right). La versión en Python es así:
def rule_90(neighbours):
left = neighbours[0]
right = neighbours[1]
if left == 1 and right == 0:
return 1
elif left == 0 and right == 1:
return 1
else:
return 0
En este caso, los vecinos (neighbours) llegan en forma
de una tupla cuyo primer elemento es el estado de la celda de la
izquierda (left) y cuyo segundo elemento es el estado de la
celda de la derecha (right).
Ahora nos hace falta una función para estraer el vecindario de una
lista de celdas. Lo más interesante es que la topología es la de una
circunferencia, así que la celda anterior a la primera celda es la
última celda y la celda siguiente a la última celda es la primera
celda. En Scheme, obtener la lista de celdas a la derecha es fácil:
es la cola de la lista de celdas tras dejar el primer elemento fuera
y, al final, el primer elemento. La lista de celdas a la izquierda
es commo la de la de celdas a la derecha, pero calculada del revés.
La idea es la siguiente:
(define (rule-90-neighbourhoods cells)
(define sllec (reverse cells))
(define left (reverse (append (list-tail sllec 1) (list (car sllec)))))
(define right (append (list-tail cells 1) (list (car cells))))
(map cons left right))
Esta función, rule-90-neighbourhoods, acepta una lista
de celdas (cells), construye las celdas a la izquierda
(left) y las celdas a la derecha (right) y
empaqueta todo esto en una lista en la que cada elemento es un par
con el estado de la celda a la izquierda y el estado de la celda a la
derecha de la celda correspondiente. El código en Python es similar:
def rule_90_neighbourhoods(cells):
sllec = cells[::-1]
left = (sllec[1:] + [sllec[0]])[::-1]
right = cells[1:] + [cells[0]]
return zip(left, right)
El funcionamiento es idéntico, pero usamos la sintaxis más
críptica pero a la vez más compacta de Python y además usamos
la función zip, que a efectos prácticos hace lo mismo
que el (map cons left right) de la versión de Scheme:
recorre los elementos de las listas left y right
y los empaqueta en pares.
Tenemos que mostrar por pantalla nuestras listas de celdas. Podemos
imprimir un asterisco si una celda está a 1 y un espacio si una celda está
a 0. Definamos una función llamada display-cells que acepte
una lista de celdas e imprima según este criterio:
(define (display-cells cells)
(display (list->string (map (lambda (cell)
(if (= cell 1) #\* #\ ))
cells))))
La función equivalente en Python es así:
def display_cells(cells):
import sys
sys.stdout.write(''.join(map(lambda cell: '*' if cell == 1 else ' ',
cells)))
Ya tenemos casi todo preparado. Ahora necesitamos algo para poner
el autómata celular en movimiento. Vamos a inventarnos una función
llamada interactive-rule-90 que va a aceptar como entrada
el estado inicial de las celdas e imprimirá una nueva generación cada
vez que el usuario pulse <ENTER> o parará cuando el
usuario introduzca la letra q. Usamos las funciones
escritas hoy en combinación con la sencillísima apply-rule
que definimos el otro día para iterar de generación en generación de
celdas. Esto es así en Scheme:
(define (interactive-rule-90 cells)
(display-cells cells)
(if (not (eq? (read-char) #\q))
(interactive-rule-90 (apply-rule rule-90
cells
rule-90-neighbourhoods))))
Este planteamiento recursivo puede explotar en Python, así que
lo escribimos de forma iterativa:
def interactive_rule_90(cells):
import sys
while True:
display_cells(cells)
if sys.stdin.read(1) == 'q':
break
new_cells = apply_rule(rule_90,
cells,
rule_90_neighbourhoods)
cells = new_cells
Estamos en condiciones de empezar a jugar. Podemos hacer esto en
Scheme:
(interactive-rule-90 '(0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0))
En Python:
interactive_rule_90(8 * [0] + [1] + 8 * [0])
Tras pulsar <ENTER< varias veces, sale esto:
*
* *
* *
* * * *
* *
* * * *
* * * *
* * * * * * * *
* *
¡Recuerda a un triángulo de Sierpinski!
Trabajo futuro
Lo que hemos hecho hasta ahora no es ni elegante ni adaptable.
Plantearemos en los próximos artículos un sistema muy flexible que nos
permitirá expresar cómodamente nuevos autómmatas celulares con los que
experimentar.
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/18/jugando-con-automatas-celulares-2/
Volver arriba
2013-08-12
Un autómata celular es un objeto matemático que consiste en un
conjunto de celdas con valores que van cambiando de un estado a otro
con el paso del tiempo, de generación en generación. El estado al que
cambia una celda depende del estado en el que se encuentra y del de
las celdas que forman su vecindario. Esto parece poco más que un mero
divertimento, pero resulta que los autómatas celulares pueden exhibir
propiedades sorprendentes con fascinantes comportamientos complejos
y organizados que emergen a partir de reglas muy sencillas. Hay
autómatas celulares que funcionan como computadores universales
(¡aunque quizá poco prácticos!).
En esta serie de artículos vamos a plantear unos sencillos
ejercicios prácticos con los que divertirnos con autómatas celulares.
Programaremos nuestro propio sistema para jugar con estas cosas. Por
hacerlo de alguna manera, haremos el programa en dos lenguajes:
Scheme R5RS y Python 2. El primero es un dialecto de Lisp (¿o no?) minimalista
y elegante, mientras que el segundo es un lenguaje que ahora mismo
es muy popular.
Diseño general
Vamos a desarrollar una pequeña biblioteca para manejar autómatas
celulares variados, tanto deterministas como indeterministas y de
topología arbitraria.
Partimos de una colección de celdas, cada celda con un estado
determinado, en un instante dado. Queremos dar un paso temporal,
conocer el estado de las celdas en el siguiente instante. Para ello,
tenemos una regla, que no es más que una función que, dado el
vecindario de una celda, da el nuevo estado que tendrá dicha celda.
Si aplicamos la regla al conjunto de celdas, obtenemos la siguiente
generación, las celdas en el siguiente instante. Para hacer esto,
tomamos las siguientes decisiones:
- Representamos las celdas como una lista plana. Así, la función
que sirve para obtener la próxima generación de celdas no tiene que
conocer la topología de nuestro conjunto de celdas; el mismo código
vale si tenemos una línea de celdas, un retículo bidimensional o
cualquier otra cosa más complicada.
- La función que extrae el vecindario de una celda (es decir, el
estado de cada celda del vecindario) sí ha de conocer la topología,
naturalmente. No es lo mismo conocer las celdas vecinas en una red
unidimensional (una línea en la que hay vecinos a la izquierda y a la
derecha) que en una red bidimensional (un plano donde hay vecinos
tanto en la dirección horizontal como en la dirección vertical). Esta
función no es parte de la que sirve para dar el paso temporal, sino
que se la pasa el usuario de la biblioteca de autómatas celulares.
- Las reglas son funciones, no un meras tablas donde consultar. Si
nos limitáramos a comparar siempre los vecinos con una tabla para
saber el nuevo estado de la celda, solamente podríamos hacer autómatas
deterministas. Si usamos una función, nada impide que esta función se
limite internamente a consultar una tabla y devolver el valor que
corresponda, pero también puede hacer cosas algo más complicadas como
consultar un generador de números aleatorios si nuestro autómata es
indeterminista. Esto da mucho juego.
- La función que itera de un instante de tiempo a otro acepta la
regla, la lista de celdas y la función que extrae el vecindario de
cada celda como argumentos. Se limita a obtener los vecindarios y
a aplicar la regla a cada uno de estos vecindarios. Esto tan sencillo
es el núcleo de un autómata celular; todo lo demás, lo interesante,
está en cómo es la regla y cómo extraemos los vecinos.
Estas ideas quedan plasmada en este código de Scheme tan sencillo:
(define (apply-rule rule cells neighbourhoods)
(map rule (neighbourhoods cells)))
Ya está. La función apply-rule es la que itera de un
instante temporal al siguiente, la que devuelve la siguiente
generación de celdas. Le pasamos la función rule, que es
la regla que acepta como argumento el vecindario de una celda y
devuelve el próximo estado de la celda. También le pasamos la lista
de celdas, cells. Finalmente, el último argumento es la
función que extrae los vecindarios, neighbourhoods. Esta
función acepta como argumento una lista de celdas y devuelve una lista
con los vecindarios de estas celdas. Es así de sencillo.
También podemos hacer lo equivalente en Python:
def apply_rule(rule, cells, neighbourhoods):
return map(rule, neighbourhoods(cells))
El funcionamiento es el mismo.
Por ahora, esto no hace nada, ya que necesitamos la
regla y el extractor de vecindarios. Tendremos algo en el
próximo artículo, en el que crearemos las funciones para un
autómata determinista unidimensional cíclico (es decir, con las
celdas en una circunferencia).
Otros artículos de la serie
Categorías:
Informática
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/12/jugando-con-automatas-celulares-1/
Volver arriba
2013-08-09
Las bicicletas son unos ingenios mecánicos que pueden
parecer simples en un primer vistazo y muy sofisticados
tras un estudio exhaustivo. Por algún motivo, de
vez en cuando aparecen artículos de divulgación en los
que se afirma que desconocemos los principios que hacen funcionar una
bicicleta, lo que es falso. Estos artículos suelen referirse
al problema de la estabilidad lateral/direccional de la bicicleta y
suelen mencionar explicaciones absolutamente incompletas como el
efecto giroscópico es responsable de todo
para luego desmentirlas.
En efecto, sabemos que el efecto giroscópico no es estrictamente
necesario para que una bicicleta sea estable si se cumplen otras
condiciones que, de hecho, se cumplen en la mayoría de los casos.
Tal cosa puede decirse de otras explicaciones simplísimas que no
son explicaciones en realidad. Decir efecto giroscópico
es
como no decir nada; para explicar el mundo físico, mal que le pese
a quien no disfruta del privilegio de entender estas cosas, una buena
explicación tiene más de modelo matemático que de palabra suelta.
Resulta que la dinámica de la bicicleta está bien estudiada
matemáticamente y disponemos de modelos de complejidad variadita,
aunque es raro tener que irse a lo más sofisticado para anticipar si
una determinada bicicleta va a ser estable, pues casi siempre basta
con linealizar alrededor de condiciones de equilibrio, con lo que el
problema, una vez planteado, es una mera cuestión de álgebra lineal
y autovalores. Ahora bien, aquí sucede que el modelo matemático
depende de unas cuantas variables y la cuestión de la estabilidad
depende de ellas de una forma lo bastante compleja como para que un
chiquillo se asuste un poquito. De hecho, la cosa es suficientemente
compleja como para que no podamos sacar conclusiones generales
elementales como cualquier bicicleta, no importa lo caprichoso
de su diseño, es estable si sus ruedas giran por encima de veinte
revoluciones por minuto
. Como tal cosa no existe, el trabajo
de los ingenieros que diseñan bicicletas no se acaba y es posible
encontrar diseños estables aparentemente alocados, por ejemplo sin
efecto giroscópico (difícil de conseguir, pues hay que añadir
ruedas contrarrotatorias) y con avance o trail negativo.
Sí entendemos las bicicletas. Lo que sucede es que sabemos que
esto que entendemos no es trivial.
Categorías:
Matemáticas
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/09/a-pesar-de-los-malos-titulares-si-sabemos-como-funciona-una-bicicleta/
Volver arriba
2013-08-05
Hoy es día 5 del mes 8 del año 2013, que abreviado es «13». Este
día es notablemente notable porque escrito el día, luego el
mes y luego el año es «5, 8, 13». Estos son los números quinto,
sexto y séptimo de la sucesión de Fibonacci. El número séptimo es
el 21, el número octavo es el 34 y el noveno número es el 55,
así que hay que mirar los relojes a las 21:34:55.
El primer número que caracteriza la fecha de hoy es el número 5,
que a su vez es el quinto elemento de la sucesión de Fibonacci. Esto
es notabilísimo. Solamente hay otro número de la sucesión de
Fibonacci cuyo valor coincide con su ordinal: el 1. De este modo,
tenemos cada siglo dos instantes interesantísimos escritos en el
formato «día/mes/año horas:minutos:segundos»:
- 01/02/03 05:08:13;
- 05/08/13 21:34:55.
Categorías:
Fechas,
Matemáticas
Artículos publicados el mismo mes
Permalink:
http://sgcg.es/articulos/2013/08/05/05-08-13-dia-de-fibonacci/
Volver arriba
