A rekurzió az objektum valamilyen önmagához hasonló jellegét (az adott probléma valamilyen ábrázolását) használja, hogy az objektumon keresztül valamilyen kvantitatív mértéket (kimenetet) hozzon létre valamilyen algoritmus (az önmagához hasonló természet felhasználásával).

Képes-e algoritmusokat fraktálként ábrázolni (az ilyen ábrázolás nem lehetséges, nem nyilvánvaló, és hogy az ábrázolásnak miként kell lennie, ha van ilyen) az objektum néhány mérhető információjára, amelyen az algoritmus működik?

A fraktálok tanulmányozásához használt eszközök szolgáltattak-e megvilágító példákat az alsó vagy felső határokra az algoritmusok rekurzív komplexitása érdekében?

Példákat és hivatkozásokat keresek annak mentén, hogy az algoritmusokat fraktálként lehet kezelni, és a fraktálokról szóló eszközökkel igazolhatók az algoritmusok eredményei.

most hozzáadva Kénytelenek lennénk újradefiniálni a Sierpinski-háromszög néhány alapvető tulajdonságát, ha a Walsh-transzformáció vagy a Sierpinski-háromszög transzformációja teljesen lineárisnak bizonyul? http://en.wikipedia.org/wiki/Walsh_matrix

Megjegyzések

  • IIUC, azt kérdezi: ” a fraktálok tanulmányozásához használt eszközöket alkalmaztak-e az algoritmusok bonyolultságának alsó / felső határainak bizonyítására? “. Érdemes bővebben kitérnie arra, hogy miért gondolja ezt valószínűnek, és magyarázza el részletesebben az első bekezdést. Sok fraktál rekurzívan definiált, és önmagukhoz hasonló felépítésű, de nem hiszem, hogy az egyik implikálja a másikat: egy objektum rekurzív meghatározása nem ‘ t azt jelenti, hogy ez egy fraktál, és a fraktált nem kell rekurzívan definiálni. Nem ‘ nem látom, hogy itt hogyan játszanak szerepet az információk.
  • Egyébként nem vagyok biztos benne, mit értesz ” algoritmusok rekurzív bonyolultsága “. Valami mást ért, mint az algoritmusok bonyolultságának szokásos elképzeléseit? ps: A kérdést kissé szerkesztettem az olvasás megkönnyítése érdekében, nyugodtan gördítsd vissza a szerkesztésemet.
  • Úgy tűnik, hogy JeffE ‘ válasza közel áll a miért nem lehetséges egy ilyen keretrendszer.
  • Nem tudom, hogy következik ez Jeff ‘ válaszából. ps: Általánosabban a valódi RAM-modell az egyik megközelítés a kiszámítható elemzéshez. Számos szakértő véleménye szerint a számítható elemzésben ez nem túl jó modell, különösen gyakorlati szempontból, mivel hiányzik az elemzéshez elengedhetetlen korlátok kezelésének képessége, és a modell nem ‘ t megfelel annak, ahogyan a valós számokkal a gyakorlatban foglalkozunk. Ker-I Ko, Mark Braverman, … a fraktálok kiszámíthatóságáról / összetettségéről írtak. A Weirauch könyv Btw, 9. fejezete összehasonlítja a különböző modelleket, ha érdekel.
  • ‘ bezárás ‘ itt relatív kifejezés. A jelet ‘ -től veszem, szinte minden érdekes fraktál kiszámíthatatlan ‘. Úgy tűnik azonban, hogy a visszajelzései is mondanak valamit a kérdésről.

Válasz

Blum, Shub és Smale bebizonyította, hogy a Mandelbrot készlet tagsága eldönthetetlen a számítás Real RAM modelljében ( néhány induló körben BSS modellként ismert ).

A magas szintű argumentum egy mondat hosszú: Bármely Real RAM kiszámítható halmaz a félig algebrai halmazok megszámlálható uniója, így annak határa Hausdorff 1. dimenzióval rendelkezik, de a Mandelbrot halmaz határának Hausdorff dimenziója van. 2. Ugyanezzel az érvvel szinte minden érdekes fraktál ki nem számolható a valós RAM modellben.

Válasz

Megnézheti Lutz, Mayordomo, Hitchcock, Gu et al. a tényleges dimenzión :

… A matematikában az effektív dimenzió a Hausdorff dimenzió és más fraktál dimenziók módosítása, amely elhelyezi egy számíthatóság-elméleti beállításban …

Érdekesnek találtam (bár nem vagyok szakértő) E. Mayordomo bemutatkozó videója “Hatékony fraktál dimenzió a számítási komplexitásban és az algoritmikus információelméletben” (vagy a kapcsolódó cikk ).

Lásd még: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, “A komplexitási osztályok fraktálgeometriája”

válasz

Fraktálok alkalmazását javasolták a dokumentumelemzésben:

Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., “A módosított fraktál aláíráson alapuló dokumentumelemzés új megközelítése”, Dokumentumelemzés és -felismerés, 1995., Proceedings of the Third International Conference on, 2. kötet, sz., 567 570. kötet, 1995. augusztus 14-16. doi: 10.1109 / ICDAR.1995.601960

Íme az absztrakt:

A javasolt megközelítés módosított fraktál-aláíráson alapszik. Az időigényes hagyományos megközelítések (felülről lefelé és alulról felfelé történő megközelítés) helyett, ahol iteratív műveletekre van szükség a dokumentum blokkokra bontásához annak geometriai (elrendezési) struktúrájának kibontásához, ez az új megközelítés a dokumentumot csak egy blokkokra oszthatja lépés. Ez a megközelítés nagy geometriai összetettségű dokumentumok feldolgozására használható. Kísérleteket végeztek a dokumentum-feldolgozás javasolt új megközelítésének igazolására.

Két évvel később egy kiterjesztett folyóirat-verziót tettek közzé:

Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, “Módosított fraktál aláírás (MFS): új megközelítés a dokumentumelemzéshez az automatikus ismeretszerzéshez”, IEEE tranzakciók a tudás és az adatmérnöki munkákról, vol. 9. sz. 5, 747–762. Oldal, 1997. szeptember – október.

Itt található az utóbbi.

Válasz

A kihívás része ezen a területen úgy tűnik, hogy nincs szigorú formai / matematikai definíció a “fraktál” . eredetileg a Mandelbrot által 1975-ben megalkotott formában informális geometriai értelmezést kapott, de ma már általánosabbnak tekintik, például olyan fontos matematikai objektumokra vonatkozik, amelyeket az elvek egyesítése előtt hoztak létre / fedeztek fel / felismerték a fraktálok tulajdonságait, például kántorpor vagy a Sierpinsky háromszög , vagy akár a Weierstrauss függvény .

természetesen mivel ezekben a példákban a fraktálok rajzolására szolgáló algoritmusnak fraktál komplexitási tulajdonságai vannak. úgy tűnik azonban, hogy a fraktálok és az algoritmusok (talán fundamentális?) között sokkal mélyebb kapcsolat van, amint azt a fraktálszámítások és a határozatlanság (esetleg ugyanazon jelenségek két arca?) közötti összefüggések fedik fel.

az egyik alternatíva vegye figyelembe a szorosan kapcsolódó iterált függvényrendszereket . pl. próbálkozz

Ezek az eredmények azt mutatják, hogy minden Turing-gépnél létezik egy fraktálkészlet, amelyet bizonyos értelemben úgy tekinthetünk, mint ahogyan a gép által elfogadott nyelv kiegészítését geometrikusan kódolja. Felépíthető egy fraktál alapú geometriai számítási modell, amely számítási szempontból univerzális. Másodszor felmérjük azokat az eredményeket, amelyek megmutatják, hogy a fraktálgeometria hogyan lehet eredményesen felhasználni a megosztani és meghódítani visszatérések megoldására. A rekurzív algoritmus időbeli én-hasonlósággal rendelkezik, és természetes kapcsolat van a térbeli önmagához hasonló tárgyakkal (fraktál képek). Ez a megközelítés új és gênerai módszert ad az ilyen megosztani és meghódítani elõfordulók megoldására.

Ebben a cikkben , kapcsolat alakul ki a klasszikus számítási elmélet és a fraktálgeometria között. Az iterált funkciós rendszereket használják a fraktálok meghatározására. Kimutatták, hogy az iterált függvényrendszerekkel kapcsolatos két kérdés eldönthetetlen: annak tesztelése, hogy egy adott iterált függvényrendszer és egy adott vonalszakasz vonzója keresztezi-e egymást, és annak tesztelése, hogy egy adott iterált funkciós rendszer teljesen le van-e kapcsolva.

Vélemény, hozzászólás?

Az email címet nem tesszük közzé. A kötelező mezőket * karakterrel jelöltük