Recursie maakt gebruik van een of andere soortgelijke aard van een object (een representatie van het gegeven probleem) om een kwantitatieve maat (output) op het object te produceren door middel van een algoritme (gebruikmakend van de zelf-gelijkende aard).

Kan men algoritmen voorstellen als fractals (een dergelijke representatie is niet mogelijk is niet duidelijk, noch hoe de representatie zou moeten zijn als er een bestaat) van enige meetbare informatie van het object waaraan het algoritme werkt?

Hebben de tools die worden gebruikt bij de studie van fractals verhelderende voorbeelden opgeleverd voor onder- of bovengrenzen voor recursieve complexiteit van algoritmen?

Ik ben op zoek naar voorbeelden en verwijzingen in de trant van of algoritmen kunnen worden behandeld als fractals en tools over fractals kunnen worden gebruikt om resultaten over algoritmen te bewijzen.

zojuist toegevoegd Zouden we gedwongen zijn om een essentiële eigenschap van de Sierpinski-driehoek opnieuw te definiëren als wordt aangetoond dat Walsh-transformatie of Sierpinski-driehoekstransformatie volledig lineair is? http://en.wikipedia.org/wiki/Walsh_matrix

Reacties

  • IIUC, u vraagt: ” heeft tools die zijn gebruikt bij de studie van fractals zijn gebruikt om de onder- / bovengrenzen van de complexiteit van algoritmen te bewijzen? “. Misschien wilt u meer uitleggen waarom u denkt dat dat waarschijnlijk is, en de eerste alinea in meer detail uitleggen. Veel fractals zijn recursief gedefinieerd en hebben een vergelijkbare structuur, maar ik denk niet dat ‘ niet de ene de andere impliceert: recursieve definitie van een object is niet ‘ t betekent dat het een fractal is en een fractal hoeft niet ‘ t recursief te worden gedefinieerd. Ik ‘ zie niet hoe informatie hier een rol speelt.
  • Ik weet trouwens niet zeker wat je bedoelt met ” recursieve complexiteit van algoritmen “. Bedoel je iets anders dan de gebruikelijke noties van complexiteit van algoritmen? ps: ik heb de vraag een beetje aangepast om het lezen gemakkelijker te maken, voel je vrij om mijn bewerking terug te draaien.
  • JeffE ‘ s antwoord lijkt dichtbij waarom zon raamwerk misschien niet mogelijk is.
  • Ik weet niet zeker hoe dat volgt uit het antwoord van Jeff ‘. ps: Meer in het algemeen is het echte RAM-model een van de benaderingen van berekenbare analyse. Naar de mening van veel experts in berekenbare analyse is het geen erg goed model, vooral niet vanuit praktisch perspectief, omdat het niet in staat is om met limieten om te gaan, wat essentieel is voor analyse en het model niet ‘ t komen overeen met hoe we in de praktijk met reële getallen omgaan. Er zijn papers van Ker-I Ko, Mark Braverman, … over berekenbaarheid / complexiteit van fractals. Trouwens, hoofdstuk 9 van het Weirauch-boek bevat een vergelijking van verschillende modellen als je geïnteresseerd bent.
  • ‘ close ‘ is hier een relatief begrip. Ik neem het signaal van ‘ bijna elke interessante fractal is onberekenbaar ‘. Het opnemen van uw feedback lijkt echter ook iets over de vraag te zeggen.

Answer

Blum, Shub en Smale bewees dat lidmaatschap van de Mandelbrot-set onbeslisbaar is in het Real RAM-model van berekening ( bekend in enkele beginnende kringen als het BSS-model ).

Het argument op hoog niveau is één zin lang: elke Real RAM-berekenbare set is de telbare unie van semi-algebraïsche verzamelingen, dus de grens heeft Hausdorff-dimensie 1, maar de grens van de Mandelbrot-set heeft een Hausdorff-dimensie 2. Met hetzelfde argument, is bijna elke interessante fractal onberekenbaar in het real-RAM-model.

Answer

Je kunt een kijkje nemen in het werk van Lutz, Mayordomo, Hitchcock, Gu et al. op Effectieve dimensie :

… In de wiskunde is effectieve dimensie een wijziging van Hausdorff-dimensie en andere fractale dimensies die plaatsen het in een berekenbaarheidstheorie-setting …

Ik vond het interessant (hoewel ik “geen expert ben) E. Mayordomos introductievideo “Effective Fractal Dimension in Computational Complexity and Algorithmic Information Theory” (of de gerelateerde paper ).

Zie ook: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, “The Fractal Geometry of Complexity Classes”

Antwoord

Een toepassing van fractals in documentanalyse is voorgesteld in

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, deel 2, nr., Pp. 567,570 deel 2, 14-16 aug. 1995 doi: 10.1109 / ICDAR.1995.601960

Hier is de samenvatting:

De voorgestelde benadering is gebaseerd op een gemodificeerde fractale handtekening. In plaats van de tijdrovende traditionele benaderingen (top-down en bottom-up benaderingen) waarbij iteratieve bewerkingen nodig zijn om een document in blokken te splitsen om de geometrische (lay-out) structuur te extraheren, kan deze nieuwe benadering een document in slechts één blok opdelen in blokken. stap. Deze benadering kan worden gebruikt om documenten met een hoge geometrische complexiteit te verwerken. Er zijn experimenten uitgevoerd om de voorgestelde nieuwe aanpak voor documentverwerking te bewijzen.

Twee jaar later publiceerden ze een uitgebreide tijdschriftversie:

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, nee. 5, pp. 747-762, september-oktober 1997

Hier is het laatste artikel.

Antwoord

Een deel van de uitdaging op dit gebied is dat er geen strikte formele / wiskundige definitie lijkt te zijn van de term “fractal” . oorspronkelijk zoals bedacht door Mandelbrot in 1975 had het een informele geometrische interpretatie maar wordt nu gezien als algemener, bijvoorbeeld van toepassing op diverse belangrijke wiskundige objecten die zijn gemaakt / ontdekt voordat principes werden verenigd / eigenschappen van fractals werden herkend, zoals Cantor dust of de Sierpinsky-driehoek of zelfs de Weierstrauss-functie .

natuurlijk, zoals in deze voorbeelden, heeft een algoritme om fractals te tekenen fractale complexiteitseigenschappen. er lijkt echter een veel diepere verbinding te zijn tussen fractals en algoritmen (misschien fundamenteel?), zoals ontdekt in de verbanden tussen fractalberekeningen en onbeslisbaarheid (misschien twee gezichten van hetzelfde fenomeen?).

een alternatief is om overweeg de nauw verwante herhaalde functiesystemen . bijv. probeer

Deze resultaten laten zien dat er voor elke Turing-machine een fractal-set bestaat die in zekere zin kan worden gezien als een geometrische codering van het complement van de taal die door de machine wordt geaccepteerd. Men kan een op fractal gebaseerd geometrisch rekenmodel bouwen dat computationeel universeel is. Ten tweede onderzoeken we de resultaten die laten zien hoe fractale geometrie vruchtbaar kan worden gebruikt om verdeel-en-heers recidieven op te lossen. Een recursief algoritme bezit temporele zelfgelijkenis en er is een natuurlijke connectie met ruimtelijke zichzelf gelijkende objecten (fractale afbeeldingen). Deze benadering levert een nieuwe en gênerai manier op om dergelijke verdeel-en-heersrecurrences op te lossen.

In dit artikel wordt een verband gelegd tussen de klassieke computertheorie en fractale geometrie. Iterated Function Systems worden gebruikt als tools om fractals te definiëren. Er wordt aangetoond dat twee vragen over Iterated Function Systems onbeslisbaar zijn: om te testen of de attractor van een bepaald Iterated Function System en een bepaald lijnsegment elkaar kruisen en om te testen of een bepaald Iterated Function System volledig is losgekoppeld.

Geef een reactie

Het e-mailadres wordt niet gepubliceerd. Vereiste velden zijn gemarkeerd met *