私はオンラインでConcreteMathsの内容をちらっと見ていました。私は少なくとも言及された機能とトリックのほとんどを聞いたことがありますが、特別な番号に関するセクション全体があります。これらの数には、スターリング数、オイラー数、調和数などが含まれます。今、私はこれらの奇妙な数字のいずれにも遭遇したことがありません。それらは計算問題をどのように助けますか？それらは一般的にどこで使用されますか？
1221 次
7 に答える
5
調和数はほとんどどこにでも現れます！音楽のハーモニー、クイックソートの分析... スターリング数 (第 1 種および第 2 種) は、さまざまな組み合わせ論および分割の問題で発生します。オイラー数もいくつかの場所で発生しますが、最も顕著なのは多対数関数の順列と係数です。
于 2009-05-23T15:57:25.137 に答える
4
あなたが言及した数字の多くは、アルゴリズムの分析に使用されます。コードにこれらの数値が含まれていない場合もありますが、コードの実行にかかる時間を見積もりたい場合は、これらの数値が必要になります。あなたはあなたのコードにもそれらを見るかもしれません。これらの数値のいくつかは、組み合わせ論に関連しており、何かが起こり得る方法の数を数えています。
可能性を列挙する必要があるため、可能性がいくつあるかを知るだけでは不十分な場合があります。 進行中のクヌースのTAOCPの第4巻では、必要なアルゴリズムを提供しています。
数値積分問題の一部として フィボナッチ数を使用する例を次に示します。
調和数は対数の離散アナログであるため、対数が微分方程式で現れるのと同じように、調和数は微分方程式で現れます。これは、調和数に関連する調和平均の物理的応用の例です。動作中の調和数の多くの例、特に「それは調和世界です」の章 については、本「ガンマ」を参照してください。
于 2009-05-23T16:28:58.193 に答える
3
これらの特別な数値は、多くの点で計算問題に役立ちます。例えば：
2つの数値のGCDを計算するプログラムが最も長い時間を要する時期を知りたい場合は、2つの連続するフィボナッチ数を試してください。
多数の階乗の概算を求めていますが、階乗プログラムに時間がかかりすぎています。スターリングの近似を使用してください。
素数をテストしていますが、一部の数値では常に間違った答えが返されます。フェルマーの素数テストを使用している可能性があります。その場合、カーマイケル数が原因です。
私が考えることができる最も一般的な一般的なケースは、ループです。ほとんどの場合、あるタイプの構文を使用してループを指定します(start;stop;step)。その場合、関連する数値のプロパティを使用することで実行時間を短縮できる可能性があります。
たとえば、ループ内でnが大きい場合、1からnまでのすべての数値を合計すると、IDを使用するよりも明らかに遅くなりますsum = n*(n + 1)/2。
このような例はたくさんあります。それらの多くは暗号化されており、情報システムのセキュリティはこのようなトリックに依存することがあります。また、パフォーマンスの問題やメモリの問題にも役立ちます。数式を知っていると、他のこと、つまり実際に気になっていることを計算するためのより高速で効率的な方法を見つけることができるからです。
詳細については、ウィキペディアをチェックするか、プロジェクトオイラーを試してみてください。あなたはかなり速くパターンを見つけ始めるでしょう。
于 2009-05-23T16:24:08.163 に答える
2
これらの数のほとんどは、特定の種類の離散構造を数えます (たとえば、スターリング数はサブセットとサイクルを数えます)。このような構造、したがってこれらのシーケンスは、アルゴリズムの分析で暗黙のうちに発生します。
OEIS には、Concrete Math に表示されるほぼすべてのシーケンスをリストした広範なリストがあります。そのリストからの短い要約:
- ゴロムの数列
- 二項係数
- レンコントル数
- スターリング数
- オイラー数
- 超階乗
- ジェノッキナンバーズ
それぞれの配列の OEIS ページを参照して、これらの配列の「プロパティ」に関する詳細情報を取得できます (ただし、それが最も興味がある場合は、正確なアプリケーションではありません)。
また、アルゴリズムの分析におけるこれらのシーケンスの実際の使用法を見たい場合は、Knuth の Art of Computer Programming のインデックスをめくると、これらのシーケンスの「アプリケーション」への参照が多数見つかります。ジョン・D・クックはすでにフィボナッチ数とハーモニック数の応用について言及しました。いくつかの例を次に示します。
スターリングサイクル数は、配列の最大要素を見つける標準アルゴリズムの分析で発生します(TAOCP Sec. 1.2.10): 最大値を見つけるときに、現在の最大値を何回更新する必要がありますか? 要素kの配列で最大値を見つけるときに最大値を更新する必要がある確率は です。このことから、平均して、おおよその更新が必要になることがわかります。np[n][k] = StirlingCycle[n, k+1]/n!Log(n)
ジェノッキ数は、「薄い」BDD の数のカウントに関連して発生します (TAOCP 7.1.4 演習 174 )。
于 2009-05-25T14:55:11.240 に答える
1
あなたが言及した参照から必ずしも魔法の数ではありませんが、それでも-
0x5f3759df
-- 悪名高いマジック ナンバーで、数値の逆平方根を計算するために使用されます。これは、多くの場合 John Carmack の作品に起因する、ニュートンの近似根に適切な最初の推定値を与えることによって行われます。詳細はこちら。
プログラミング関係なくね？:)
于 2009-05-23T16:38:04.597 に答える
0
これはプログラミングに直接関係していますか？確かに関係はありますが、どこまで密接かはわかりません。
e や pi などの特殊な数字がいたるところに出てきます。この二つについて議論する人はいないと思います。Golden_ratioは、アートから他の特殊な数自体まで、驚くべき頻度で表示されます (連続するフィボナッチ数の比率を見てください)。
さまざまな数列や数族が数学の多くの場所に登場するため、プログラミングにも登場します。見るのに美しい場所は、整数シーケンスの百科事典です。
これは経験的なことだと思います。たとえば、何年も前に線形代数を学んだとき、行列の固有値と固有ベクトルについて学びました。さまざまな場所で使用されているのを見るまで、固有値/固有ベクトルの重要性をまったく理解していなかったことを認めます。統計学では、共分散行列からの推定値の不確実性、主成分分析の信頼楕円のサイズと形状、またはマルコフ過程の長期的な状態について何を教えてくれるかという観点からです。最適化であろうと ODE ソルバーであろうと、方法の収束について教えてくれる数値的方法。機械工学では、それらを主な応力とひずみと見なします。
于 2009-05-24T12:29:42.087 に答える
0
于 2009-05-24T19:25:56.883 に答える