FRACTALES

FRACTAL

MODELACION CELULAR

La modelación celular se efectúa mediante automas celulare los celulares son herramientas utilizadas en Inteligencia Artificial para la representación de comportamientos complejos de algunos sistemas físicos, mecánicos, biológicos o químicos entre otros.

Para la modelación de sistemas complejos como los autómatas celulares se tienen 3 opciones

·      Lograr un modelo de naturaleza continua (en aquellos sistemas que sean analógicos),

·      Utilizar métodos aproximados de discretización (el cual tiene algunos problemas de digitalización),

·      Modelar utilizando un Autómata Celular

Los Automatas Celulare están formados por 3 partes:

1. Una lattice discreta (L). Es el arreglo de celdas que tiene el sistema,
2. Una vecindad (r). Son las celdas que se encuentran junto a la celda-estado. De las vecindades depende la forma en como se comportará y como irá evolucionando el autómata a través del tiempo,

3.    Las reglas de transición (f). Son funciones de transición local como puede ser: la función de transición celda-estado, o una tabla de transición de la celda-estado. Una función f  que puede ser descrita por una fórmula o por reglas de transiciones de la forma u(x)^k →x^k+1, o simplemente por una tabla de transiciones de celda-estado donde k describe el intervalo de evolución del AC

Una regla de evolución también llamada de transición local, que define la evolución del estado de cada célula dependiendo del estado de su vecindad en la generación anterior

Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.

Son sistemas descubiertos dentro del campo de la física computacional por John von Neumann en la década de 1950. La teoría de los autómatas celulares se inicia con su precursor John von Neumann a finales de los década de 1940 con su libro Theory of Self-reproducingAutomata.

Fecha	1936	1947	1950	1951	1952-3	1952-3	1956-9
Evento	pensamiento acerca de las operaciones en las secuencias arbitrarias de elementos discretos	modelo teórico de auto-reproducción de la biologí	sistemas equivalentes a los autómatas celulares	autómata celular en 2D	Autómata celular particular	construcción de una celda de configuración de 200.000	aplicaciones en la resistencia de interferencia de radio control
protagonista	turing	Von Neumann.	Stanislaw Ulam	Stanislaw Ulam	Von Neumann.	Von Neumann.	Salomón Golomb

1960	1961	1966	1967	1970	1970	1980 -1990	1980- 2000
construcción de autómatas reales	propiedades de auto-reproducción	auto-reproducción del libro Theory of Self-reproducing Automata	que el Universo es un gran automata celular , automatas celulares de dos estados , variando el número de estados posibles para cada celula, autómata celular en 1D	Juegos de simulacion	El juego de la vida	investigación en profundidad de los autómatas celulares y su clasificación	estudio de formaciones tridimensionales a partir de automatas celulares. , Para aplicaciones tales como el reconocimiento óptico de caracteres y el recuento de partículas microscópicas
Von Neumann.	Edward Fredkin	Von Neumann.	Konrad Zuse , Edward Fredkin , Stanislaw Ulam, Robert Schrandt, Edgar Frank Codd	Stanislaw Ulam	John Conway	Stephen Wolfram	Carter Bays

AUTAMATAS CELULARES

Un autómata celular es un modelo matemático para un sistema dinámico que evoluciona en pasos discretos. Es adecuado para modelar sistemas naturales que puedan ser descritos como una colección masiva de objetos simples que interactúen localmente unos con otros.

No existe una definición formal y matematica aceptada de Autómata Celular; sin embargo, se puede describir a un A.C. como una tupla, es decir, un conjunto ordenado de objetos caracterizado por los siguientes componentes:

• Una rejilla o cuadriculado (lattice) de enteros (conjunto Z ) infinitamente extendida, y con dimensión (d) que pertenece a (Z). Cada celda de la cuadrícula se conoce como celula.
• Cada célula puede tomar un valor en Z a partir de un conjunto finito de estados k.
• Cada célula, además, se caracteriza por su vecindad, un conjunto finito de células en las cercanías de la misma.
• De acuerdo con esto, se aplica a todas las células de la cuadrícula una función de transición ( f ) que toma como argumentos los valores de la célula en cuestión y los valores de sus vecinos, y regresa el nuevo valor que la célula tendrá en la siguiente etapa de tiempo. Esta función f se aplica, como ya se dijo, de forma homogénea a todas las células, por cada paso discreto de tiempo.

Condiciones de frontera

 

Topología del autómata celular de 2D plegado en 3D para el caso de frontera periódica.

Por definición, un A.C. consiste de una retícula infinita de enteros. Sin embargo, para cuestiones prácticas (como en modelos de sistemas físicos llevados a cabo en ordenadores de memoria finita), se requiere tomar ciertas consideraciones a la hora de implementar un A.C. Por ello, la definición original se modifica para dar cabida a retículas finitas en las que las células del A.C. interactúen. Esto conlleva la consideración extra de lo que debe de suceder con aquellas células que se encuentren en los bordes de la retícula. A la implementación de una o varias consideraciones específicas se le conoce como condición de frontera.

Dentro del ámbito de los A.C., se pueden implementar numerosas condiciones de frontera, en función de lo que el problema real requiera para su modelado. Por ejemplo:

• Frontera abierta. Se considera que fuera de la lattice residen células, todas con un valor fijo. En el caso particular del juego de la vida y de otros A.C. con dos estados en su conjunto k, una frontera se dice fría si las células fuera de la frontera se consideran muertas, y caliente si se consideran vivas.
• Frontera periódica. Se considera a la lattice como si sus extremos se tocaran. En una lattice de dimensión 1, esto puede visualizarse en dos dimensiones como una circunferencia. En dimensión 2, la lattice podría visualizarse en tres dimensiones como un toroide.
• Frontera reflectora. Se considera que las células fuera de la lattice "reflejan" los valores de aquellas dentro de la lattice. Así, una célula que estuviera junto al borde de la lattice (fuera de ella) tomaría como valor el de la célula que esté junto al borde de la lattice, dentro de ella.
• Sin frontera. Haciendo uso de implementaciones que hagan crecer dinámicamente el uso de memoria de la lattice implementada, se puede asumir que cada vez que las células deben interactuar con células fuera de la lattice, esta se hace más grande para dar cabida a estas interacciones. Obviamente, existe un límite (impuesto por la memoria disponible) para esta condición. Es muy importante no confundir esta condición de frontera con la definición original de A.C. cuya lattice es inicialmente infinita. En el caso de un A.C. sin frontera, la lattice comienza con un tamaño definido y finito, y conforme se requiera va creciendo en el tiempo, lo cual no lo hace necesariamente un modelo más cercano a la realidad, pues si se inicializara la lattice aleatoriamente, con esta condición sólo se pueden inicializar las células dentro de la lattice inicial finita, mientras que en el caso de la definición original, en teoría todas las células de la lattice infinita deberían ser inicializadas.

VARIACIONES:

Los A.C. pueden variar en alguna de las características antes mencionadas, derivando en autómatas celulares no estándar.

Por ejemplo, un A.C. estándar tiene una cuadrícula donde se asume que las células son cuadros; es decir, que la retícula tiene una geometría cuadrada. Esto no es necesariamente un requisito, y se puede variar el A.C. para presentar una geometría triangular o hexagonal (en A.C. de 2 dimensiones, el cuadrado, el triángulo y el hexágono son las únicas figuras geométricas que llenan el plano).

También puede variarse el conjunto de estados k que cada célula puede tomar, la función de transición f de forma que ya no sea homogénea, utilizar elementos estocásticos (aleatoriedad) en f (lo que se conoce como A.C. probabilístico), variar las vecindades de cada célula, etc.

Ejemplos de Autómatas Celulares

De una dimensión:

 

Autómata celular generado con la regla 30.

El AC no trivial más simple consiste en una retícula unidimensional de células que sólo pueden tener dos estados (« 0 » o « 1 »), con un vecindario constituido, para cada célula, de ella misma y de las dos células adyacentes (2³=8 configuraciones posibles). Existen 2⁸=256 modos de definir cuál ha de ser el estado de una célula en la generación siguiente para cada una de estas configuraciones, luego existen 256 AC diferentes de este tipo.

Consideremos el AC definido por la tabla siguiente, que nos da la regla de evolución:

Motivo inicial	111	110	101	100	011	010	001	000
Valor siguiente de la célula central	0	0	0	1	1	1	1	0

Juego de la vida

Animación del juego de la vida de Conway

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

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

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

La vida tiene una variedad de patrones reconocidos que provienen de determinadas posiciones iniciales. Poco después de la publicación, se descubrieron el pentaminó R, el planeador o caminador (en inglés glider, conjunto de células que se desplazan) y el explosionador (células que parecen formar la onda expansiva de una explosión), lo que atrajo un mayor interés hacia el juego. Contribuyó a su popularidad el hecho de que se publicó justo cuando se estaba lanzando al mercado una nueva generación de miniordenadores baratos, lo que significaba que se podía jugar durante horas en máquinas que, por otro lado, no se utilizarían por la noche.

Para muchos aficionados, el juego de la vida sólo era un desafío de programación y una manera divertida de usar ciclos de la CPU. Para otros, sin embargo, el juego adquirió más connotaciones filosóficas. Desarrolló un seguimiento casi fanático a lo largo de los años 1970 hasta mediados de los 80.

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

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

• Una célula muerta con exactamente 3 células vecinas vivas "nace" (al turno siguiente estará viva).
• Una célula viva con 2 ó 3 células vecinas vivas sigue viva, en otro caso muere o permanece muerta (por "soledad" o "superpoblación").

Modelo Nagel-Schreckenberg

El modelo de Nagel y Schreckenberg (Na-Sch) es un modelo de flujo de tránsito vehicular con un autómata celular (AC) probabilístico. Por ende, es un modelo de espacio y tiempo discretos, donde cada célula del autómata equivale ya sea a un vehículo en movimiento con cierta velocidad v o a un espacio vacío de la avenida donde se encuentran los vehículos.

El modelo Na-Sch original sirve para modelar autopistas de un carril (ya sea abiertas o en circuito) con vehículos homogéneos.

Creado en 1992 por los científicos Kai Nagel y Michael Schreckenberg, el modelo Na-Sch se ha convertido en la base de muchos otros modelos discretos de tráfico vehicular, debido a su sencillez que sin embargo es capaz de modelar adecuadamente los fenómenos de congestionamiento en autopistas. Esto sucede ya que las gráficas de densidad de tráfico vs. flujo de tráfico son muy similares a las observadas empíricamente en diversas avenidas reales. Además, una simulación de este modelo permite observar las ondas de tráfico comunes en el flujo vehicular.

AUTOMATAS  FINITOS

Un autómata finito es un modelo matemático de una máquina que acepta cadenas de un

lenguaje definido sobre un alfabeto A. Consiste en un conjunto finito de estados y un conjunto

de transiciones entre esos estados, que dependen de los símbolos de la cadena de entrada

DEFINICION AUTOMATAS FINITOS:

Un autómata finito es una tupla (Q, Σ, q₀, δ, F) donde:⁶

§   Q es un conjunto finito de estados;

§  ∑ es un alfabeto finito;

§   q0 ع Q Es el estado inicial;

§   es una función de transición;

§    Es un conjunto de estados finales o de aceptación.

Los autómatas finitos se pueden representar mediante grafos particulares, también llamados diagramas de estados finitos, de la siguiente manera:

§  Los estados se representan como vértices, etiquetados con su nombre en el interior.

§  Una transición desde un estado a otro, dependiente de un símbolo del alfabeto, se representa mediante una arista dirigida que une a estos vértices, y que está etiquetada con dicho símbolo.

§  El estado inicial se caracteriza por tener una arista que llega a él, proveniente de ningún otro vértice.

§  El o los estados finales se representan mediante vértices que están encerrados a su vez por otra circunferencia.

§  Ejemplo de un estado finito:

Este autómata finito está definido sobre el alfabeto Σ={0,1}, posee dos estados s₁ y s₂, y sus transiciones son δ(s₁,0)=s₂, δ(s₁,1)=s₁, δ(s₂,0)=s₁ y δ(s₂,1)=s₂. Su estado inicial es s₁, que es también su único estado final. El lenguaje regular que reconoce puede expresarse mediante la expresión regular (00 | 11 | (01 | 10)(01 | 10)) 

Una de las maneras de representar los autómatas finitos es mediante las tablas de transición o matrices de estado

. Dos posibles tablas para el ejemplo de la imagen anterior podrían ser las siguientes:

salida q ∈ Q símbolo σ ∈ Σ llegada δ(q,σ) ∈ Q s1 0 s2 s1 1 s1 s2 0 s1 s2 1 s2

0 1 →*s1 s2 s1 s2 s1 s2

La primera representa explícitamente los parámetros y el valor que toma cada ocurrencia de la función de transición.⁷ La segunda es más compacta, y marca con una flecha el estado inicial, y con un asterisco los estados finales.

TIPOS DE AUTOMAS FINITOS

Autómatas finitos deterministas (AFD)

Un AFD o autómata finito determinista es aquel autómata finito cuyo estado de llegada está unívocamente determinado por el estado inicial y el carácter leído por el autómata. Formalmente, un autómata finito determinista (AFD) es similar a un Autómata de estados finitos, representado con una 5-tupla (S,Σ,T,s,A) donde:

Σ es un alfabeto; • S un conjunto de estados; • T es la función de transición: ; • es el estado inicial; • es un conjunto de estados de aceptación o finales.

Al contrario de la definición de autómata finito, este es un caso particular donde no se permiten transiciones lambda (vacías), el dominio de la función T es S (con lo cual no se permiten transiciones desde un estado de un mismo símbolo a varios estados).

A partir de este autómata finito es posible hallar la expresión regular resolviendo un sistema de ecuaciones.

               S1 = 1 S1 + 0 S2 + ε

               S2 = 1 S2 + 0 S1+

Siendo ε la palabra nula. Resolviendo el sistema y haciendo uso de las reducciones apropiadas se obtiene la siguiente expresión regular: 1*(01*01*)*. Inversamente, dada la expresión regular es posible generar un autómata que reconozca el lenguaje en cuestión utilizando el algoritmo de Thompson, desarrollado por Ken Thompson, uno de los principales creadores de UNIX, junto con Dennis Ritchie. Un tipo de autómatas finitos deterministas interesantes son los tries.

Autómatas finitos no deterministas (AFND)

Un autómata finito no determinista es aquel que presenta cero, una o más transiciones por el mismo carácter del alfabeto . Un autómata finito no determinista también puede o no tener más de un nodo inicial. Los AFND también se representan formalmente como tuplas de 5 elementos (S,Σ,T,s,A). La única diferencia respecto al AFD es T.

AFD: AFND: (partes de S)

Debido a que la función de transición lleva a un conjunto de estados, el automáta puede estar en varios estados a la vez (o en ninguno si se trata del conjunto vacío de estados). Autómatas finitos no deterministas con transiciones λ Un AFND-λ o autómata finito no determinista con transiciones λ permite cambiar de estado sin procesar ningún símbolo de entrada. Cuando el autómata llega a un estado, se encuentra en ese estado y en los estados a los que apunte este mediante una transición λ.

Un automata es un AFND: (partes de S) AFND-λ: (partes de S)

Cuando el símbolo de entrada es la palabra vacía (λ), existe una transición λ entre los estados. AFD, AFND y AFND-λ Para todo AFND-λ existe un AFND equivalente y para todo AFND existe un AFD equivalente.

4 Que son los procesos de transformación y difumino
5 Que son los fractales?

QUE SON LOS FRACTALES

Podemos decir que son modelos matemáticos que como los grafos se utilizan como herramientas en situaciones problemáticas de biología, arte, ingeniería, física, físico - química, etc. Los fractales son “objetos” (geométricos) generados a partir de un objeto geométrico inicial como puede ser un punto, un segmento, un triángulo, un segmento de curva, etc. que se va modificando por medio de la aplicación reiterada de una ley infinitas veces (llamada ley de reproducción). Como resultado de este procedimiento se obtienen estructuras cuyas partes por pequeñas que sean conservan el mismo aspecto que la versión inicial. Esta particularidad hace que si se amplía una parte de un fractal, no se puede distinguir la figura ampliada de la original. Observemos la formación de un helecho fractal. Como podemos observar de una rama salen muchas ramas y en cada una de ellas se repite el mismo esquema por lo que la ampliación de una parte del original es muy similar al original mismo. Esta es una característica de los fractales.

6Elabore un cuadro explicativo donde explique al menos 5 fractales conocidos, su autor y su uso


 

FRACTAL	AUTOR	USO
conjunto de Mandelbrot		Fue utilizado inicialmente por IBM para Solucionar ruido en las líneas telefónicas  y el mal uso del flujo de la información
triángulo de Sierpinski	matemático polaco Waclaw Sierpinski introdujo el fractal en 1919	Sierpinski diseñó este Fractal  para demostrar, entre otras cosas, que era posible construir una curva que se "cruzaba" consigo misma en todos sus puntos ...  *El triángulo de Sierpinski se puede descomponer en tres figuras congruentes y esas 3 se pueden descomponer en otras tres y asi sucesivamente Esta propiedad ha sido utilizada con astucia en ingeniería. Un ejemplo reciente son las antenas fractales
Curva de Hilbert	David Hilbert (1862-1943)	Se usa en  algoritmos de tramado de imágenes  sin cortarse nunca a sí misma, podía llenar completamente el interior de un cuadrado
curva de Peano	Giuseppe Peano (1858-1932)	Se utiliza en el estudio de células y mnejo de ADN ·         no pasa dos veces por el mismo punto ·          es continua y converge uniformemente ·          la función que define la curva es inyectiva        no hay puntos de cruce, por lo que las hebras nunca se enredan
El Conjunto Triádico de Cantor.	Georg Cantor (1845-1918),	·         estudio del calor específico del espectro energético ·         es un subconjunto de puntos del intervalo [0,1]

7 Que campos del conocimiento utilizan los fractales como modelos de simulación

RELACIÓN CON LAS MATEMATICAS

"Paradójicamente cuando más abstracta se hace la matemática, más concretas resultan sus aplicaciones". La geometría fractal brinda descripciones matemáticas adecuadas para fenómenos naturales. En el Mundo abstracto de la matemática para las estructuras fractales como las consideradas en los ejemplos se denominan fractales ordenadas. En el Mundo real, obvio es, fractales tan ordenados no existen. Como por ejemplo, los litorales, los árboles, los ríos, las nubes, los vasos sanguíneos, las trayectorias de las partículas en movimiento browniano y miles de fenómenos mas "fractales amorfos" constituyen modelos imperfectos que se podrían considerar como "fractales estadísticos o estocásticos". Podriamos decir que los fractales son una idealización ,pues los objetos reales no tienen la infinita cantidad de detalles que estos tienen. La ecuación de Mandelbrot es z = z² + c. Esta originará diversos fractales según el número de iteraciones n que se operen.

RELACIÓN CON LA INFORMATICA

"En Informática los fractales han revolucionado la tecnología en lo que se refiere a la generación de imágenes y su reproducción. Por medio de programas computarizados se pueden representar fractales a fin de describir los flujos de lava, la distribución de galaxias y otros fenómenos más complejos. Es aquí donde aparecen los modelos de simulación digital tan en boga. Un modelo de simulación digital es un conjunto de instrucciones que traducido a un lenguaje computarizado permite obtener datos del comportamiento del fenómeno que se desea estudiar con el fin de predecir y a veces prevenir fenómenos que resultarían costosos o destructivos si se trataron de experimentar. Como por ejemplo: Estudiar el comportamiento de un reactor nuclear ,el crecimiento poblacional de colonias de bacterias o fenómenos sociales. Estudiar problemas ambientales como factores climáticos, un tornado, el flujo turbulento de un río,incendios de bosque, etc. Estudiar aerodinámica en el diseño de aviones, autos y lanchas. En la figura anterior se muestra una fuerte tempestad modelada por un potente supercomputador amenaza sobre un paisaje artificial. Las bolitas de colores muestran el movimiento del aire en el interior y alrededor de la tormenta.

RELACIÓN CON LA NATURALEZA

"Muchos fenómenos de la naturaleza de apariencia aleatoria han podido ser estudiados gracias a los fractales. Porque en este mundo dominado por el caos y la irregularidad los buenos intentos de la geometría clásica no alcanzan, mientras que estos "monstruos " de esta nueva geometría, nos aportan nuevas reglas para conocer y describir la maravillosa y compleja naturaleza. Obeservamos la cristalización de sales de yodo,nafatalina y nos sorprendio la forma de sus bordes. Neuronas de cuerpo humano Forma de la Nubes

8Investigar sobre modelos matemáticos que sirven para construir fractales

9.Datos biograficos de constructores de fractales:

Los fractales fueron concebidos aproximadamente en 1.890 por el francés HENRI PONCARÉ. Sus ideas fueron extendidas más tarde fundamentalmente por dos matemáticos también franceses, Gaston Julia y Pierre Fatou, hacia 1.918. Se trabajó mucho en este campo durante varios años, pero el estudio quedó congelado en los años 20. El estudio fue renovado a partir de 1974 en IBM y fue fuertemente impulsado por el desarrollo de la computadora digital. El Doctor Mandelbrot, de la Universidad de Yale, con sus experimentos de computadora, es considerado como el padre de la GEOMETRÍA FRACTAL. En honor a él, uno de los conjuntos que él investigó fue nombrado en su nombre.

En el siguiente cuadro vemos brevemente un poco de historia fractal: