Rekursion använder en viss självliknande natur av ett objekt (viss representation av det givna problemet) för att producera någon kvantitativ mått (output) på objektet genom någon algoritm (med användning av den självliknande naturen).
Kan man representera algoritmer som fraktaler (en sådan representation är inte möjlig är inte uppenbart eller hur representationen ska vara om man existerar) av någon mätbar information om objektet algoritmen arbetar med?
Har verktygen som används i studien av fraktaler gett några lysande exempel för nedre eller övre gränser för rekursiv komplexitet av algoritmer?
Jag letar efter exempel och referenser i linje med huruvida algoritmer kan behandlas som fraktaler och verktyg om fraktaler kan användas för att bevisa resultat om algoritmer.
just lagt till Skulle vi tvingas omdefiniera någon väsentlig egenskap hos Sierpinski-triangeln om Walsh Transform eller Sierpinski-triangeltransformation visar sig vara helt linjär? http://en.wikipedia.org/wiki/Walsh_matrix
Kommentarer
- IIUC, du frågar: ” har verktyg som används i studien av fraktaler använts för att bevisa lägre / övre gränser för komplexiteten hos algoritmer? ”. Du kanske vill utöka mer om varför du tror att det är troligt och förklara första stycket mer detaljerat. Många fraktaler är rekursivt definierade och har självliknande struktur men jag tror inte ’ att den ena antyder den andra: rekursiv definition av ett objekt inte ’ t betyder att det är en fraktal och en fraktal behöver inte ’ t definieras rekursivt. Jag ser inte ’ hur information spelar in här.
- Jag är förresten inte säker på vad du menar med ” rekursiv komplexitet av algoritmer ”. Menar du något annat än de vanliga uppfattningarna om algoritmernas komplexitet? ps: Jag redigerade frågan lite för att göra det lättare att läsa, kolla gärna tillbaka min redigering.
- JeffE ’ s svar verkar vara nära varför en sådan ram kanske inte är möjlig.
- Jag är inte säker på hur det följer av Jeff ’ svar. ps: Mer allmänt är den verkliga RAM-modellen en av metoderna för beräkningsbar analys. Enligt många experter inom beräkningsbar analys är det inte en mycket bra modell, särskilt ur det praktiska perspektivet, eftersom den saknar förmågan att hantera gränser som är nödvändiga för analys och modellen inte ’ t motsvarar hur vi hanterar reella tal i praktiken. Det finns papper av Ker-I Ko, Mark Braverman, … om beräknbarhet / komplexitet av fraktaler. Btw, kapitel 9 i Weirauch-boken har en jämförelse av olika modeller om du är intresserad.
- ’ stäng ’ är en relativ term här. Jag tar köen från ’ nästan alla intressanta fraktaler är oberäknbara ’. Men att inkludera din feedback verkar också säga något om frågan.
Svar
Blum, Shub och Smale bevisade att medlemskap i Mandelbrot-uppsättningen är obeslutbart i Real RAM-modell för beräkning ( känd i några uppstartscirklar som BSS-modell ).
Argumentet på hög nivå är en mening långt: Alla Real RAM-beräknbara uppsättningar är den räknbara sammansättningen av halvalgebraiska uppsättningar, så dess gräns har Hausdorff-dimension 1, men Mandelbrot-uppsättningens gräns har Hausdorff-dimension 2. Med samma argument är nästan alla intressanta fraktaler oberäknbara i real-RAM-modellen.
Svar
Du kan titta på arbetet med Lutz, Mayordomo, Hitchcock, Gu et al. på Effektiv dimension :
… I matematik är effektiv dimension en modifiering av Hausdorff-dimension och andra fraktala dimensioner som placerar det i en inställning för beräkbarhetsteori …
Jag tyckte att det var intressant (även om jag inte är expert) E. Mayordomos introduktionsvideo ”Effektiv fraktal dimension i beräkningskomplexitet och algoritmisk informationsteori” (eller relaterad uppsats ).
Se även: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, ”The Fractal Geometry of Complexity Classes”
Svar
En tillämpning av fraktaler i dokumentanalys har föreslagits i
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., ”Ett nytt tillvägagångssätt för dokumentanalys baserad på modifierad fraktalsignatur,” Dokumentanalys och erkännande, 1995., Proceedings of the Third International Conference on, vol.2, nr., S.567,570 vol.2, 14-16 Aug 1995 doi: 10.1109 / ICDAR.1995.601960
Här är abstrakt:
Det föreslagna tillvägagångssättet bygger på modifierad fraktal signatur. Istället för de tidskrävande traditionella tillvägagångssätten (uppifrån och ner och nedifrån och upp-tillvägagångssätt) där iterativa operationer är nödvändiga för att dela upp ett dokument i block för att extrahera dess geometriska (layout) struktur, kan denna nya metod dela upp ett dokument i block i endast ett steg. Detta tillvägagångssätt kan användas för att bearbeta dokument med hög geometrisk komplexitet. Experiment har genomförts för att bevisa det föreslagna nya tillvägagångssättet för dokumentbehandling
Två år senare publicerade de en utökad journalversion:
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, nr. 5, s 747-762, september-oktober 1997
Här är det sistnämnda papperet.
Svar
del av utmaningen inom detta område är att det verkar inte finnas en strikt formell / matematisk definition av termen ”fractal” . ursprungligen som myntad av Mandelbrot 1975 hade den en informell geometrisk tolkning men ses nu som mer allmän, t.ex. tillämpar på diverse viktiga matematiska objekt som skapats / upptäckts innan de förenade principerna / egenskaper hos fraktaler kändes igen, såsom Cantor dust eller Sierpinsky-triangeln eller till och med Weierstrauss-funktion .
så som i dessa exempel har en algoritm för att rita fraktaler fraktalkomplexitetsegenskaper. emellertid verkar det finnas en mycket djupare koppling mellan fraktaler och algoritmer (kanske grundläggande?) som avslöjats i länkarna mellan fraktalberäkningar och undecidability (kanske två ansikten av samma fenomen?).
ett alternativ är att överväga de närbesläktade itererade funktionssystem . t.ex. försök
- Fraktalgeometri, Turing-maskiner och dela och erövra återkommningar [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (vol 28, nr 3-4, 1994, s. 405-423)
Dessa resultat visar att för varje Turing-maskin finns en fraktaluppsättning som i viss mening kan ses som geometriskt kodande komplementet till det språk som accepteras av maskinen. Man kan bygga en fraktalbaserad geometrisk beräkningsmodell som är beräkningsuniversell. För det andra undersöker vi resultaten som visar hur fraktalgeometri kan användas på ett fruktbart sätt för att lösa uppdelningar och erövringar. En rekursiv algoritm har temporär självlikhet och det finns en naturlig koppling till rumsliga självliknande objekt (fraktalbilder). Detta tillvägagångssätt ger ett nytt och gênerai sätt att lösa sådana uppdelnings-och-erövra återkommningar. div> Undecidable Problems in Fractal Geometry S. Dube, Complex Systems 7 (1993) 423-444
I detta dokument , ett samband mellan den klassiska beräkningsteorin och fraktalgeometrin upprättas. Itererade funktionssystem används som verktyg för att definiera fraktaler. Det visas att två frågor om Itererade funktionssystem är obeslutbara: att testa om lockaren till ett givet Iterated Function System och ett givet linjesegment skär varandra och att testa om ett givet Iterated Function System är helt frånkopplat.