Rekurze využívá určitou podobnost objektu (určité vyjádření daného problému) k vytvoření kvantitativní míry (výstupu) na objektu prostřednictvím nějaký algoritmus (využívající vlastní podobnou povahu).

Může někdo reprezentovat algoritmy jako fraktály (takové znázornění není možné, není zřejmé, ani jak by mělo být znázorněno, pokud existuje) nějaké měřitelné informace o objektu, na kterém algoritmus pracuje?

Poskytly nástroje použité při studiu fraktálů nějaké osvětlovací příklady pro dolní nebo horní mez pro rekurzivní složitost algoritmů?

Hledám příklady a odkazy v duchu toho, zda algoritmy lze považovat za fraktály a k prokázání výsledků algoritmů lze použít nástroje o fraktálech.

právě přidáno Byli bychom nuceni předefinovat některé základní vlastnosti Sierpinského trojúhelníku, pokud se ukáže, že Walshova transformace nebo Sierpinského trojúhelníková transformace jsou plně lineární? http://en.wikipedia.org/wiki/Walsh_matrix

Komentáře

  • IIUC, ptáte se: “ byly nástroje použité při studiu fraktálů použity k prokázání dolních / horních mezí složitosti algoritmů? „. Možná budete chtít více rozvinout, proč si myslíte, že je to pravděpodobné, a vysvětlit první odstavec podrobněji. Mnoho fraktálů je definováno rekurzivně a má podobnou strukturu, ale nemyslím si, že jeden implikuje druhý: rekurzivní definice objektu není ‚ t znamená, že se jedná o fraktál a fraktál není nutné ‚ definovat rekurzivně. Nechápu ‚, jak zde vstupují informace.
  • Mimochodem, nejsem si jistý, co myslíš tím “ rekurzivní složitost algoritmů „. Máte na mysli něco jiného než obvyklé představy o složitosti algoritmů? ps: Trochu jsem otázku upravil, aby bylo snazší číst, klidně stáhni svoji editaci.
  • JeffE ‚ odpověď se zdá být blízká proč takový rámec nemusí být možný.
  • Nejsem si jistý, jak to vyplývá z odpovědi Jeffa ‚. ps: Obecněji je skutečný model RAM jedním z přístupů k vypočítatelné analýze. Podle názoru mnoha odborníků na vypočítatelnou analýzu nejde o velmi dobrý model, zejména z praktického hlediska, protože mu chybí schopnost vyrovnat se s limity, které jsou pro analýzu zásadní, a tento model ‚ t odpovídá tomu, jak v praxi zacházíme se skutečnými čísly. Existují práce od Ker-I Ko, Marka Bravermana, … o vypočítatelnosti / složitosti fraktálů. Btw, kapitola 9 knihy Weirauch obsahuje srovnání různých modelů, pokud máte zájem.
  • ‚ zavřít ‚ je zde relativní pojem. Beru vodítko z ‚ téměř každý zajímavý fraktál je nepočítatelný ‚. Zdá se však, že zahrnutí vaší zpětné vazby také říká něco o otázce.

Odpověď

Blum, Shub a Smale dokázal, že členství v sadě Mandelbrot je nerozhodné v modelu skutečné RAM výpočtu ( známý v některých povýšených kruzích jako model BSS ).

Argument na vysoké úrovni má délku jedné věty: Jakákoli vypočítatelná množina Real RAM je počítatelným spojením poloalgebraických množin, takže její hranice má Hausdorffovu dimenzi 1, ale hranice sady Mandelbrot má Hausdorffovu dimenzi 2. Stejným argumentem je téměř každý zajímavý fraktál v modelu reálné RAM nepočítatelný .

Odpověď

Můžete se podívat na práci Lutze, Mayordomo, Hitchcocka, Gu a kol. na Efektivní dimenze :

… V matematice je efektivní dimenzí modifikace Hausdorffovy dimenze a dalších fraktálních dimenzí, které umisťují to v nastavení teorie vypočítatelnosti …

Považoval jsem za zajímavé (i když nejsem odborník) úvodní video E. Mayordomo „Efektivní fraktální dimenze ve výpočetní složitosti a teorii algoritmických informací“ (nebo související příspěvek ).

Viz také: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, „The Fractal Geometry of Complexity Classes“

Odpověď

Aplikace fraktálů v analýze dokumentů byla navržena v

Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y.„Nový přístup k analýze dokumentů založený na modifikovaném fraktálovém podpisu,“ Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, sv. 2, č., Str. 567 570 sv. 2, 14. – 16. doi: 10.1109 / ICDAR.1995.601960

Zde je abstrakt:

Navrhovaný přístup je založen na upraveném fraktálním podpisu. Místo časově náročných tradičních přístupů (přístupy shora dolů a zdola nahoru), kde jsou nutné iterační operace k rozdělení dokumentu na bloky, aby se získala jeho geometrická (rozložení) struktura, může tento nový přístup rozdělit dokument na bloky pouze v jednom krok. Tento přístup lze použít ke zpracování dokumentů s vysokou geometrickou složitostí. Byly provedeny experimenty k prokázání navrhovaného nového přístupu ke zpracování dokumentů.

O dva roky později vydali rozšířenou verzi deníku:

Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, „Modifikovaný fraktální podpis (MFS): Nový přístup k analýze dokumentů pro automatické získávání znalostí,“ IEEE Transactions on Knowledge and Data Engineering, sv. 9, č. 5, str. 747–762, září – říjen 1997

Zde je druhý příspěvek.

Odpověď

součástí výzvy v této oblasti je, že se zdá, že neexistuje striktní formální / matematická definice pojmu „fraktál“ . původně vytvořený společností Mandelbrot v roce 1975 měla neformální geometrickou interpretaci, ale nyní je považována za obecnější, například při aplikaci na různé důležité matematické objekty vytvořené / objevené před sjednocujícími principy / vlastnosti fraktálů byly rozpoznány, například Cantorův prach nebo Sierpinsky trojúhelník nebo dokonce Weierstraussova funkce .

Samozřejmě stejně jako v těchto příkladech má algoritmus pro kreslení fraktálů vlastnosti fraktální složitosti. zdá se však, že existuje mnohem hlubší souvislost mezi fraktály a algoritmy (možná zásadní?), jak je odhaleno ve vazbách mezi fraktálními výpočty a nerozhodnutelností (možná dvě tváře stejných jevů?).

Jednou alternativou je zvažte úzce související iterované funkční systémy . např. zkuste

Tyto výsledky ukazují, že pro každý Turingův stroj existuje fraktální množina, kterou lze v určitém smyslu považovat za geometricky kódující doplněk jazyka akceptovaného strojem. Lze vytvořit fraktální geometrický model výpočtu, který je výpočetně univerzální. Zadruhé zkoumáme výsledky, které ukazují, jak lze fraktální geometrii plodně využít k řešení opakování rozděl a panuj. Rekurzivní algoritmus má časovou sebepodobnost a existuje přirozené spojení s prostorovými sebepodobnými objekty (fraktální obrazy). Tento přístup přináší nový a gênerai způsob řešení takových opakovaných návratů rozděl a panuj.

V tomto příspěvku , je vytvořen vztah mezi klasickou teorií výpočtu a fraktální geometrií. Iterované funkční systémy se používají jako nástroje k definování fraktálů. Ukazuje se, že dvě otázky týkající se systémů s iterovanými funkcemi jsou nerozhodnutelné: otestovat, zda se přitahují přitažlivost daného systému s iterovanými funkcemi a daného segmentu čáry, a otestovat, zda je daný systém s iterovanými funkcemi zcela odpojen.

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *