재귀는 객체의 자체 유사한 특성 (주어진 문제의 일부 표현)을 활용하여 객체에 대한 정량적 측정 (출력)을 생성합니다. 일부 알고리즘 (자체 유사 특성 활용).
알고리즘이 작동하는 물체의 측정 가능한 정보의 프랙탈로 알고리즘을 표현할 수 있습니까 (이러한 표현은 불가능하며 표현이 존재하는 경우 어떻게 표현되어야하는지)?
프랙탈 연구에 사용 된 도구가 알고리즘의 반복적 복잡성에 대한 하한 또는 상한에 대한 조명 예제를 제공 했습니까?
나는 다음 여부에 대한 예제와 참고 자료를 찾고 있습니다. 알고리즘은 프랙탈로 취급 될 수 있으며 프랙탈에 대한 도구는 알고리즘에 대한 결과를 증명하는 데 사용될 수 있습니다.
방금 추가됨 Walsh Transform 또는 Sierpinski 삼각형 변환이 완전히 선형으로 표시되면 Sierpinski 삼각형의 필수 속성을 재정의해야합니까? http://en.wikipedia.org/wiki/Walsh_matrix
댓글
- IIUC, 질문 : " 프랙탈 연구에 사용 된 도구가 알고리즘의 복잡성에 대한 하한 / 상한을 증명하는 데 사용 되었습니까? ". 그럴 가능성이 있다고 생각하는 이유를 더 확장하고 첫 번째 단락을 더 자세히 설명 할 수 있습니다. 많은 프랙탈이 재귀 적으로 정의되고 자체적으로 유사한 구조를 가지고 있지만 ' 하나가 다른 것을 의미한다고 생각하지 않습니다. 객체의 재귀 적 정의가 ' 그것이 프랙탈이고 프랙탈이 재귀 적으로 정의 될 필요가 없음을 의미하는 것은 아닙니다. ' ' 여기에서 정보가 어떻게 작동하는지 알 수 없습니다.
- 그런데 " 알고리즘의 반복적 인 복잡성 ". 알고리즘의 복잡성에 대한 일반적인 개념 이외의 것을 의미합니까? 추신 : 읽기 쉽도록 질문을 약간 수정했습니다. 언제든지 수정을 롤백 할 수 있습니다.
- JeffE '의 답변은 왜 그러한 프레임 워크가 불가능할 수 있는지.
- 제프 '의 대답에서 이것이 어떻게 따르는 지 잘 모르겠습니다. 추신 :보다 일반적으로 실제 RAM 모델은 계산 가능한 분석에 대한 접근 방식 중 하나입니다. 계산 가능한 분석의 많은 전문가들은 분석에 필수적인 한계를 처리 할 수있는 능력이 부족하고 모델이 그렇지 않기 때문에 특히 실용적인 관점에서 매우 좋은 모델이 아닙니다. ' t는 실제로 실수를 다루는 방법에 해당합니다. Ker-I Ko, Mark Braverman, … 프랙탈의 계산 가능성 / 복잡성에 대한 논문이 있습니다. Btw, ch.9 Weirauch 책에는 관심이있는 경우 여러 모델을 비교합니다.
- ' close '는 여기서 상대적인 용어입니다. 저는 ' 거의 모든 흥미로운 프랙탈을 계산할 수 없습니다 '에서 단서를 얻습니다. 그러나 귀하의 의견을 포함하면 질문에 대해서도 언급하는 것 같습니다.
답변
Blum, Shub 및 Smale은 계산의 실제 RAM 모델 에서 Mandelbrot 세트의 멤버십을 결정할 수 없음 을 증명했습니다 ( 일부 신생 서클 에서는 BSS 모델 로 알려져 있습니다.
높은 수준의 주장은 한 문장입니다. 모든 실제 RAM 계산 가능 집합은 반 대수 집합의 가산 조합이므로 해당 경계에는 Hausdorff 차원 1이 있지만 Mandelbrot 집합의 경계에는 Hausdorff 차원이 있습니다. 2. 동일한 주장으로, 실제 RAM 모델에서는 거의 모든 흥미로운 프랙탈을 계산할 수 없습니다.
답변
Lutz, Mayordomo, Hitchcock, Gu 등의 작업을 살펴볼 수 있습니다. on 유효 치수 :
… 수학에서 유효 치수는 Hausdorff 치수 및 기타 프랙탈 치수를 수정하여 계산 가능성 이론 설정에서 …
재미있는 것을 발견했습니다 (전문가는 아니지만) E. Mayordomo의 소개 동영상 “Computational Complexity and Algorithmic Information Theory의 효과적인 프랙탈 차원” (또는 관련 논문 )
참조 : John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, “복잡성 클래스의 프랙탈 기하학”
답변
문서 분석에서 프랙탈 적용이 제안되었습니다.
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; 수엔, C.Y., “수정 된 프랙탈 서명에 기반한 문서 분석에 대한 새로운 접근 방식”, Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, vol.2, no., pp.567,570 vol.2, 1995 년 8 월 14-16 일 doi : 10.1109 / ICDAR.1995.601960
추상은 다음과 같습니다.
제안 된 접근 방식은 수정 된 프랙탈 서명을 기반으로합니다. 기하학적 (레이아웃) 구조를 추출하기 위해 문서를 블록으로 나누기 위해 반복 작업이 필요한 시간 소모적 인 기존 접근 방식 (하향식 및 상향식 접근 방식) 대신이 새로운 접근 방식은 문서를 하나의 블록으로 분할 할 수 있습니다. 단계. 이 접근 방식은 기하학적 복잡성이 높은 문서를 처리하는 데 사용할 수 있습니다. 문서 처리에 대해 제안 된 새로운 접근 방식을 증명하기위한 실험이 수행되었습니다.
2 년 후 그들은 확장 저널 버전을 출판했습니다.
Yuan Y. Tang, Hong Ma, Dihua Xi, Xiaogang Mao, Ching Y. Suen, “MFS (Modified Fractal Signature) : 자동 지식 획득을위한 문서 분석에 대한 새로운 접근 방식,”IEEE Transactions on Knowledge and Data Engineering, vol. 9, 아니. 5, pp. 747-762, 1997 년 9 월 -10 월
여기 는 후자의 논문입니다.
답변
이 영역의 문제 중 일부는 “프랙탈”. 원래는 1975 년 Mandelbrot 에 의해 만들어졌으며 비공식적 인 기하학적 해석이 있었지만 이제는 원칙을 통합하기 전에 생성 / 발견 된 기타 중요한 수학적 개체에 적용하는 것과 같이 더 일반적으로 보입니다. / 프랙탈의 속성 (예 : 캔터 더스트 또는 Sierpinsky 삼각형 또는 Weierstrauss 함수 .
물론이 예제 에서처럼 프랙탈을 그리는 알고리즘은 프랙탈 복잡성 속성을 가지고 있습니다. 그러나 프랙탈 계산과 결정 불가능 (동일한 현상의 두면) 사이의 연결에서 밝혀진 것처럼 프랙탈과 알고리즘 (아마 근본적인 것일까 요?) 사이에는 훨씬 더 깊은 연결이있는 것 같습니다.
한 가지 대안은 다음과 같습니다. 밀접하게 관련된 반복 함수 시스템 을 고려하십시오. 예 :
- 프랙탈 지오메트리, 튜링 머신 및 분할 및 정복 반복 [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (vol. 28, no 3-4, 1994, p. 405-423)
이 결과는 모든 Turing 머신에 대해 특정 의미에서 볼 수있는 프랙탈 세트가 있음을 보여줍니다.이 프랙탈 세트는 머신에서 허용하는 언어의 보완을 기하학적으로 인코딩합니다. 계산적으로 보편적 인 프랙탈 기반의 기하학적 계산 모델을 만들 수 있습니다. 두 번째로 우리는 프랙탈 기하학이 분할 정복 반복을 해결하는 데 어떻게 유익하게 사용될 수 있는지 보여주는 결과를 조사합니다. 재귀 알고리즘은 시간적 자기 유사성을 가지고 있으며 공간적 자기 유사 객체 (프랙털 이미지)와 자연스럽게 연결됩니다. 이 접근 방식은 이러한 분할 및 정복 재발을 해결하는 새롭고 간결한 방법을 제공합니다.
- 프랙탈 기하학의 결정 불가능한 문제 S. Dube, Complex Systems 7 (1993) 423-444
이 문서에서 , 계산의 고전 이론과 프랙탈 기하학 사이의 관계가 확립됩니다. 반복 함수 시스템은 프랙탈을 정의하는 도구로 사용됩니다. 반복 함수 시스템에 대한 두 가지 질문은 결정할 수없는 것으로 나타났습니다. 주어진 반복 함수 시스템과 주어진 선분의 어 트랙터가 교차하는지 테스트하고 주어진 반복 함수 시스템이 완전히 분리되었는지 테스트하는 것입니다.