La ricorsione utilizza una natura auto-simile di un oggetto (una rappresentazione del problema dato) per produrre una misura quantitativa (output) sulloggetto attraverso alcuni algoritmi (utilizzando la natura auto-simile).
Si possono rappresentare gli algoritmi come frattali (una tale rappresentazione non è possibile non è ovvio né come dovrebbe essere la rappresentazione se ne esiste una) di alcune informazioni misurabili delloggetto su cui lavora lalgoritmo?
Gli strumenti utilizzati nello studio dei frattali hanno fornito degli esempi illuminanti per i limiti inferiore o superiore per la complessità ricorsiva degli algoritmi?
Sto cercando esempi e riferimenti sulla falsariga se gli algoritmi possono essere trattati come frattali e gli strumenti sui frattali possono essere utilizzati per dimostrare i risultati sugli algoritmi.
appena aggiunto Saremmo costretti a ridefinire alcune proprietà essenziali del triangolo di Sierpinski se la trasformata di Walsh o la trasformata del triangolo di Sierpinski si dimostrasse completamente lineare? http://en.wikipedia.org/wiki/Walsh_matrix
Commenti
- IIUC, stai chiedendo: ” sono stati utilizzati strumenti utilizzati nello studio dei frattali per dimostrare i limiti inferiore / superiore sulla complessità degli algoritmi? “. Potresti voler espandere di più il motivo per cui pensi che sia probabile e spiegare il primo paragrafo in modo più dettagliato. Molti frattali sono definiti in modo ricorsivo e hanno una struttura auto-simile, ma non ‘ penso che uno implichi laltro: la definizione ricorsiva di un oggetto non ‘ Significa che è un frattale e che un frattale non ‘ deve essere definito ricorsivamente. Non ‘ non vedo come entrano in gioco le informazioni qui.
- A proposito, non sono sicuro di cosa intendi con ” complessità ricorsiva degli algoritmi “. Intendi qualcosa di diverso dalle solite nozioni di complessità degli algoritmi? ps: ho modificato un po la domanda per renderla più facile da leggere, sentiti libero di ripristinare la mia modifica.
- JeffE ‘ la risposta sembra essere vicina a perché un tale framework potrebbe non essere possibile.
- Non sono sicuro di come ciò derivi dalla risposta di Jeff ‘. ps: Più in generale il modello RAM reale è uno degli approcci allanalisi computabile. Secondo lopinione di molti esperti di analisi computabile, non è un modello molto buono, in particolare dal punto di vista pratico, in quanto manca della capacità di affrontare i limiti che è essenziale per lanalisi e il modello non ‘ t corrisponde a come trattiamo i numeri reali nella pratica. Ci sono articoli di Ker-I Ko, Mark Braverman, … sulla computabilità / complessità dei frattali. A proposito, il capitolo 9 del libro Weirauch ha un confronto di diversi modelli se sei interessato.
- ‘ chiudi ‘ è un termine relativo qui. Prendo spunto da ‘ quasi tutti i frattali interessanti sono non numerabili ‘. Tuttavia, includere il tuo feedback sembra dire qualcosa anche sulla domanda.
Risposta
Blum, Shub e Smale ha dimostrato che lappartenenza al set di Mandelbrot è indecidibile nel modello RAM reale di calcolo ( noto in alcuni circoli nuovi come modello BSS ).
Largomento di alto livello è lungo una frase: qualsiasi insieme calcolabile di RAM reale è lunione numerabile di insiemi semi-algebrici, quindi il suo confine ha dimensione di Hausdorff 1, ma il confine dellinsieme di Mandelbrot ha dimensione di Hausdorff 2. Con lo stesso argomento, quasi tutti i frattali interessanti sono non numerabili nel modello con RAM reale.
Risposta
Puoi dare unocchiata al lavoro di Lutz, Mayordomo, Hitchcock, Gu et al. su Dimensione effettiva :
… In matematica, la dimensione effettiva è una modifica della dimensione di Hausdorff e di altre dimensioni frattali che pone in un contesto di teoria della computabilità …
Ho trovato interessante (anche se non sono un esperto) il video introduttivo di E. Mayordomo “Effective Fractal Dimension in Computational Complexity and Algorithmic Information Theory” (o il relativo paper ).
Vedi anche: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, “The Fractal Geometry of Complexity Classes”
Risposta
Unapplicazione dei frattali nellanalisi dei documenti è stata proposta in
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., “Un nuovo approccio allanalisi dei documenti basata sulla firma frattale modificata”, Document Analysis and Recognition, 1995., Atti della Terza Conferenza Internazionale del, vol.2, no., Pp.567,570 vol.2, 14-16 agosto 1995 doi: 10.1109 / ICDAR.1995.601960
Ecco labstract:
Lapproccio proposto si basa sulla firma frattale modificata. Invece degli approcci tradizionali che richiedono tempo (approcci top-down e bottom-up) in cui sono necessarie operazioni iterative per suddividere un documento in blocchi per estrarne la struttura geometrica (layout), questo nuovo approccio può dividere un documento in blocchi in uno solo passo. Questo approccio può essere utilizzato per elaborare documenti con elevata complessità geometrica. Sono stati condotti esperimenti per dimostrare il nuovo approccio proposto per lelaborazione dei documenti
Due anni dopo, hanno pubblicato una versione estesa della rivista:
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, “Modified Fractal Signature (MFS): un nuovo approccio allanalisi dei documenti per lacquisizione automatica della conoscenza”, IEEE Transactions on Knowledge and Data Engineering, vol. 9, n. 5, pp. 747-762, settembre-ottobre 1997
Ecco il secondo documento.
Risposta
parte della sfida in questarea è che sembra non esserci una definizione formale / matematica rigorosa del termine “frattale” . originariamente come coniato da Mandelbrot nel 1975 aveva uninterpretazione geometrica informale ma ora è visto come più generale, ad esempio si applica a oggetti matematici importanti creati / scoperti prima dellunificazione dei principi / sono state riconosciute proprietà dei frattali, come Cantor dust o il triangolo di Sierpinsky o persino il Funzione Weierstrauss .
ovviamente come in questi esempi un algoritmo per disegnare frattali ha proprietà di complessità frattale. tuttavia sembra esserci una connessione molto più profonda tra frattali e algoritmi (forse fondamentale?) come scoperto nei collegamenti tra calcoli frattali e indecidibilità (forse due facce dello stesso fenomeno?).
unalternativa è quella di considera i sistemi di funzioni iterati strettamente correlati. ad esempio, prova
- Geometria frattale, macchine di Turing e ricorrenze divide et impera [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (vol. 28, no 3-4, 1994, p. 405-423)
Questi risultati mostrano che per ogni macchina di Turing esiste un insieme frattale che può essere visto, in un certo senso, come codificare geometricamente il complemento del linguaggio accettato dalla macchina. Si può costruire un modello geometrico di calcolo basato sui frattali che sia computazionalmente universale. In secondo luogo esaminiamo i risultati che mostrano come la geometria frattale possa essere utilizzata fruttuosamente per risolvere le ricorrenze divide et impera. Un algoritmo ricorsivo possiede unauto-similarità temporale e cè una connessione naturale con oggetti spaziali auto-simili (immagini frattali). Questo approccio offre un modo nuovo e generoso di risolvere tali ricorrenze divide et impera.
- Problemi indecidibili nella geometria frattale S. Dube, Complex Systems 7 (1993) 423-444
In questo documento , viene stabilita una relazione tra la teoria classica del calcolo e la geometria frattale. I sistemi di funzioni iterati sono usati come strumenti per definire i frattali. È dimostrato che due domande sui sistemi di funzioni iterate sono indecidibili: per verificare se lattrattore di un dato sistema di funzioni iterate e un dato segmento di linea si intersecano e per verificare se un dato sistema di funzioni iterato è totalmente disconnesso.