La recursividad utiliza alguna naturaleza auto-similar de un objeto (alguna representación del problema dado) para producir alguna medida cuantitativa (salida) en el objeto a través de Algún algoritmo (utilizando la naturaleza auto-similar).
¿Se pueden representar algoritmos como fractales (tal representación no es posible, no es obvio ni cómo debería ser la representación si existe) de alguna información medible del objeto sobre el que trabaja el algoritmo?
¿Las herramientas utilizadas en el estudio de los fractales han proporcionado algunos ejemplos esclarecedores de límites inferiores o superiores para la complejidad recursiva de los algoritmos?
Estoy buscando ejemplos y referencias en la línea de si los algoritmos pueden tratarse como fractales y las herramientas sobre fractales pueden usarse para probar resultados sobre algoritmos.
recién agregado ¿Nos veríamos obligados a redefinir alguna propiedad esencial del triángulo de Sierpinski si se demuestra que la Transformada de Walsh o la Transformada del triángulo de Sierpinski son completamente lineales? http://en.wikipedia.org/wiki/Walsh_matrix
Comentarios
- IIUC, estás preguntando: » ¿se han utilizado herramientas utilizadas en el estudio de los fractales para probar los límites inferiores / superiores en la complejidad de los algoritmos? «. Es posible que desee ampliar más las razones por las que cree que es probable y explicar el primer párrafo con más detalle. Muchos fractales se definen de forma recursiva y tienen una estructura auto-similar, pero no ‘ no creo que uno implique al otro: la definición recursiva de un objeto no ‘ t significa que es un fractal y un fractal no ‘ t necesita ser definido recursivamente. No ‘ veo cómo la información entra en juego aquí.
- Por cierto, no estoy seguro de qué quieres decir con » complejidad recursiva de algoritmos «. ¿Quiere decir algo más que las nociones habituales de complejidad de los algoritmos? PD: Edité un poco la pregunta para que sea más fácil de leer, no dudes en revertir mi edición.
- La respuesta de JeffE ‘ parece estar cerca de por qué tal marco puede no ser posible.
- No estoy seguro de cómo se desprende de la respuesta de Jeff ‘. ps: De manera más general, el modelo de RAM real es uno de los enfoques del análisis computable. En opinión de muchos expertos en análisis computable, no es un modelo muy bueno, particularmente desde la perspectiva práctica, ya que carece de la capacidad para lidiar con límites que es esencial para el análisis y el modelo no ‘ t corresponde a cómo manejamos los números reales en la práctica. Hay artículos de Ker-I Ko, Mark Braverman, … sobre computabilidad / complejidad de los fractales. Por cierto, el capítulo 9 del libro de Weirauch tiene una comparación de diferentes modelos si está interesado.
- ‘ close ‘ es un término relativo aquí. Sigo el ejemplo de ‘ casi todos los fractales interesantes son ‘ incomputables. Sin embargo, incluir tus comentarios también parece decir algo sobre la pregunta.
Responder
Blum, Shub y Smale demostró que la pertenencia al conjunto de Mandelbrot es indecidible en el modelo de RAM real de cálculo ( conocido en algunos círculos advenedizos como el modelo BSS ).
El argumento de alto nivel tiene una oración de longitud: cualquier conjunto computable de RAM real es la unión contable de conjuntos semi-algebraicos, por lo que su límite tiene dimensión de Hausdorff 1, pero el límite del conjunto de Mandelbrot tiene dimensión de Hausdorff 2. Con el mismo argumento, casi todos los fractales interesantes son incomputables en el modelo de RAM real.
Respuesta
Puede echar un vistazo al trabajo de Lutz, Mayordomo, Hitchcock, Gu et al. en Dimensión efectiva :
… En matemáticas, la dimensión efectiva es una modificación de la dimensión de Hausdorff y otras dimensiones fractales que coloca en un escenario de teoría de computabilidad …
Me pareció interesante (aunque no soy un experto) el video introductorio de E. Mayordomo «Dimensión fractal efectiva en la teoría de la complejidad computacional y la información algorítmica» (o el artículo relacionado).
Consulte también: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, «La geometría fractal de las clases de complejidad»
Respuesta
Se ha propuesto una aplicación de fractales en el análisis de documentos en
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., «Un nuevo enfoque para el análisis de documentos basado en la firma fractal modificada», Análisis y reconocimiento de documentos, 1995., Actas de la Tercera Conferencia Internacional, vol.2, no., Pp.567,570 vol.2, 14-16 de agosto de 1995 doi: 10.1109 / ICDAR.1995.601960
Aquí está el resumen:
El enfoque propuesto se basa en una firma fractal modificada. En lugar de los enfoques tradicionales que consumen mucho tiempo (enfoques de arriba hacia abajo y de abajo hacia arriba) donde las operaciones iterativas son necesarias para dividir un documento en bloques para extraer su estructura geométrica (diseño), este nuevo enfoque puede dividir un documento en bloques en solo uno. paso. Este enfoque se puede utilizar para procesar documentos con alta complejidad geométrica. Se han realizado experimentos para probar el nuevo enfoque propuesto para el procesamiento de documentos
Dos años después, publicaron una versión de revista ampliada:
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, «Firma fractal modificada (MFS): Un nuevo enfoque para el análisis de documentos para la adquisición automática de conocimientos», IEEE Transactions on Knowledge and Data Engineering, vol. 9, no. 5, págs. 747-762, septiembre-octubre de 1997
Aquí está el último artículo.
Respuesta
Parte del desafío en esta área es que parece no haber una definición formal / matemática estricta del término «fractal» . originalmente como lo acuñó Mandelbrot en 1975, tenía una interpretación geométrica informal, pero ahora se ve como más general, por ejemplo, se aplica a varios objetos matemáticos importantes creados / descubiertos antes de los principios unificadores / se reconocieron las propiedades de los fractales, como el polvo de Cantor o el triángulo de Sierpinsky o incluso el Función Weierstrauss .
Por supuesto, como en estos ejemplos, un algoritmo para dibujar fractales tiene propiedades de complejidad fractal. sin embargo, parece haber una conexión mucho más profunda entre los fractales y los algoritmos (¿quizás fundamental?) como se descubre en los vínculos entre los cálculos fractales y la indecidibilidad (¿quizás dos caras del mismo fenómeno?).
Una alternativa es considere los sistemas de funciones iteradas estrechamente relacionados. p. ej., pruebe
- Geometría fractal, máquinas de Turing y recurrencias de dividir y conquistar [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (vol. 28, no 3-4, 1994, p. 405-423)
Estos resultados muestran que para cada máquina de Turing existe un conjunto fractal que se puede ver, en cierto sentido, como codificación geométrica del complemento del lenguaje aceptado por la máquina. Se puede construir un modelo geométrico de computación basado en fractales que sea computacionalmente universal. En segundo lugar, examinamos los resultados que muestran cómo la geometría fractal se puede utilizar de manera fructífera para resolver las recurrencias de divide y vencerás. Un algoritmo recursivo posee una auto-semejanza temporal y existe una conexión natural con objetos espaciales auto-similares (imágenes fractales). Este enfoque produce una forma nueva y genérica de resolver tales recurrencias de divide y vencerás.
- Problemas indecidibles en geometría fractal S. Dube, Complex Systems 7 (1993) 423-444
En este artículo , se establece una relación entre la teoría clásica de la computación y la geometría fractal. Los sistemas de funciones iteradas se utilizan como herramientas para definir fractales. Se muestra que dos preguntas sobre los sistemas de funciones iteradas son indecidibles: probar si el atractor de un sistema de funciones iteradas dado y un segmento de línea dado se cruzan y probar si un sistema de funciones iteradas dado está totalmente desconectado.