SGCG

…esto no es un subtítulo…

Ir a: contenido categorías calendario archivo suscripción

Volver arriba

Agosto de 2013

Calendario de artículos de agosto de 2013

lumamijuvido
1234
567891011
12131415161718
19202122232425
262728293031

Jugando con autómatas celulares (9)

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:

  1. Convertimos el número de norma en su expansión binaria de 8 bits. Esto podemos hacerlo con integer->bits.
  2. 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

Permalink: http://sgcg.es/articulos/2013/08/31/jugando-con-automatas-celulares-9/

Jugando con autómatas celulares (8)

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

Permalink: http://sgcg.es/articulos/2013/08/29/jugando-con-automatas-celulares-8/

Jugando con autómatas celulares (7)

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

Permalink: http://sgcg.es/articulos/2013/08/27/jugando-con-automatas-celulares-7/

Jugando con autómatas celulares (6)

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

Permalink: http://sgcg.es/articulos/2013/08/26/jugando-con-automatas-celulares-6/

Jugando con autómatas celulares (5)

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

Permalink: http://sgcg.es/articulos/2013/08/22/jugando-con-automatas-celulares-5/

Jugando con autómatas celulares (4)

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

Permalink: http://sgcg.es/articulos/2013/08/20/jugando-con-automatas-celulares-4/

Jugando con autómatas celulares (3)

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

Permalink: http://sgcg.es/articulos/2013/08/19/jugando-con-automatas-celulares-3/

Jugando con autómatas celuluares (2)

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

Permalink: http://sgcg.es/articulos/2013/08/18/jugando-con-automatas-celulares-2/

Jugando con autómatas celulares (1)

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:

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

Permalink: http://sgcg.es/articulos/2013/08/12/jugando-con-automatas-celulares-1/

A pesar de los malos titulares, sí sabemos cómo funciona una bicicleta

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

Permalink: http://sgcg.es/articulos/2013/08/09/a-pesar-de-los-malos-titulares-si-sabemos-como-funciona-una-bicicleta/

05/08/13: Día de Fibonacci

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»:


Categorías: Fechas, Matemáticas

Permalink: http://sgcg.es/articulos/2013/08/05/05-08-13-dia-de-fibonacci/