問題タブ [discrete-mathematics]

リストのリストを生成 (または印刷、私は気にしません)可能な限り最小限のコード行で、サイズ Nのパスカルの三角形を生成します!

これが私の試みです（トリックを使用してpython 2.6で118文字）：

説明：

• リスト内包表記の最初の要素 (長さが 0 の場合) は[1]
• 次の要素は次の方法で取得されます。
• 前のリストを取得して 2 つのリストを作成します。1 つは先頭に 0 をパディングし、もう 1 つは最後にパディングします。
  • たとえば、2 番目のステップでは、取り[1]、作成[0,1]し、[1,0]
• 2 つの新しいリストを要素ごとに合計する
  • たとえば、新しいリスト[(0,1),(1,0)]を作成し、合計でマップします。
• n回繰り返すだけです。

使用法 (かなりの印刷で、実際には code-golf xD から):

出力：

以下を計算する必要がある友人がいます。

完全なグラフ Kn (k<=13) には、k*(k-1)/2 個のエッジがあります。各エッジは 2 つの方法で方向付けられるため、2^[(k*(k-1))/2] の異なるケースになります。

彼女は計算する必要があるP[A !-> B && C !-> D] - P[A !-> B]*P[C !-> D]

X !-> Y は「X から Y への経路がない」ことを意味し、P[ ] は確率です。

したがって、ブルートフォース アルゴリズムは 2^[(k*(k-1))/2] 個の異なるグラフをすべて調べることであり、それらは完全であるため、各グラフで A、B の 1 つのセットを考慮するだけで済みます。 C、D は対称性によるものです。

次に、P[A !-> B] は、「ノード 1 と 2 の間にパスがないグラフの数」をグラフの総数で割った値、つまり 2^[(k*(k-1))/2] として計算されます。

ブルートフォース法は K8 までの Mathematica で機能しますが、彼女には K9、K10... K13 までが必要です。

明らかに、ケースで最短経路を見つける必要はありません。最短経路があるかどうかを見つけたいだけです。

最適化の提案はありますか? (これは典型的な Project Euler の問題のように聞こえます)。

例：

最小グラフ K4 には 4 つの頂点があり、6 つのエッジがあります。したがって、4 つの頂点 A、B、C、および D にラベルを付ける場合、エッジに方向を割り当てる方法は 2^6 = 64 通りあります。

一部のグラフでは、A から B へのパスはありません (それらの X としましょう)。他のグラフでは、C から D へのパスはありません (Y としましょう)。しかし、一部のグラフでは、A から B への経路がなく、同時に C から D への経路もありません。これらは W です。

だからP[A !-> B]=X/64、P[C !-> D]=Y/64そしてP[A !-> B && C !-> D] = W/64。

アップデート：

• A、B、C、D は 4 つの異なる頂点であるため、少なくとも K4 が必要です。
• DIRECTED グラフを扱っていることに注意してください。したがって、UT 行列を使用した通常の表現では十分ではありません。
• Mathematica には、有向グラフのノード間の距離を求める関数があります (無限大を返す場合、パスはありません)。ただし、パスまたはいいえ。

2つの2進数の乗算にはn^2の時間がかかりますが、数値の2乗はどういうわけかより効率的に行うことができます。（nはビット数です）どうしてそれができるでしょうか？

それとも不可能ですか？これは狂気です！

私の大学の離散数学コースでは、教師が学生にアッカーマン関数を示し、紙の上で関数を開発するよう学生に割り当てます。

再帰最適化のベンチマークであることに加えて、アッカーマン関数には実際の用途がありますか?

私の問題は(g^x) mod p、JavaScript ですばやく計算することです。^指数modはモジュロ演算です。すべての入力は非負の整数で、x約 256 ビットあり、p2048 ビットの素数であり、g最大 2048 ビットの場合があります。

JavaScript でこれを実行できるソフトウェアのほとんどは、JavaScript BigInt ライブラリ ( http://www.leemon.com/crypto/BigInt.html ) を使用しているようです。このライブラリでこのようなサイズの累乗を 1 回実行すると、遅いブラウザ (Firefox 3.0 と SpiderMonkey) で約 9 秒かかります。少なくとも 10 倍高速なソリューションを探しています。二乗と乗算 (二乗によるべき乗、http://en.wikipedia.org/wiki/Exponentiation_by_squaring ) を使用するという明白なアイデアは、2048 ビットの数値には遅すぎます: 最大 4096 の乗算が必要です。

ブラウザのアップグレードはオプションではありません。別のプログラミング言語を使用することはオプションではありません。番号を Web サービスに送信することはできません。

実装されているより高速な代替手段はありますか?

更新:以下の outis の回答に記載されている記事http://www.ccrwest.org/gordon/fast.pdfで推奨されているように、いくつかの追加の準備 (つまり、数百乗の事前計算) を行うことで、2048-最大で 354 のモジュラ乗算のみを使用するビット モジュラべき乗。(従来の平方乗算法は非常に遅く、最大 4096 の剰余乗算を使用します。) そうすることで、累乗剰余を Firefox 3.0 では 6 倍、Google Chrome では 4 倍高速化します。4096/354 の完全な高速化が得られない理由は、BigInt の累乗剰余アルゴリズムが、モンゴメリー削減 ( http://en.wikipedia.org/wiki/Montgomery_reduction )を使用するため、2 乗乗算よりも既に高速であるためです。 .

更新: BigInt のコードから始めて、手動で最適化された (およびインライン化された) カラツバ乗算 ( http://en.wikipedia.org/wiki/Karatsuba_algorithm ) の 2 つのレベルを実行する価値があるように思われ、その後でベース 32768 O( n^2) 乗算は BigInt で実装されます。これにより、2048 ビット整数の乗算が 2.25 倍高速化されます。残念ながらモジュロ演算は速くなりません。

更新: http://www.lirmm.fr/arith18/papers/hasenplaugh-FastModularReduction.pdf で定義されている修正された Barrett リダクションと、からつばの乗算と事前計算の累乗 ( http://www.ccrwest.org/gordon/で定義されている) を使用します。 fast.pdf )、Firefox 3.0 では、1 回の乗算に必要な時間を 73 秒から 12.3 秒に短縮できます。これは私ができる最善のようですが、それでも遅すぎます。

更新: Flash Player の ActionScript 2 (AS2) インタープリターは、Firefox 3.0 の JavaScript インタープリターよりも遅いように見えるため、使用する価値がありません: Flash Player 9 の場合は 4.2 倍遅く、Flash Player の場合は10、2.35倍遅いようです。数値計算における ActionScript2 と ActionScript3 (AS3) の速度の違いを知っている人はいますか?

更新: Flash Player 9 の ActionScript 3 (AS3) インタープリターは、JavaScript int Firefox 3.0 とほぼ同じ速度であるため、使用する価値はありません。

更新: Flash Player 10 の ActionScript 3 (AS3) インタープリターは、 の代わりに を使用し、intの代わりに を使用すると、Firefox 3.0 の JavaScript インタープリターよりも最大 6.5 倍高速になります。少なくとも、2048 ビットの大きな整数の乗算では 2.41 倍高速でした。そのため、可能な場合は Flash Player 10 で実行して、AS3 でべき乗剰余を実行する価値があるかもしれません。これは、Google Chrome の JavaScript インタープリターである V8 よりもまだ遅いことに注意してください。さまざまなプログラミング言語と JavaScript の実装の速度比較については、http://ptspts.blogspot.com/2009/10/javascript-and-actionscript-performance.htmlを参照してください。NumberVector.<int>Array

Update: There is a very fast Java solution, which can be called from the browser's JavaScript if the Java plugin is installed. The following solution is about 310 times faster than the pure JavaScript implementation using BigInt.

Can anyone translate this code to Silverlight (C#)?

私は基本的な大学の微積分以上の数学の授業を受けていません。しかし、プログラミングの過程で、ブログや読書から多くの数学や計算機科学を学びました。私はまともな数学の心を持っていると心から信じています。たとえば、プロジェクトオイラーを楽しんで成功しています。

私は飛び込んで、いくつかのクールな数学、特に離散数学、集合論、グラフ理論、数論、組み合わせ論、圏論、ラムダ計算などを学び始めたいと思っています。これまでの私の印象は、これらを受け入れる準備が整っているということです概念レベルではありますが、私は数学の言語と記号に非常に苦労しています。私はただ「言語を話す」ことはしません、そして私はそれを学ぼうとしていますが、私は行くのが非常に遅いです。数式や用語の重い段落を1つでも処理するには、数時間かかる場合があります。そして、ええ、私は用語と定義を調べることができますが、それは私が学ぼうとしていることの理論的な単純さを非常に曖昧にする非常に厄介なプロセスです。

中断したところに戻って、中級レベルの数学の教科書を手に入れ、その考え方を身につけるために演習に真剣に時間を費やさなければならないのではないかと本当に恐れています。しかし、これは驚くほど退屈に聞こえるので、他の誰かがこれについて何かアイデアや経験を持っているのだろうかと思いました。

10 進数 (基数 10) では、1/30.33333 の繰り返しにしか近似できません。

近似値としてしか表現できない 2 進法に相当する数は?

Michael Feather の SCNA トーク「Self-Education and the Craftsman」を見て触発されたので、離散数学が役立つことが証明されているソフトウェア開発の実際の例について聞くことに興味があります。

こんにちは私はRSA暗号システムをセットアップしようとしています。d個の選択された素数を除くすべての値がありp=1889ます：q=2003、、、、、n=3783667phi=3779776e= 61

私はdを見つけて行き詰まりました誰かが私がそれを理解するのを手伝ってくれるでしょうか？

RSA暗号システムのセットアップ

• 2つの大きな異なる素数pとqが選択され、n = pqとΦ(n) = (p − 1)(q − 1)が計算されます。

• 整数は、の逆数が計算eされるように選択されます。gcd(Φ(n), e) = 1d = e^(−1)ZΦ(n)

  ed≡1（modΦ（n））。

• その後、番号、、、pおよびqはΦ(n)破棄されます。

• ペア(e, n)は公開暗号化キーとして公開されます
• 番号dは秘密の復号化キーです。