Rekursiossa hyödynnetään jonkin objektin itse samankaltaista luonnetta (jokin tietyn ongelman esitys) tuottaakseen objektille jonkin kvantitatiivisen mittarin (tuotoksen) jokin algoritmi (hyödyntämällä itse samanlaista luonnetta).
Voiko algoritmeja edustaa fraktaaleina (tällainen esitys ei ole mahdollista, ei ole ilmeistä eikä kuinka esityksen tulisi olla, jos sellainen on olemassa) joistakin mitattavissa olevista tiedoista algoritmista, jolla algoritmi toimii?
Onko fraktaalien tutkimuksessa käytetyt työkalut tarjonneet valaisevia esimerkkejä ala- tai ylärajoista algoritmien rekursiiviselle monimutkaisuudelle?
Etsin esimerkkejä ja viitteitä siitä, onko algoritmeja voidaan käsitellä fraktaaleina, ja fraktaaleja koskevilla työkaluilla voidaan todistaa algoritmien tulokset.
juuri lisätty Olisiko meidän pakko määritellä uudelleen Sierpinski-kolmion olennainen ominaisuus, jos Walsh-muunnoksen tai Sierpinski-kolmion muunnoksen osoitetaan olevan täysin lineaarinen? http://en.wikipedia.org/wiki/Walsh_matrix
Kommentit
- IIUC, kysyt: ” onko fraktaalien tutkimuksessa käytettyjä työkaluja käytetty osoittamaan algoritmien monimutkaisuuden ala- / ylärajat? ”. Haluat ehkä laajentaa tarkemmin sitä, miksi luulet sen olevan todennäköistä, ja selittää ensimmäinen kappale tarkemmin. Monet fraktaalit on määritelty rekursiivisesti ja niillä on itsensä kaltainen rakenne, mutta en usko, että yksi viittaa toiseen: objektin rekursiivinen määritelmä ei ’ t tarkoittaa, että se on fraktaali ja fraktaalia ’ ei tarvitse määritellä rekursiivisesti. En ’ näe, miten tieto tulee esiin tässä.
- Muuten, en ole varma, mitä tarkoitat ” algoritmien rekursiivinen monimutkaisuus ”. Tarkoitatko jotain muuta kuin tavalliset algoritmien monimutkaisuuden käsitteet? ps: Muokatin kysymystä hieman helpottamaan lukemista. Voit palata muokkaukseeni.
- JeffE ’ vastaus näyttää olevan lähellä miksi tällainen kehys ei ehkä ole mahdollista.
- En ole varma, miten se seuraa Jeffin ’ vastauksesta. ps: Yleisesti ottaen todellinen RAM-malli on yksi lähestymistavoista laskettavissa olevaan analyysiin. Monien laskettavissa olevien analyysien asiantuntijoiden mielestä se ei ole kovin hyvä malli, varsinkaan käytännön näkökulmasta, koska sillä ei ole kykyä käsitellä rajoituksia, mikä on välttämätöntä analyysille, ja malli ei ’ t vastaavat sitä, miten käsittelemme reaalilukuja käytännössä. Ker-I Ko, Mark Braverman, … ovat kirjoittaneet fraktaalien laskettavuudesta / monimutkaisuudesta. Weirauch-kirjan BTw, kappale 9 vertaa eri malleja, jos olet kiinnostunut.
- ’ sulje ’ on tässä suhteellinen termi. Otan vihjeen ’ melkein jokainen mielenkiintoinen fraktaali on laskematon ’. Palautteesi sisällyttäminen näyttää kuitenkin sanovan jotain myös kysymyksestä.
Vastaa
Blum, Shub ja Smale osoitti, että jäsenyys Mandelbrot-sarjassa on ratkaisematon laskennan todellisessa RAM-mallissa ( tunnetaan joissakin alkupiireissä nimellä BSS-malli ).
Korkean tason argumentti on yhden lauseen pituinen: Mikä tahansa Real RAM -laskettava joukko on puolialgebraalisten joukkojen laskettava unioni, joten sen rajalla on Hausdorff-ulottuvuus 1, mutta Mandelbrot-joukon rajalla on Hausdorff-ulottuvuus 2. Samalla argumentilla melkein jokainen mielenkiintoinen fraktaali on laskematon todellisessa RAM-mallissa.
Vastaus
Voit tutustua Lutzin, Mayordomon, Hitchcockin, Gu ym. päällä Tehokas ulottuvuus :
… Matematiikassa tehokas ulottuvuus on Hausdorff-ulottuvuuden ja muiden fraktaali-ulottuvuuksien muunnos, joka sijoittaa se laskettavuuden teoria-asetuksessa …
Pidin mielenkiintoisesta (vaikka en ole asiantuntija) E. Mayordomon esittelyvideo ”Laskennallisen monimutkaisuuden ja algoritmisen informaatioteorian tehokas fraktaaliulottuvuus” (tai siihen liittyvä -artikkeli ).
Katso myös: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, ”Monimutkaisuusluokkien fraktaaligeometria”
vastaus
Fraktaalien käyttöä asiakirjan analysoinnissa on ehdotettu julkaisussa
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., ”Uusi lähestymistapa asiakirjaanalyysiin, joka perustuu modifioituun fraktaaliallekirjoitukseen”, Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, vol.2, no., S.567,570 vol.2, 14.-16.8.1995. doi: 10.1109 / ICDAR.1995.601960
Tässä on tiivistelmä:
Ehdotettu lähestymistapa perustuu modifioituun fraktaalin allekirjoitukseen. Aikaa vievien perinteisten lähestymistapojen (ylhäältä alas ja alhaalta ylöspäin suuntautuvien lähestymistapojen) sijaan, joissa iteratiiviset toiminnot ovat tarpeen asiakirjan hajottamiseksi lohkoiksi sen geometrisen (asettelun) rakenteen purkamiseksi, tämä uusi lähestymistapa voi jakaa asiakirjan lohkoiksi vain yhdessä askel. Tätä lähestymistapaa voidaan käyttää erittäin geometristen asiakirjojen käsittelyssä. Kokeiluja on tehty todistamaan ehdotettu uusi lähestymistapa asiakirjojen käsittelyyn.
Kaksi vuotta myöhemmin he julkaisivat laajennetun päiväkirjaversion:
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, ”Modified Fractal Signature (MFS): New Approach to Document Analysis for Automatic Knowledge Acquisition”, IEEE Transactions on Knowledge and Data Engineering, voi. 9, ei. 5, s. 747-762, syyskuu-lokakuu 1997
Tässä on jälkimmäinen paperi.
vastaus
osa haastetta tällä alueella näyttää siltä, että termille ”fraktaali” . alun perin Mandelbrot keksi vuonna 1975, sillä oli epävirallinen geometrinen tulkinta, mutta sitä pidetään nyt yleisempänä, esimerkiksi soveltamalla sekalaisiin tärkeisiin matemaattisiin kohteisiin, jotka on luotu / löydetty ennen periaatteiden yhdistämistä / fraktaalien ominaisuudet tunnistettiin, kuten kantorin pöly tai Sierpinsky-kolmio tai jopa Weierstrauss-funktio .
tietysti, koska näissä esimerkeissä fraktaalien piirtämisalgoritmilla on fraktaalin monimutkaisuusominaisuudet. fraktaalien ja algoritmien välillä näyttää kuitenkin olevan paljon syvempi yhteys (ehkä perustavanlaatuinen?), joka paljastuu fraktaalilaskelmien ja päättämättömyyden (ehkä samojen ilmiöiden kaksi kasvoa?) välisessä yhteydessä.
yksi vaihtoehto on ota huomioon läheisesti liittyvät iteroidut toimintojärjestelmät . esim. kokeile
- Fraktaaligeometria, Turingin koneet ja jakamisen ja valloittamisen toistumiset [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (28. osa, nro 3-4, 1994, s. 405-423)
Nämä tulokset osoittavat, että jokaiselle Turingin koneelle on olemassa fraktaalisarja, jota voidaan tietyssä mielessä tarkastella geometrisesti koodaavana koneen hyväksymän kielen täydennystä. Voidaan rakentaa fraktaalipohjainen geometrinen laskentamalli, joka on laskennallisesti universaali. Toiseksi tutkimme tuloksia, jotka osoittavat, kuinka fraktaaligeometriaa voidaan hedelmällisesti käyttää jakamaan ja valloittamaan -toistumisten ratkaisemiseen. Rekursiivisella algoritmilla on ajallinen itsesamankaltaisuus ja on luonnollinen yhteys itseään vastaaviin paikkatietokohteisiin (fraktaalikuvat). Tämä lähestymistapa antaa uuden ja gênerai-tavan ratkaista tällaiset jakavat ja valloita -esittelyt.
- Undecidable Problems in Fractal Geometry S.Dube, Complex Systems 7 (1993) 423-444
Tässä artikkelissa , suhde klassisen laskentateorian ja fraktaaligeometrian välillä on vakiintunut. Iteroituja funktiojärjestelmiä käytetään työkaluina fraktaalien määrittelyssä. Osoitetaan, että kahta iteroitua funktiojärjestelmää koskevaa kysymystä ei voida ratkaista: testata, ristikkääkö tietyn iteroidun toimintojärjestelmän ja tietyn linjasegmentin vetovoima, ja testata, onko tietty iteroitu funktiojärjestelmä täysin kytketty irti.