La récursivité utilise une certaine nature auto-similaire dun objet (une représentation du problème donné) pour produire une mesure quantitative (sortie) sur lobjet à travers un algorithme (utilisant la nature similaire de soi).
Peut-on représenter des algorithmes comme des fractales (une telle représentation nest pas possible nest pas évidente ni comment la représentation devrait être si elle existe) de certaines informations mesurables de lobjet sur lequel lalgorithme travaille?
Les outils utilisés dans létude des fractales ont-ils fourni des exemples éclairants pour les limites inférieures ou supérieures de la complexité récursive des algorithmes?
Je recherche des exemples et des références dans le sens de savoir si les algorithmes peuvent être traités comme des fractales et des outils sur les fractales peuvent être utilisés pour prouver des résultats sur les algorithmes.
vient dêtre ajouté Serions-nous obligés de redéfinir une propriété essentielle du triangle de Sierpinski si la transformée de Walsh ou celle du triangle de Sierpinski est montrée comme étant entièrement linéaire? http://en.wikipedia.org/wiki/Walsh_matrix
Commentaires
- IIUC, vous demandez: » les outils utilisés dans létude des fractales ont-ils été utilisés pour prouver les limites inférieures / supérieures de la complexité des algorithmes? « . Vous voudrez peut-être expliquer pourquoi vous pensez que cela est probable et expliquer le premier paragraphe plus en détail. De nombreuses fractales sont définies de manière récursive et ont une structure auto-similaire, mais je ne ‘ que l’une implique l’autre: la définition récursive d’un objet n’a pas ‘ t signifie quil sagit dune fractale et quune fractale na ‘ pas besoin dêtre définie récursivement. Je ne ‘ pas voir comment les informations entrent en jeu ici.
- Au fait, je ne suis pas sûr de ce que vous entendez par » complexité récursive des algorithmes « . Voulez-vous dire autre chose que les notions habituelles de complexité des algorithmes? ps: Jai modifié un peu la question pour la rendre plus facile à lire, nhésitez pas à annuler ma modification.
- La réponse de JeffE ‘ semble être proche de pourquoi un tel cadre nest peut-être pas possible.
- Je ne sais pas comment cela découle de la réponse de Jeff ‘. ps: Plus généralement, le modèle de RAM réel est lune des approches de lanalyse calculable. De lavis de nombreux experts en analyse calculable, il ne sagit pas dun très bon modèle, en particulier du point de vue pratique, car il na pas la capacité de gérer les limites qui sont essentielles pour lanalyse et le modèle ne ‘ t correspond à la façon dont nous traitons les nombres réels dans la pratique. Il existe des articles de Ker-I Ko, Mark Braverman, … sur la calculabilité / complexité des fractales. Btw, le chapitre 9 du livre de Weirauch a une comparaison de différents modèles si vous êtes intéressé.
- ‘ close ‘ est un terme relatif ici. Je prends la réplique de ‘ presque toutes les fractales intéressantes ne sont pas calculables ‘. Cependant, le fait dinclure vos commentaires semble également en dire long sur la question.
Answer
Blum, Shub et Smale a prouvé que lappartenance à lensemble de Mandelbrot est indécidable dans le modèle de RAM réel de calcul ( connu dans certains cercles parvenus sous le nom de modèle BSS ).
Largument de haut niveau est long dune phrase: tout ensemble calculable de RAM réelle est lunion dénombrable densembles semi-algébriques, donc sa frontière a la dimension de Hausdorff 1, mais la limite de lensemble de Mandelbrot a la dimension de Hausdorff 2. Par le même argument, presque toutes les fractales intéressantes ne sont pas calculables dans le modèle de la RAM réelle.
Réponse
Vous pouvez jeter un œil aux travaux de Lutz, Mayordomo, Hitchcock, Gu et al. sur Dimension effective :
… En mathématiques, la dimension effective est une modification de la dimension de Hausdorff et dautres dimensions fractales qui place dans un contexte de théorie de calcul …
Jai trouvé intéressant (bien que je ne sois pas un expert) la vidéo dintroduction de E. Mayordomo « Dimension fractale effective dans la complexité de calcul et la théorie de linformation algorithmique » (ou le article associé).
Voir aussi: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, « The Fractal Geometry of Complexity Classes »
Réponse
Une application des fractales dans lanalyse de documents a été proposée dans
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., « A new approach to document analysis based on modified fractal signature, » Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, vol.2, no., Pp.567.570 vol.2, 14-16 août 1995 doi: 10.1109 / ICDAR.1995.601960
Voici le résumé:
Lapproche proposée est basée sur une signature fractale modifiée. Au lieu des approches traditionnelles chronophages (approches descendante et ascendante) où des opérations itératives sont nécessaires pour diviser un document en blocs afin dextraire sa structure géométrique (mise en page), cette nouvelle approche peut diviser un document en blocs en un seul étape. Cette approche peut être utilisée pour traiter des documents à haute complexité géométrique. Des expériences ont été menées pour prouver la nouvelle approche proposée pour le traitement des documents
Deux ans plus tard, ils ont publié une version de revue étendue:
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, « Modified Fractal Signature (MFS): A New Approach to Document Analysis for Automatic Knowledge Acquisition, » IEEE Transactions on Knowledge and Data Engineering, vol. 9, non. 5, pp. 747-762, septembre-octobre 1997
Voici ce dernier article.
Réponse
Une partie du défi dans ce domaine est quil ne semble pas y avoir de définition formelle / mathématique stricte du terme « fractale » . à lorigine, comme inventé par Mandelbrot en 1975, il avait une interprétation géométrique informelle mais est maintenant considéré comme plus général, par exemple en sappliquant à divers objets mathématiques importants créés / découverts avant lunification des principes / propriétés des fractales ont été reconnues, telles que Poussière de Cantor ou le triangle de Sierpinsky ou même le Fonction Weierstrauss .
bien sûr, comme dans ces exemples, un algorithme pour dessiner des fractales a des propriétés de complexité fractale. cependant il semble y avoir un lien beaucoup plus profond entre les fractales et les algorithmes (peut-être fondamental?) tel que découvert dans les liens entre les calculs fractals et lindécidabilité (peut-être deux faces du même phénomène?).
une alternative est de considérez les systèmes de fonctions itérés étroitement liés. par exemple, essayez
- Géométrie fractale, machines de Turing et récurrences diviser et conquérir [pdf] S. Dube, Informatique théorique et Applications / Informaties théoriques et applications (vol. 28, no 3-4, 1994, p. 405-423)
Ces résultats montrent que pour chaque machine de Turing il existe un ensemble fractal qui peut être vu, dans un certain sens, comme encodant géométriquement le complément du langage accepté par la machine. On peut construire un modèle de calcul géométrique basé sur les fractales qui est universel en termes de calcul. Deuxièmement, nous examinons les résultats qui montrent comment la géométrie fractale peut être utilisée de manière fructueuse pour résoudre les récidives de division pour vaincre. Un algorithme récursif possède une auto-similitude temporelle et il existe une connexion naturelle avec des objets auto-similaires spatiaux (images fractales). Cette approche donne une nouvelle et géniale façon de résoudre ces récurrences de division pour la conquête.
- Problèmes indécidables en géométrie fractale S. Dube, Complex Systems 7 (1993) 423-444
Dans cet article , une relation entre la théorie classique du calcul et la géométrie fractale est établie. Les systèmes fonctionnels itérés sont utilisés comme outils pour définir les fractales. Il est montré que deux questions sur les systèmes de fonctions itérées sont indécidables: tester si lattracteur dun système de fonctions itérées donné et un segment de ligne donné se croisent et tester si un système de fonctions itérées donné est totalement déconnecté.