再帰は、オブジェクトの自己相似性（特定の問題の表現）を利用して、オブジェクトの定量的測定（出力）を生成します。いくつかのアルゴリズム（自己相似性を利用）。アルゴリズムが動作する対象の測定可能な情報のフラクタルとしてアルゴリズムを表現することはできるか。

フラクタルの研究で使用されたツールは、アルゴリズムの再帰的な複雑さの下限または上限の明確な例を提供しましたか？

私は次のような例と参照を探しています。アルゴリズムはフラクタルとして扱うことができ、フラクタルに関するツールを使用して、アルゴリズムに関する結果を証明できます。

追加したばかり Walsh変換またはシェルピンスキー三角形変換が完全に線形であることが示されている場合、シェルピンスキー三角形のいくつかの本質的なプロパティを再定義する必要がありますか？ http://en.wikipedia.org/wiki/Walsh_matrix

コメント

  • IIUC、あなたは尋ねています："フラクタルの研究で使用されるツールは、アルゴリズムの複雑さの下限/上限を証明するために使用されましたか？"。それが起こりそうな理由をさらに詳しく説明し、最初の段落をより詳細に説明することをお勧めします。多くのフラクタルは再帰的に定義され、自己相似構造を持っていますが、'一方が他方を暗示しているとは思いません。オブジェクトの再帰的定義は' tはそれがフラクタルであり、フラクタルを再帰的に定義する必要がないことを意味します'。 'ここで情報がどのように機能するかわかりません。
  • ちなみに、"アルゴリズムの再帰的な複雑さ"。アルゴリズムの複雑さという通常の概念以外の何かを意味しますか？ ps：読みやすくするために質問を少し編集しました。編集内容をロールバックしてください。
  • JeffE 'の回答はに近いようです。なぜそのようなフレームワークが不可能なのか。
  • Jeff 'の回答からそれがどのように続くのかわかりません。 ps：より一般的には、実際のRAMモデルは計算可能な分析へのアプローチの1つです。計算可能分析の多くの専門家の意見では、分析に不可欠な制限を処理する能力がなく、モデルが' tは、実際の実数の処理方法に対応しています。 Ker-I Ko、Mark Braverman、…によるフラクタルの計算可能性/複雑性に関する論文があります。ところで、ヴァイラウフの本の第9章には、興味があればさまざまなモデルの比較があります。
  • ' close 'はここでは相対的な用語です。 'からヒントを得ています。ほとんどすべての興味深いフラクタルは計算不可能です'。ただし、フィードバックを含めると、質問についても何かがわかるようです。

回答

Blum、Shub、およびSmaleは、計算のリアルRAMモデルで、マンデルブロ集合のメンバーシップが決定不能であることを証明しました（ いくつかの新興サークルでは BSSモデルとして知られています）。

高レベルの引数は1文の長さです。RealRAMの計算可能な集合は半代数集合の可算集合であるため、その境界はハウスドルフ次元1ですが、マンデルブロ集合の境界はハウスドルフ次元です。 2.同じ議論により、実際のRAMモデルではほとんどすべての興味深いフラクタルは計算不可能です。

回答

Lutz、Mayordomo、Hitchcock、Gu他の作品を見ることができます。 on 有効次元：

…数学では、有効次元はハウスドルフ次元やその他のフラクタル次元を修正したものです。計算可能性理論の設定で…

興味深いと思いました（私は専門家ではありませんが）E。マヨルドモの紹介ビデオ「計算の複雑さとアルゴリズム情報理論における有効なフラクタル次元」（または関連する論文）。

参照： John M. Hitchcock、Jack H. Lutz、Elvira Mayordomo、「複雑性クラスのフラクタル幾何学」

回答

ドキュメント分析でのフラクタルの適用が提案されています

Tang、YY;ホンマ; Xiaogang Mao; Dan Liu; Suen、C.Y。、「修正されたフラクタル署名に基づく文書分析への新しいアプローチ」、文書分析と認識、1995年。、第3回国際会議議事録、vol.2、no。、pp.567,570 vol.2、1995年8月14-16日doi：10.1109 / ICDAR.1995.601960

要約は次のとおりです：

提案されたアプローチは、修正されたフラクタル署名に基づいています。ドキュメントをブロックに分割して幾何学的（レイアウト）構造を抽出するために反復操作が必要な時間のかかる従来のアプローチ（トップダウンおよびボトムアップアプローチ）の代わりに、この新しいアプローチでは、ドキュメントを1つのブロックに分割できます。ステップ。このアプローチは、高い幾何学的複雑性を持つ文書を処理するために使用できる。提案されたドキュメント処理の新しいアプローチを証明するための実験が行われました

2年後、拡張ジャーナルバージョンを公開しました：

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、no。 5、pp。747-762、1997年9月から10月

ここに後者の論文があります。

回答

この分野での課題の一部は、「フラクタル」。もともとは1975年にマンデルブロによって造られたもので、非公式の幾何学的解釈がありましたが、現在ではより一般的なものと見なされています。 カントールダストやシェルピンスキーの三角形など、フラクタルの/プロパティが認識されました。 ワイエルシュトラス関数。これらの例のように、フラクタルを描くアルゴリズムにはフラクタル複雑性の特性がある。ただし、フラクタル計算と決定不能性（同じ現象の2つの面？）の間のリンクで明らかにされているように、フラクタルとアルゴリズム（おそらく基本的？）の間にははるかに深い関係があるようです。

1つの代替手段は密接に関連する反復関数システムを検討してください。例：

これらの結果は、すべてのチューリングマシンに、マシンが受け入れる言語の補数を幾何学的にエンコードしていると特定の意味で表示できるフラクタルセットが存在することを示しています。フラクタルを使った計算の幾何学的モデルを構築することができる。第二に、フラクタル幾何学がどのように効果的に用いられるかを示す結果を調査することである。再帰的アルゴリズムは時間的自己相似性を持ち、フラクタル画像と呼ばれる空間的自己類似オブジェクトとの自然な接続が存在する。このアプローチは、そのような分割統治法の再発を解決する新しい一般的な方法を生み出します。

この論文では、古典的な計算理論とフラクタル幾何学の間の関係が確立されます。 Iterated Function Systemsはフラクタルを定義するためのツールとして使われている。反復関数システムに関する2つの質問が決定不能であることが示されています。特定の反復関数システムのアトラクタと特定の線分が交差するかどうかをテストすることと、特定の反復関数システムが完全に切断されているかどうかをテストすることです。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です