Rekursjon benytter en eller annen selvlignende karakter av et objekt (noen representasjon av det gitte problemet) for å produsere noe kvantitativt mål (output) på objektet gjennom noen algoritmer (som bruker den selvlignende naturen).
Kan man representere algoritmer som fraktaler (en slik representasjon er ikke mulig er ikke åpenbart, og heller ikke hvordan representasjonen skal være hvis man eksisterer) av noen målbar informasjon om objektet algoritmen jobber med?
Har verktøyene som ble brukt i studien av fraktaler gitt noen lysende eksempler for nedre eller øvre grenser for rekursiv kompleksitet av algoritmer?
Jeg leter etter eksempler og referanser i retning av om algoritmer kan behandles som fraktaler og verktøy om fraktaler kan brukes til å bevise resultater om algoritmer.
nettopp lagt til Ville vi bli tvunget til å omdefinere noen essensielle egenskaper ved Sierpinski-trekanten hvis Walsh Transform eller Sierpinski-trekanttransformasjon er vist å være helt lineær? http://en.wikipedia.org/wiki/Walsh_matrix
Kommentarer
- IIUC, du spør: » har verktøy brukt i studien av fraktaler blitt brukt til å bevise nedre / øvre grenser på kompleksiteten til algoritmer? «. Det kan være lurt å utvide mer om hvorfor du tror det er sannsynlig og forklare første avsnitt mer detaljert. Mange fraktaler er rekursivt definert og har selvlignende struktur, men jeg tror ikke ‘ at den ene impliserer den andre: rekursiv definisjon av et objekt ikke ‘ t betyr at det er en fraktal og en fraktal trenger ikke ‘ t å være definert rekursivt. Jeg ser ikke ‘ hvordan informasjon spiller inn her.
- Jeg er forresten ikke sikker på hva du mener med » rekursiv kompleksitet av algoritmer «. Mener du noe annet enn de vanlige forestillingene om kompleksitet i algoritmer? ps: Jeg redigerte spørsmålet litt for å gjøre det lettere å lese, rull gjerne redigeringen min tilbake.
- JeffE ‘ sitt svar ser ut til å være nær hvorfor et slikt rammeverk kanskje ikke er mulig.
- Jeg er ikke sikker på hvordan det følger av Jeff ‘ sitt svar. ps: Mer generelt er den virkelige RAM-modellen en av tilnærmingene til beregningsbar analyse. Etter mange eksperters mening i beregningsanalyse er det ikke en veldig god modell, spesielt fra det praktiske perspektivet, da den mangler evnen til å håndtere grenser som er avgjørende for analyse og modellen ikke ‘ t tilsvarer hvordan vi håndterer reelle tall i praksis. Det er papirer av Ker-I Ko, Mark Braverman, … om beregningsevne / kompleksitet av fraktaler. Btw, kapittel 9 i Weirauch-boken har en sammenligning av forskjellige modeller hvis du er interessert.
- ‘ lukk ‘ er et relativt begrep her. Jeg tar signalet fra ‘ nesten alle interessante fraktaler er uberegnelige ‘. Imidlertid ser det ut til å inkludere tilbakemeldingene dine å si noe om spørsmålet.
Svar
Blum, Shub og Smale beviste at medlemskap i Mandelbrot-settet er ubestemmelig i Real RAM-modellen for beregning ( kjent i noen oppstartsirkler som BSS-modellen ).
Argumentet på høyt nivå er en setning langt: Ethvert virkelig RAM-beregningsbart sett er den tellbare foreningen av semi-algebraiske sett, så grensen har Hausdorff-dimensjon 1, men grensen til Mandelbrot-settet har Hausdorff-dimensjon 2. Med samme argument er nesten alle interessante fraktaler uberegnelige i den virkelige RAM-modellen.
Svar
Du kan se på arbeidet til Lutz, Mayordomo, Hitchcock, Gu et al. på Effektiv dimensjon :
… I matematikk er effektiv dimensjon en modifisering av Hausdorff dimensjon og andre fraktale dimensjoner som plasserer det i en beregningsteoriinnstilling …
Jeg syntes det var interessant (selv om jeg ikke er ekspert) E. Mayordomo «s introduksjonsvideo «Effektiv Fractal Dimension in Computational Complexity and Algorithmic Information Theory» (eller den relaterte paper ).
Se også: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, «The Fractal Geometry of Complexity Classes»
Svar
En anvendelse av fraktaler i dokumentanalyse er blitt foreslått i
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., «En ny tilnærming til dokumentanalyse basert på modifisert fraktal signatur,» Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, vol.2, no., Pp.567,570 vol.2, 14-16 Aug 1995 doi: 10.1109 / ICDAR.1995.601960
Her er abstrakt:
Den foreslåtte tilnærmingen er basert på modifisert fraktal signatur. I stedet for de tidkrevende tradisjonelle tilnærmingene (ovenfra og ned og opp og ned) hvor iterative operasjoner er nødvendige for å dele et dokument i blokker for å trekke ut den geometriske (layout) strukturen, kan denne nye tilnærmingen dele et dokument i blokker i bare en steg. Denne tilnærmingen kan brukes til å behandle dokumenter med høy geometrisk kompleksitet. Eksperimenter har blitt gjennomført for å bevise den foreslåtte nye tilnærmingen for dokumentbehandling
To år senere publiserte de en utvidet tidsskriftversjon:
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
Her er sistnevnte papir.
Svar
en del av utfordringen i dette området er at det synes ikke å være en streng formell / matematisk definisjon av begrepet «fractal» . opprinnelig som myntet av Mandelbrot i 1975, den hadde en uformell geometrisk tolkning, men blir nå sett på som mer generell, for eksempel å bruke på diverse viktige matematiske objekter opprettet / oppdaget før de forenet prinsipper. / egenskaper til fraktaler ble gjenkjent, for eksempel Cantor dust eller Sierpinsky-trekanten eller til og med Weierstrauss-funksjon .
selvfølgelig, som i disse eksemplene, har en algoritme for å tegne fraktaler fraktalkompleksitetsegenskaper. det ser imidlertid ut til å være en mye dypere sammenheng mellom fraktaler og algoritmer (kanskje grunnleggende?) som avdekket i koblingene mellom fraktalberegninger og undecidability (kanskje to ansikter med de samme fenomenene?).
et alternativ er å vurdere de nært beslektede itererte funksjonssystemene . prøv
- Fraktal geometri, Turing-maskiner, og del-og-erobre gjentakelser [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (bind 28, nr. 3-4, 1994, s. 405-423)
Disse resultatene viser at det for hver Turing-maskin eksisterer et fraktalsett som kan sees i en viss forstand som geometrisk kodende for komplementet til språket som er akseptert av maskinen. Man kan bygge en fraktalbasert geometrisk beregningsmodell som er beregningsmessig universell. For det andre kartlegger vi resultatene som viser hvordan fraktal geometri fruktbart kan brukes til å løse deling og erobring gjentakelser. En rekursiv algoritme har tidsmessig selvlikhet, og det er en naturlig forbindelse med romlige selvlignende objekter (fraktalbilder). Denne tilnærmingen gir en ny og gênerai måte å løse slike skill-og-erobre inntekter på.
- Undecidable Problems in Fractal Geometry S. Dube, Complex Systems 7 (1993) 423-444
I denne artikkelen , er det etablert et forhold mellom den klassiske beregningsteorien og fraktalgeometrien. Iterated Function Systems brukes som verktøy for å definere fraktaler. Det er vist at to spørsmål om Iterated Function Systems ikke er avgjørbare: å teste om tiltrekkeren til et gitt Iterated Function System og et gitt linjesegment krysser hverandre og å teste om et gitt Iterated Function System er helt frakoblet.