Die Rekursion verwendet eine selbstähnliche Natur eines Objekts (eine Darstellung des gegebenen Problems), um ein quantitatives Maß (Ausgabe) für das Objekt durch zu erzeugen ein Algorithmus (unter Verwendung der selbstähnlichen Natur).
Kann man Algorithmen als Fraktale (eine solche Darstellung ist nicht möglich, ist weder offensichtlich noch wie die Darstellung sein sollte, wenn eine existiert) einiger messbarer Informationen des Objekts darstellen, an dem der Algorithmus arbeitet?
Haben die bei der Untersuchung von Fraktalen verwendeten Werkzeuge aufschlussreiche Beispiele für Unter- oder Obergrenzen für die rekursive Komplexität von Algorithmen geliefert?
Ich suche nach Beispielen und Referenzen in der Richtung, ob Algorithmen können als Fraktale behandelt werden, und Werkzeuge zu Fraktalen können verwendet werden, um Ergebnisse zu Algorithmen zu beweisen.
gerade hinzugefügt Würden wir gezwungen sein, einige wesentliche Eigenschaften des Sierpinski-Dreiecks neu zu definieren, wenn gezeigt wird, dass die Walsh-Transformation oder die Sierpinski-Dreieck-Transformation vollständig linear sind? http://en.wikipedia.org/wiki/Walsh_matrix
Kommentare
- IIUC, Sie fragen: “ Wurden Werkzeuge zur Untersuchung von Fraktalen verwendet, um Unter- / Obergrenzen für die Komplexität von Algorithmen zu beweisen? „. Vielleicht möchten Sie näher darauf eingehen, warum Sie dies für wahrscheinlich halten, und den ersten Absatz ausführlicher erläutern. Viele Fraktale sind rekursiv definiert und haben eine selbstähnliche Struktur, aber ich glaube nicht, dass eines das andere impliziert: Die rekursive Definition eines Objekts ist nicht ‚ t bedeutet, dass es sich um ein Fraktal handelt und ein Fraktal
nicht rekursiv definiert werden muss. Ich sehe ‚ nicht, wie Informationen hier ins Spiel kommen.
Antwort
Blum, Shub und Smale hat bewiesen, dass die Mitgliedschaft im Mandelbrot-Set unentscheidbar ist im Real RAM-Modell der Berechnung ( bekannt in einigen Emporkömmlingskreisen als BSS-Modell ).
Das übergeordnete Argument ist ein Satz lang: Jede real RAM-berechenbare Menge ist die zählbare Vereinigung von semi-algebraischen Mengen, daher hat ihre Grenze die Hausdorff-Dimension 1, aber die Grenze der Mandelbrot-Menge hat die Hausdorff-Dimension 2. Nach demselben Argument ist fast jedes interessante Fraktal im realen RAM-Modell nicht berechenbar .
Antwort
Sie können einen Blick auf die Arbeit von Lutz, Mayordomo, Hitchcock, Gu et al. on Effektive Dimension :
… In der Mathematik ist die effektive Dimension eine Modifikation der Hausdorff-Dimension und anderer fraktaler Dimensionen, die platziert werden es in einer Einstellung der Berechenbarkeitstheorie …
Ich fand das Einführungsvideo von E. Mayordomo „Effektive fraktale Dimension in der Computerkomplexität und der algorithmischen Informationstheorie“ (oder das zugehörige -Papier ).
Siehe auch: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, „Die fraktale Geometrie von Komplexitätsklassen“
Antwort
Eine Anwendung von Fraktalen in der Dokumentenanalyse wurde in
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y.“Ein neuer Ansatz zur Dokumentenanalyse auf der Grundlage einer modifizierten fraktalen Signatur“, Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, Bd. 2, Nr., S. 567.570, Bd. 2, 14.-16. August 1995 doi: 10.1109 / ICDAR.1995.601960
Hier ist die Zusammenfassung:
Der vorgeschlagene Ansatz basiert auf einer modifizierten fraktalen Signatur. Anstelle der zeitaufwändigen herkömmlichen Ansätze (Top-Down- und Bottom-Up-Ansätze), bei denen iterative Operationen erforderlich sind, um ein Dokument in Blöcke zu zerlegen, um seine geometrische (Layout-) Struktur zu extrahieren, kann dieser neue Ansatz ein Dokument in Blöcke in nur einem aufteilen Schritt. Mit diesem Ansatz können Dokumente mit hoher geometrischer Komplexität verarbeitet werden. Es wurden Experimente durchgeführt, um den vorgeschlagenen neuen Ansatz für die Dokumentenverarbeitung zu beweisen.
Zwei Jahre später veröffentlichten sie eine erweiterte Journalversion:
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, „Modifizierte Fraktale Signatur (MFS): Ein neuer Ansatz zur Dokumentenanalyse für den automatischen Wissenserwerb“, IEEE Transactions on Knowledge and Data Engineering, vol. 9, nein. 5, S. 747-762, September-Oktober 1997
Hier ist das letztere Papier.
Antwort
Ein Teil der Herausforderung in diesem Bereich besteht darin, dass es keine strikte formale / mathematische Definition des Begriffs „Fraktal“ . ursprünglich wie von Mandelbrot im Jahr 1975 geprägt, hatte es eine informelle geometrische Interpretation, wird aber jetzt als allgemeiner angesehen, z. B. für verschiedene wichtige mathematische Objekte, die vor der Vereinheitlichung von Prinzipien erstellt / entdeckt wurden / Eigenschaften von Fraktalen wurden erkannt, wie z. B. Cantorstaub oder das Sierpinsky-Dreieck oder sogar das Weierstrauss-Funktion .
Natürlich hat wie in diesen Beispielen ein Algorithmus zum Zeichnen von Fraktalen fraktale Komplexitätseigenschaften. Es scheint jedoch eine viel tiefere Verbindung zwischen Fraktalen und Algorithmen zu geben (möglicherweise grundlegend?), die in den Zusammenhängen zwischen fraktalen Berechnungen und Unentscheidbarkeit (möglicherweise zwei Gesichter desselben Phänomens?) aufgedeckt wird.
Eine Alternative ist zu Betrachten Sie die eng verwandten iterierten Funktionssysteme . Versuchen Sie beispielsweise
- Fraktale Geometrie, Turing-Maschinen und Wiederholungen zum Teilen und Erobern [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (Bd. 28, Nr. 3-4, 1994, S. 405-423)
Diese Ergebnisse zeigen, dass es für jede Turing-Maschine eine fraktale Menge gibt, die in gewissem Sinne als geometrische Codierung des Komplements der von der Maschine akzeptierten Sprache angesehen werden kann. Man kann ein fraktalbasiertes geometrisches Berechnungsmodell erstellen, das rechnerisch universell ist. Zweitens untersuchen wir die Ergebnisse, die zeigen, wie die fraktale Geometrie fruchtbar verwendet werden kann, um Divide-and-Conquer-Wiederholungen zu lösen. Ein rekursiver Algorithmus besitzt zeitliche Selbstähnlichkeit und es besteht eine natürliche Verbindung zu räumlichen selbstähnlichen Objekten (fraktalen Bildern). Dieser Ansatz bietet eine neue und umfassende Möglichkeit, solche Teilungs- und Eroberungsrückstände zu lösen.
- Unentscheidbare Probleme in der Fraktalgeometrie S. Dube, Complex Systems 7 (1993) 423-444
In diesem Artikel wird eine Beziehung zwischen der klassischen Berechnungstheorie und der fraktalen Geometrie hergestellt. Iterierte Funktionssysteme werden als Werkzeuge zum Definieren von Fraktalen verwendet. Es wird gezeigt, dass zwei Fragen zu iterierten Funktionssystemen unentscheidbar sind: zu testen, ob sich der Attraktor eines bestimmten iterierten Funktionssystems und eines bestimmten Liniensegments schneidet, und zu testen, ob ein bestimmtes iteriertes Funktionssystem vollständig getrennt ist.