Autosimilaridad en vinculaciones

Presentación del articulo "Vinculaciones autosimilares" para la materia Teoría de la Computación de la maestría en ciencias de la computación en la Universidad Simón Bolívar

1. Autosimilaridad en vinculaciones Francisco Berrizbeitia Universidad Simón Bolívar Teoría de la computación Junio 2014

2. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Temario Autosimilitud de forma general Autosimilitud en vinculaciones Generación de vinculaciones autosimilares

3. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 “En Matemática, la autosimilaridad , a veces llamada autosimilitud o autosemejanza , es la propiedad de un objeto (llamado objeto autosimilar ) en el que el todo es exacta o aproximadamente similar a una parte de sí mismo, por ejemplo cuando el todo tiene la misma forma que una o varias de sus partes. Muchos objetos del mundo real, como las costas marítimas, son estadísticamente autosimilares : partes de ella muestran las mismas propiedades estadísticas en diversas escalas. La autosimilaridad es una propiedad de los fractales.”

4. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Exacta Aproximada

5. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 http://en.wikipedia.org/wiki/Fractal_landscape

6. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? ¿Cuánto mide la costa de Gran Bretaña? ( Mandelbrot 1967)

7. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? The misbehavior of markets ( Mandelbrot 2008)

8. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? Internet traffic viewed on different time scales is self-similar (fractal ) http://www.math.duke.edu/~rtd/p6/

9. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? Medicina

10. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? Medicina

11. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? Plantas

12. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Dónde podemos encontrar objetos autosimilares ? Teoría del caos Atractores extraños

13. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Por qué estudiar esto?

14. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Por qué estudiar esto? Modelado de datos como grafos: Graph Databases RDF OWL

15. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 ¿Por qué estudiar esto? Modelado de datos como grafos: Graph Databases RDF OWL Detección de invariantes Generación de datos sintéticos

16. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Vínculos Estructuras de vínculos Autosimilitud en estructuras de vínculos

17. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Vínculo

18. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Vinculación

19. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Las vinculaciones las podemos interpretar como un grafo dirigido {¦<: a,b :>,<: a,c :>,<: b,d :>,<: c:d :>} El largo de los lados y la forma de figura no aportan ninguna información, la información esta únicamente en la adyacencia de los nodos y la orientación de los arcos .

20. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014

21. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Según B. Mandelbrot , un objeto es autosimilar o autosemejante si sus partes tienen la misma forma o estructura que el todo, aunque pueden presentarse a diferente escala y pueden estar ligeramente deformadas. Una vinculación es autosimilar si se puede expresar como la unión de vinculaciones isomorfas entre sí.

22. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Por ejemplo la siguiente vinculación es autosimilar porque se puede representar como {¦<: a,b :>,<: a,c :>,<: b,d :>,<: c:d :>} U {¦<: c,d :>,<: c,e :>,<: e,f :>,<: d:f :>} U {¦<: e,f :>,<: e,g :>,<: f,h :>,<: g:h :>} que son claramente isomorfas entre sí.

23. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Generación de complejidad en estructuras de vinculación

24. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Anexión Sean V’ y V dos vinculaciones donde V tiene un único final y V’ un único inicio, la anexión de V’ a V es el resultado de crear un vínculo <: v,v ’:> donde v corresponde al elemento no marcado del final de V y v’ es el elemento marcado del inicio de V’ y unir ambas vinculaciones y el nuevo vínculo.

25. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Sustitución Dado un vínculo <: a,b :> en una vinculación V, y una vinculación V ’ con un único inicio y un único final tal como está definido en ( Baralt Torrijos, Vinculación, 2014 ) La sustitución <: a,b :> por V’ en V el resultado de sustraer <: a,b :> de V, sustituir el inicio de V’ por el elemento marcado de <: a,b :> , el final de V’ por el elemento no marcado de <: a,b :> y unir V’ a V.

26. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Sustitución

27. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014

28. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Sistemas de Lindenmeyer en vinculaciones Los sistema L son definidos como un conjunto G = {V, S, ω, P}, Donde • V (el alfabeto) es un conjunto de símbolos que contiene elementos que pueden ser remplazados (variables ) • S es un conjunto de símbolos que contiene elementos que se mantiene fijos (constantes ) • ω es una cadena de símbolos de V que definen el estado inicial del sistema (inicio o axioma) • P es un conjunto de reglas o producciones que definen la forma en la que las variables pueden ser remplazadas por combinaciones de constantes y otras variables. Una producción está formada por dos cadenas — el predecesor y el sucesor. Las reglas gramaticales de los sistemas-L se aplican iterativamente a partir de un estado inicial.

29. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Variables  : F Constantes  : + − Inicio  : F Reglas  : (F → F-F++F-F) Aquí,  F  significa "dibujar hacia adelante",  +  significa "vuelta de 45° hacia la izquierda", y  -  significa "vuelta de 45° hacia la derecha". Curva de Koch http://www.kevs3d.co.uk/dev/lsystems/ 1 Iteración 3 Iteraciones 6 Iteraciones

30. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Sea donde Z son los número enteros y la colección de los elementos posibles en una vinculación. En la cadena un número a la derecha de un elemento significa que hay vínculo cuyo elemento destacado es el elemento a la izquierda del número y el no destacado el j- esimo elemento de la cadena (a la derecha si es positivo o a la izquierda si es negativo) de la cadena .   C = a12b2c1d genera la siguiente vinculación V = {¦<: a,b :>,<: a,c :>,<: b,d :>,<: c,d :> }

31. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Variables: A,B,C,D Inicio: A Reglas: A → A12B2C1D Haciendo dos iteraciones tenemos: V = A12B2C1D12B2C1D Ejemplo Si permitimos que la variables “se instancien” como elementos de una colección podemos obtener una vinculación mucho más interesante ya que los vínculos no estarían repetidos con los mismo elementos.

32. Autosimilaridad en vinculaciones Francisco Berrizbeitia – USB – Teoría de la computación - Junio 2014 Conclusiones