A recursão utiliza alguma natureza auto-semelhante de um objeto (alguma representação do problema dado) para produzir alguma medida quantitativa (saída) no objeto por meio algum algoritmo (utilizando a natureza auto-similar).
Pode-se representar algoritmos como fractais (tal representação não é possível, não é óbvia nem como a representação deveria ser se existir) de alguma informação mensurável do objeto em que o algoritmo trabalha?
As ferramentas usadas no estudo de fractais forneceram alguns exemplos esclarecedores para limites inferiores ou superiores para complexidade recursiva de algoritmos?
Estou procurando exemplos e referências ao longo das linhas de algoritmos podem ser tratados como fractais e ferramentas sobre fractais podem ser usadas para provar resultados sobre algoritmos.
recém-adicionado Seríamos compelidos a redefinir alguma propriedade essencial do triângulo de Sierpinski se a transformada de Walsh ou a transformada do triângulo de Sierpinski fosse mostrada como totalmente linear? http://en.wikipedia.org/wiki/Walsh_matrix
Comentários
- IIUC, você está perguntando: ” as ferramentas usadas no estudo de fractais foram usadas para provar limites inferior / superior na complexidade de algoritmos? “. Você pode querer expandir mais sobre por que você acha que isso é provável e explicar o primeiro parágrafo com mais detalhes. Muitos fractais são recursivamente definidos e têm estrutura semelhante, mas eu não ‘ acho que um implica o outro: a definição recursiva de um objeto não ‘ t significa que é um fractal e um fractal não ‘ t precisa ser definido recursivamente. Não ‘ não vejo como as informações entram em jogo aqui.
- A propósito, não tenho certeza do que você quer dizer com ” complexidade recursiva de algoritmos “. Você quer dizer algo diferente das noções usuais de complexidade de algoritmos? ps: Eu editei a pergunta um pouco para torná-la mais fácil de ler, fique à vontade para reverter minha edição.
- JeffE ‘ a resposta parece estar perto de por que tal estrutura pode não ser possível.
- Não tenho certeza de como isso segue a resposta de Jeff ‘. ps: Mais geralmente, o modelo real de RAM é uma das abordagens para a análise computável. Na opinião de muitos especialistas em análise computável, não é um modelo muito bom, especialmente do ponto de vista prático, pois não tem a capacidade de lidar com os limites que são essenciais para a análise e o modelo não ‘ t corresponde a como lidamos com números reais na prática. Existem artigos de Ker-I Ko, Mark Braverman, … sobre computabilidade / complexidade de fractais. A propósito, o capítulo 9 do livro Weirauch tem uma comparação de diferentes modelos, se você estiver interessado.
- ‘ close ‘ é um termo relativo aqui. Pego a sugestão de ‘ quase todo fractal interessante é incomputável ‘. No entanto, incluir seu feedback parece dizer algo sobre a questão também.
Resposta
Blum, Shub e Smale provou que associação no conjunto Mandelbrot é indecidível no modelo RAM real de computação ( conhecido em alguns círculos iniciantes como o modelo BSS ).
O argumento de alto nível tem uma frase: Qualquer conjunto real RAM computável é a união contável de conjuntos semi-algébricos, então seu limite tem dimensão de Hausdorff 1, mas o limite do conjunto de Mandelbrot tem dimensão de Hausdorff 2. Pelo mesmo argumento, quase todo fractal interessante é incomputável no modelo real-RAM.
Resposta
Você pode dar uma olhada no trabalho de Lutz, Mayordomo, Hitchcock, Gu et al. em Dimensão efetiva :
… Em matemática, dimensão efetiva é uma modificação da dimensão de Hausdorff e outras dimensões fractais que colocam em um cenário de teoria da computabilidade …
Achei interessante (embora não seja um especialista) Vídeo introdutivo do E. Mayordomo “Dimensão Fractal Eficaz na Complexidade Computacional e Teoria Algorítmica da Informação” (ou o artigo relacionado).
Veja também: John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo, “The Fractal Geometry of Complexity Classes”
Resposta
Uma aplicação de fractais na análise de documentos foi proposta em
Tang, YY; Hong Ma; Xiaogang Mao; Dan Liu; Suen, C.Y., “Uma nova abordagem à análise documental baseada na assinatura fractal modificada,” Document Analysis and Recognition, 1995., Proceedings of the Third International Conference on, vol.2, no., Pp.567.570 vol.2, 14-16 de agosto de 1995 doi: 10.1109 / ICDAR.1995.601960
Aqui está o resumo:
A abordagem proposta é baseada na assinatura fractal modificada. Em vez das abordagens tradicionais demoradas (abordagens de cima para baixo e de baixo para cima), onde operações iterativas são necessárias para quebrar um documento em blocos para extrair sua estrutura geométrica (layout), esta nova abordagem pode dividir um documento em blocos em apenas um degrau. Essa abordagem pode ser usada para processar documentos com alta complexidade geométrica. Experimentos foram conduzidos para provar a nova abordagem proposta para o processamento de documentos
Dois anos depois, eles publicaram uma versão estendida do jornal:
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, não. 5, pp. 747-762, setembro-outubro de 1997
Aqui está o último artigo.
Resposta
parte do desafio nesta área é que parece não haver uma definição formal / matemática estrita do termo “fractal” . originalmente como cunhado por Mandelbrot em 1975, tinha uma interpretação geométrica informal, mas agora é visto como mais geral, por exemplo, aplicando-se a diversos objetos matemáticos importantes criados / descobertos antes de princípios unificadores / propriedades dos fractais foram reconhecidas, como pó Cantor ou o triângulo de Sierpinsky ou mesmo o Função Weierstrauss .
é claro, como nesses exemplos, um algoritmo para desenhar fractais tem propriedades de complexidade fractal. no entanto, parece haver uma conexão muito mais profunda entre fractais e algoritmos (talvez fundamentais?), conforme descoberto nas ligações entre cálculos fractais e indecidibilidade (talvez duas faces do mesmo fenômeno?).
uma alternativa é considere os sistemas de função iterada estreitamente relacionados . por exemplo, tente
- Geometria fractal, máquinas de Turing e recorrências de divisão e conquista [pdf] S. Dube, Informatique théorique et Applications / Theoietical Informaties and Applications (vol. 28, no 3-4, 1994, p. 405-423)
Esses resultados mostram que para cada máquina de Turing existe um conjunto fractal que pode ser visto, em certo sentido, como codificando geometricamente o complemento da linguagem aceita pela máquina. Pode-se construir um modelo geométrico de computação baseado em fractal que seja computacionalmente universal. Em segundo lugar, examinamos os resultados que mostram como a geometria fractal pode ser usada com sucesso para resolver recorrências de dividir e conquistar. Um algoritmo recursivo possui autossimilaridade temporal e há uma conexão natural com objetos autossimilares espaciais (imagens fractais). Essa abordagem produz uma maneira nova e ampla de resolver essas recorrências de dividir e conquistar.
- Undecidable Problems in Fractal Geometry S. Dube, Complex Systems 7 (1993) 423-444
Neste artigo , uma relação entre a teoria clássica da computação e a geometria fractal é estabelecida. Os Sistemas de Função Iterada são usados como ferramentas para definir fractais. É mostrado que duas questões sobre Sistemas de Função Iterada são indecidíveis: testar se o atrator de um determinado Sistema de Função Iterada e um determinado segmento de linha se cruzam e testar se um determinado Sistema de Função Iterada está totalmente desconectado.