Rekursion bruger en eller anden selvlignende karakter af et objekt (en vis repræsentation af det givne problem) til at producere et kvantitativt mål (output) på objektet gennem en eller anden algoritme (ved hjælp af den lignende natur).

Kan man repræsentere algoritmer som fraktaler (en sådan gengivelse er ikke mulig, er ikke indlysende, eller hvordan repræsentationen skal være, hvis man findes) af nogle målbare oplysninger om det objekt, algoritmen arbejder på?

Har de anvendte værktøjer til undersøgelse af fraktaler givet nogle lysende eksempler for nedre eller øvre grænser for rekursiv kompleksitet af algoritmer?

Jeg leder efter eksempler og referencer i retning af, om algoritmer kan behandles som fraktaler, og værktøjer om fraktaler kan bruges til at bevise resultater om algoritmer.

lige tilføjet Ville vi være tvunget til at omdefinere nogle vigtige egenskaber ved Sierpinski-trekanten, hvis Walsh Transform eller Sierpinski-trekantstransformation er vist at være fuldstændig lineær? http://en.wikipedia.org/wiki/Walsh_matrix

Kommentarer

  • IIUC, du spørger: ” er værktøjer, der er brugt i undersøgelsen af fraktaler, blevet brugt til at bevise nedre / øvre grænser for kompleksiteten af algoritmer? “. Det kan være en god idé at udvide mere om, hvorfor du synes det er sandsynligt, og forklare første afsnit mere detaljeret. Mange fraktaler er rekursivt definerede og har en selvlignende struktur, men jeg tror ikke ‘ den ene antyder den anden: rekursiv definition af et objekt betyder ikke ‘ t betyder, at det er en fraktal, og en fraktal behøver ikke ‘ t at være defineret rekursivt. Jeg kan ikke se ‘ hvordan information spiller ind her.
  • Forresten er jeg ikke sikker på, hvad du mener med ” rekursiv kompleksitet af algoritmer “. Mener du noget andet end de sædvanlige forestillinger om algoritmernes kompleksitet? ps: Jeg redigerede spørgsmålet lidt for at gøre det nemmere at læse. Du er velkommen til at rulle min redigering tilbage.
  • JeffE ‘ s svar synes at være tæt på hvorfor en sådan ramme muligvis ikke er mulig.
  • Jeg er ikke sikker på, hvordan det følger af Jeff ‘ s svar. ps: Mere generelt er den ægte RAM-model en af fremgangsmåderne til beregningsanalyse. Efter mange eksperters opfattelse af beregningsanalyse er det ikke en særlig god model, især fra det praktiske perspektiv, da den mangler evnen til at håndtere grænser, der er essentielle for analyse, og modellen ikke ‘ t svarer til, hvordan vi i praksis håndterer reelle tal. Der er papirer fra Ker-I Ko, Mark Braverman, … om beregningsevne / kompleksitet af fraktaler. Btw, kapitel 9 i Weirauch-bogen har en sammenligning af forskellige modeller, hvis du er interesseret.
  • ‘ luk ‘ er en relativ betegnelse her. Jeg tager køen fra ‘ næsten enhver interessant fraktal er uberegnelig ‘. Men også din feedback synes at sige noget om spørgsmålet.

Svar

Blum, Shub og Smale beviste, at medlemskab af Mandelbrot-sættet er ubeslutsom i Real RAM-modellen til beregning ( kendt i nogle upstart-cirkler som BSS-modellen ).

Argumentet på højt niveau er en sætning langt: Ethvert realt RAM-beregningssæt er den tællbare sammenslutning af semi-algebraiske sæt, så dens grænse har Hausdorff-dimension 1, men grænsen for Mandelbrot-sættet har Hausdorff-dimension 2. Af samme argument er næsten enhver interessant fraktal uberegnelig i den virkelige RAM-model.

Svar

Du kan se på arbejdet fra Lutz, Mayordomo, Hitchcock, Gu et al. på Effektiv dimension :

… I matematik er effektiv dimension en ændring af Hausdorff-dimension og andre fraktale dimensioner, som placerer det i en beregningsteoriindstilling …

Jeg fandt interessant (selvom jeg ikke er ekspert) E. Mayordomo “s introduktionsvideo “Effektiv fraktal dimension i beregningskompleksitet og algoritmisk informationsteori” (eller det relaterede papir ).

Se også: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, “Den fraktale geometri af kompleksitetsklasser”

Svar

En anvendelse af fraktaler i dokumentanalyse er blevet foreslået i

Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., “En ny tilgang til dokumentanalyse baseret på modificeret 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 abstrakten:

Den foreslåede tilgang er baseret på ændret fraktal signatur. I stedet for de tidskrævende traditionelle metoder (top-down og bottom-up-tilgange), hvor iterative operationer er nødvendige for at opdele et dokument i blokke for at udtrække dets geometriske (layout) struktur, kan denne nye tilgang opdele et dokument i blokke i kun en trin. Denne tilgang kan bruges til at behandle dokumenter med høj geometrisk kompleksitet. Eksperimenter er blevet gennemført for at bevise den foreslåede nye tilgang til dokumentbehandling

To år senere offentliggjorde de en udvidet tidsskriftversion:

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 sidstnævnte papir.

Svar

del af udfordringen på dette område er, at der ikke synes at være en streng formel / matematisk definition af udtrykket “fractal” . oprindeligt som opfundet af Mandelbrot i 1975, den havde en uformel geometrisk fortolkning, men ses nu som mere generel, f.eks. anvendelse på diverse vigtige matematiske objekter, der er oprettet / opdaget før de forenede principper / egenskaber af fraktaler blev genkendt, såsom Cantor dust eller Sierpinsky-trekanten eller endda Weierstrauss-funktion .

selvfølgelig, som i disse eksempler, har en algoritme til at tegne fraktaler fraktalkompleksitetsegenskaber. der synes imidlertid at være en meget dybere forbindelse mellem fraktaler og algoritmer (måske grundlæggende?) som afsløret i forbindelserne mellem fraktalberegninger og undecidability (måske to ansigter med de samme fænomener?).

et alternativ er at overvej de nært beslægtede itererede funktionssystemer . prøv f.eks.

Disse resultater viser, at der for hver Turing-maskine findes et fraktalsæt, som i en vis forstand kan ses som geometrisk kodende for komplementet til det sprog, der accepteres af maskinen. Man kan opbygge en fraktalbaseret geometrisk beregningsmodel, der er beregningsmæssigt universel. For det andet undersøger vi resultaterne, der viser, hvordan fraktalgeometri med frugt kan bruges til at løse opdelings-og-erobre gentagelser. En rekursiv algoritme besidder tidsmæssig selvlignelighed, og der er en naturlig forbindelse med rumlige selvlignende objekter (fraktale billeder). Denne tilgang giver en ny og gênerai måde at løse sådanne opdeling-og-erobre récurrences på.

I dette papir , er der etableret et forhold mellem den klassiske beregningsteori og fraktalgeometri. Itererede funktionssystemer bruges som værktøjer til at definere fraktaler. Det vises, at to spørgsmål om Itererede funktionssystemer er ubeslutsomme: at teste, om tiltrækkeren af et givet Itereret funktionssystem og et givet linjesegment krydser hinanden og at teste, om et givet Itereret funktionssystem er fuldstændigt afbrudt.

Skriv et svar

Din e-mailadresse vil ikke blive publiceret. Krævede felter er markeret med *