Recursiunea utilizează o natură similară a unui obiect (o reprezentare a problemei date) pentru a produce o anumită măsură cantitativă (ieșire) pe obiect prin un anumit algoritm (folosind natura de sine asemănătoare).
Se pot reprezenta algoritmi ca fractali (o astfel de reprezentare nu este posibilă nu este evident și nici cum ar trebui să fie reprezentarea dacă există una) a unor informații măsurabile ale obiectului pe care funcționează algoritmul?
Instrumentele utilizate în studiul fractalelor au furnizat exemple de iluminare pentru limitele inferioare sau superioare pentru complexitatea recursivă a algoritmilor?
Caut exemple și referințe de-a lungul liniei dacă algoritmii pot fi tratați ca fractali și instrumentele despre fractali pot fi folosite pentru a demonstra rezultatele despre algoritmi.
tocmai adăugat Am fi obligați să redefinim unele proprietăți esențiale ale triunghiului Sierpinski dacă se arată că Transformarea Walsh sau Transformarea triunghiului Sierpinski sunt complet liniare? http://en.wikipedia.org/wiki/Walsh_matrix
Comentarii
- IIUC, vă întrebați: ” instrumentele utilizate în studiul fractalelor au fost utilizate pentru a demonstra limitele inferioare / superioare ale complexității algoritmilor? „. Poate doriți să explorați mai multe de ce credeți că este probabil și să explicați primul paragraf mai detaliat. Multe fractale sunt definite recursiv și au o structură asemănătoare cu sine, dar nu cred ‘ nu cred că una o implică pe cealaltă: definiția recursivă a unui obiect nu ‘ înseamnă că este un fractal, iar un fractal nu trebuie să fie definit recursiv ‘ Nu ‘ nu văd cum intră în joc informațiile aici.
- Apropo, nu sunt sigur ce vrei să spui prin ” complexitatea recursivă a algoritmilor „. Vrei să spui altceva decât noțiunile obișnuite de complexitate a algoritmilor? ps: Am editat puțin întrebarea pentru a ușura citirea, nu ezitați să reveniți la editarea mea.
- Răspunsul lui JeffE ‘ pare să fie aproape de de ce un astfel de cadru poate să nu fie posibil.
- Nu sunt sigur cum rezultă din răspunsul lui Jeff ‘. ps: Mai general, modelul RAM real este una dintre abordările analizei calculabile. În opinia multor experți în analiza calculabilă, acesta nu este un model foarte bun, mai ales din perspectiva practică, deoarece nu are capacitatea de a face față limitelor, care este esențială pentru analiză, iar modelul nu ‘ t corespunde modului în care ne ocupăm cu numerele reale în practică. Există lucrări de Ker-I Ko, Mark Braverman, … despre calculabilitate / complexitatea fractalelor. Btw, cap.9 din cartea Weirauch are o comparație între diferite modele dacă sunteți interesat.
- ‘ închideți ‘ este un termen relativ aici. Iau indiciu de la ‘ aproape fiecare fractal interesant este incomputabil ‘. Cu toate acestea, inclusiv feedback-ul dvs. pare să spună ceva și despre întrebare.
Răspuns
Blum, Shub și Smale a dovedit că apartenența la setul Mandelbrot este indecisibilă în modelul RAM real de calcul ( cunoscut în unele cercuri parvenite ca model BSS ).
Argumentul la nivel înalt are o propoziție: orice set de calcul RAM real este uniunea numărabilă a mulțimilor semi-algebrice, deci granița sa are dimensiunea Hausdorff 1, dar granița setului Mandelbrot are dimensiunea Hausdorff 2. Prin același argument, aproape fiecare fractal interesant este incomputabil în modelul RAM real.
Răspuns
Puteți arunca o privire asupra lucrării lui Lutz, Mayordomo, Hitchcock, Gu și colab. pe Dimensiune efectivă :
… În matematică, dimensiunea efectivă este o modificare a dimensiunii Hausdorff și a altor dimensiuni fractale care plasează într-un cadru de teorie a calculabilității …
Mi s-a părut interesant (deși „nu sunt expert”) videoclipul introductiv al lui E. Mayordomo „Dimensiunea fractală eficientă în complexitatea calculațională și teoria informației algoritmice” (sau hârtie ).
Vezi și: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, „Geometria fractală a claselor de complexitate”
Răspuns
O aplicație de fractali în analiza documentelor a fost propusă în
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., „O nouă abordare a analizei documentelor bazată pe semnătura fractală modificată”, Analiza și recunoașterea documentelor, 1995., Proceedings of the Third International Conference on, vol.2, nr., Pp.567.570 vol.2, 14-16 august 1995 doi: 10.1109 / ICDAR.1995.601960
Iată rezumatul:
Abordarea propusă se bazează pe semnătura fractală modificată. În loc de abordările tradiționale care necesită mult timp (abordări de sus în jos și de jos în sus) în care sunt necesare operații iterative pentru a sparge un document în blocuri pentru a extrage structura sa geometrică (aspect), această nouă abordare poate împărți un document în blocuri într-un singur Etapa. Această abordare poate fi utilizată pentru procesarea documentelor cu complexitate geometrică ridicată. Au fost efectuate experimente pentru a demonstra noua abordare propusă pentru procesarea documentelor
Doi ani mai târziu, au publicat o versiune extinsă a jurnalului:
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, „Semnătura fractală modificată (MFS): O nouă abordare a analizei documentelor pentru achiziționarea automată a cunoștințelor”, Tranzacții IEEE privind cunoașterea și ingineria datelor, vol. 9, nr. 5, pp. 747-762, septembrie-octombrie 1997
Aici se află ultimul articol.
Răspuns
o parte a provocării din acest domeniu este că pare să nu existe o definiție formală / matematică strictă a termenului „fractal” . inițial așa cum a fost inventat de Mandelbrot în 1975, a avut o interpretare geometrică informală, dar este acum văzută ca fiind mai generală, de exemplu aplicarea diferitelor obiecte matematice importante create / descoperite înainte de a uni principiile / proprietățile fractalelor au fost recunoscute, cum ar fi praf Cantor sau triunghiul Sierpinsky sau chiar funcția Weierstrauss .
desigur ca în aceste exemple un algoritm pentru a desena fractali are proprietăți de complexitate fractală. totuși, există o legătură mult mai profundă între fractali și algoritmi (poate fundamentali?), așa cum s-a descoperit în legăturile dintre calculele fractale și indecidibilitate (poate două fețe ale aceluiași fenomen?).
o alternativă este să luați în considerare sisteme de funcții iterate strâns legate . de exemplu, încercați
- Geometria fractală, mașinile Turing și recurențele de divizare și cucerire [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (vol. 28, nr. 3-4, 1994, p. 405-423)
Aceste rezultate arată că pentru fiecare mașină Turing există un set fractal care poate fi văzut, într-un anumit sens, ca codificare geometrică a complementului limbajului acceptat de mașină. Se poate construi un model geometric de calcul bazat pe fractale, care este universal din punct de vedere al calculului. În al doilea rând, analizăm rezultatele care arată cum geometria fractală poate fi folosită în mod fructuos pentru a rezolva recurențele de împărțire și cucerire. Un algoritm recursiv posedă auto-similitudine temporală și există o legătură naturală cu obiecte spațiale auto-similare (imagini fractale). Această abordare oferă un mod nou și gênerai de a rezolva astfel de recurențe divizate și cucerite.
- Probleme nedecidabile în geometria fractală S. Dube, Complex Systems 7 (1993) 423-444
În această lucrare , se stabilește o relație între teoria clasică a calculului și geometria fractală. Sistemele de funcții iterate sunt utilizate ca instrumente pentru definirea fractalelor. Se arată că două întrebări despre sistemele de funcții iterate sunt indecidabile: pentru a testa dacă atragătorul unui anumit sistem de funcții iterat și a unui anumit segment de linie se intersectează și pentru a testa dacă un anumit sistem de funcții iterat este complet deconectat.