Rekursja wykorzystuje pewną samopodobną naturę obiektu (pewną reprezentację danego problemu) do wytworzenia ilościowej miary (wyniku) na obiekcie poprzez jakiś algorytm (wykorzystujący podobną naturę).

Czy można przedstawić algorytmy jako fraktale (taka reprezentacja nie jest możliwa, nie jest oczywista ani jak powinna wyglądać reprezentacja, jeśli taka istnieje) jakiejś mierzalnej informacji o obiekcie, nad którym pracuje algorytm?

Czy narzędzia użyte w badaniu fraktali dostarczyły jakichś pouczających przykładów dolnych lub górnych granic rekurencyjnej złożoności algorytmów?

Szukam przykładów i odniesień wzdłuż linii, czy algorytmy mogą być traktowane jako fraktale, a narzędzia dotyczące fraktali mogą służyć do potwierdzania wyników dotyczących algorytmów.

właśnie dodano Czy bylibyśmy zmuszeni przedefiniować jakąś istotną właściwość trójkąta Sierpińskiego, gdyby okazało się, że transformata Walsha lub transformata trójkąta Sierpińskiego są w pełni liniowe? http://en.wikipedia.org/wiki/Walsh_matrix

Komentarze

  • IIUC, pytasz: ” czy narzędzia używane w badaniu fraktali zostały użyte do udowodnienia dolnej / górnej granicy złożoności algorytmów? „. Możesz szerzej wyjaśnić, dlaczego uważasz, że jest to prawdopodobne, i bardziej szczegółowo wyjaśnić pierwszy akapit. Wiele fraktali jest zdefiniowanych rekurencyjnie i ma podobną strukturę, ale nie ' nie sądzę, że jeden implikuje drugie: rekurencyjna definicja obiektu nie ' t oznacza, że jest to fraktal, a fraktal nie ' nie musi być definiowany rekurencyjnie. Nie ' nie rozumiem, jak informacje wchodzą w grę.
  • Nawiasem mówiąc, nie jestem pewien, co masz na myśli, mówiąc o ” rekursywna złożoność algorytmów „. Czy masz na myśli coś innego niż zwykłe pojęcie złożoności algorytmów? ps: nieco zredagowałem pytanie, aby było łatwiejsze do czytania, nie krępuj się cofnąć zmiany.
  • Odpowiedź Jeffa ' wydaje się być bliska dlaczego taka struktura może nie być możliwa.
  • Nie jestem pewien, jak to wynika z odpowiedzi Jeffa '. ps: Mówiąc bardziej ogólnie, prawdziwy model pamięci RAM jest jednym z podejść do analizy obliczeniowej. W opinii wielu ekspertów w dziedzinie analizy obliczeniowej nie jest to model bardzo dobry, szczególnie z praktycznego punktu widzenia, ponieważ brakuje mu umiejętności radzenia sobie z granicami niezbędnymi do analizy, a model nie ' t odpowiada temu, jak w praktyce radzimy sobie z liczbami rzeczywistymi. Istnieją prace Ker-I Ko, Marka Bravermana … na temat obliczalności / złożoności fraktali. Przy okazji, rozdział 9 książki Weirauch zawiera porównanie różnych modeli, jeśli jesteś zainteresowany.
  • ' close ' jest tutaj pojęciem względnym. Biorę przykład z ', prawie każdy interesujący fraktal jest nieobliczalny '. Jednak dołączenie Twojej opinii wydaje się również mówić coś o pytaniu.

Odpowiedź

Blum, Shub i Smale udowodnił, że członkostwo w zbiorze Mandelbrota jest nierozstrzygalne w modelu rzeczywistej pamięci RAM obliczeń ( znany w niektórych początkujących kręgach jako model BSS ).

Argument wysokiego poziomu ma długość jednego zdania: każdy zbiór obliczalny Real RAM jest policzalną sumą zbiorów półalgebraicznych, więc jego granica ma wymiar Hausdorffa 1, ale granica zbioru Mandelbrota ma wymiar Hausdorffa 2. Zgodnie z tym samym argumentem, prawie każdy interesujący fraktal jest nieobliczalny w modelu z rzeczywistą pamięcią RAM.

Odpowiedź

Możesz zapoznać się z pracami Lutza, Mayordomo, Hitchcocka, Gu i in. on Wymiar efektywny :

… W matematyce wymiar efektywny to modyfikacja wymiaru Hausdorffa i innych wymiarów fraktalnych, które umieszczają w kontekście teorii obliczalności …

Znalazłem interesujące (chociaż nie jestem ekspertem) wideo wprowadzające E. Mayordomo „Effective Fractal Dimension in Computational Complexity and Algorithmic Information Theory” (lub pokrewny artykuł ).

Zobacz także: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, „The Fractal Geometry of Complexity Classes”

Answer

Zastosowanie fraktali w analizie dokumentów zostało zaproponowane w

Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., „Nowe podejście do analizy dokumentów w oparciu o zmodyfikowany podpis fraktalny”, Analiza i rozpoznawanie dokumentów, 1995., Proceedings of the Third International Conference on, vol. 2, no., Str. 567,570 vol. 2, 14-16 sierpnia 1995 doi: 10.1109 / ICDAR.1995.601960

Oto streszczenie:

Proponowane podejście jest oparte na zmodyfikowanej sygnaturze fraktalnej. Zamiast czasochłonnych tradycyjnych podejść (podejścia odgórne i oddolne), w których konieczne są operacje iteracyjne, aby podzielić dokument na bloki w celu wyodrębnienia jego struktury geometrycznej (układu), to nowe podejście może podzielić dokument na bloki tylko w jednym krok. To podejście można zastosować do przetwarzania dokumentów o dużej złożoności geometrycznej. Przeprowadzono eksperymenty, aby udowodnić proponowane nowe podejście do przetwarzania dokumentów.

Dwa lata później opublikowali rozszerzoną wersję czasopisma:

Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, „Modified Fractal Signature (MFS): A New Approach to Document Analysis for Automatic Knowledge Acquisition”, IEEE Transactions on Knowledge and Data Engineering, vol. 9, nie. 5, s. 747-762, wrzesień-październik 1997 r.

Tutaj jest ten ostatni artykuł.

Odpowiedź

Wydaje się, że częścią wyzwania w tym obszarze jest brak ścisłej formalnej / matematycznej definicji terminu „fraktal” . pierwotnie, jak ukuł Mandelbrot w 1975 r., miał nieformalną interpretację geometryczną, ale obecnie jest postrzegany jako bardziej ogólny, np. stosowany do różnych ważnych obiektów matematycznych utworzonych / odkrytych przed ujednoliceniem zasad / zostały rozpoznane właściwości fraktali, takie jak pył Kantora lub trójkąt Sierpinskiego , a nawet Funkcja Weierstrauss .

oczywiście, tak jak w tych przykładach, algorytm rysowania fraktali ma fraktalne właściwości złożoności. wydaje się jednak, że istnieje znacznie głębszy związek między fraktalami i algorytmami (może fundamentalny?), co ujawniają powiązania między obliczeniami fraktali a nierozstrzygalnością (może dwie twarze tego samego zjawiska?).

jedną z alternatyw jest rozważ ściśle powiązane iterowane systemy funkcyjne . np. spróbuj

Te wyniki pokazują, że dla każdej maszyny Turinga istnieje zbiór fraktali, który można w pewnym sensie postrzegać jako geometrycznie kodujący dopełnienie języka akceptowanego przez maszynę. Można zbudować oparty na fraktali geometryczny model obliczeniowy, który jest obliczeniowo uniwersalny. Po drugie, przyjrzymy się wynikom, które pokazują, w jaki sposób geometria fraktalna może być owocnie wykorzystana do rozwiązywania powtórzeń typu „dziel i rządź”. Algorytm rekurencyjny posiada samopodobieństwo czasowe i istnieje naturalny związek z samopodobieństwem przestrzennym (obrazy fraktalne). Takie podejście daje nowy i lepszy sposób rozwiązywania takich problemów typu „dziel i rządź”.

W tym artykule ustalono związek między klasyczną teorią obliczeń a geometrią fraktali. Iterowane systemy funkcji są używane jako narzędzia do definiowania fraktali. Wykazano, że dwa pytania dotyczące iterowanych systemów funkcji są nierozstrzygalne: sprawdzić, czy atraktor danego iterowanego systemu funkcji przecina się z danym segmentem linii oraz sprawdzić, czy dany iterowany system funkcji jest całkowicie odłączony.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *