問題タブ [clrs]

これは CLRS 24.4-12 からの演習です (宿題ではなく、CLRS のすべての演習を解決しようとしています)。

b のすべての要素が実数値であり、すべてではないが一部の未知数 xi の指定されたサブセットが整数でなければならない場合に、差分制約の系 Ax ≤ b を解く効率的なアルゴリズムを与えてください。

すべての xi が整数の場合、b = floor(b) とし、Bellman-Ford アルゴリズムを使用して制約グラフの問題を解決するための最短経路を見つけることができますが、xi の一部が整数であり、一部が整数でない場合はどうでしょうか? 整数計画問題に似ていますが、整数計画問題は NP 困難です。この質問は制約が少なく、より効率的なアルゴリズムはありますか?

これがこれを尋ねるのに適切な場所かどうかはわかりません。Cormen page 1056 で、アルゴリズムの実行時間が O(k) で、「k」が単項、つまり k 1 の文字列で表される場合、アルゴリズムの実行時間は 0(n) であり、「n」は入力サイズはビット単位で、"k" が 2 進数で表される場合、n=lg k+1 として、アルゴリズムの実行時間は o(2^n) になります。

したがって、この場合、他の場合の指数関数とは対照的に多項式時間を与えるため、「単項」表現が好まれない理由は疑問です。

コーメンのアルゴリズム入門などでプッシュフローアルゴリズムを読んでいます。

私は以下のように言及されている補題26.20を理解するのに苦労しています：

G =（V、E）をソースsとシンクtを持つフローネットワークとし、fをGのプリフローとします。次に、オーバーフローする頂点uに対して、残りのネットワークGfにuからsへの単純なパスがあります。 。

このリーマのコンテキストを確認するには、次のリンクを参照してください。

http://integrator-crimea.com/ddu0164.html

これを理解するためにあなたの助けを求めてください。

お手数をおかけしますが、よろしくお願いいたします。

「アルゴリズム入門」の第 3 版を読んでいます。「アルゴリズムの分析」セクションの下に、次のように書かれています。

また、データの各ワードのサイズに制限があると仮定します。たとえば、サイズ n の入力を扱う場合、通常、整数は定数 c>=1 に対して c lg n ビットで表されると想定します。各単語が n の値を保持できるように c>=1 である必要があり、個々の入力要素にインデックスを付けることができます。また、c を定数に制限して、単語のサイズが勝手に大きくならないようにします。

ここでの「言葉」という言葉の意味は何ですか？これはデータを「単語」で表現する基準ですか？

コーメンらによるアルゴリズム入門の47ページでこの一節に出くわしました。:

式中の無名関数の数は、漸近表記の出現回数に等しいと理解されます。たとえば、式では次のようになります。

Σ ( i =1 ～n ) O( i )

無名関数 ( iの関数) は 1 つだけです。この式は O(1) + O(2) + ... + O( n )と同じではなく、実際には明確な解釈がありません。

これは何を意味するのでしょうか？

CLRSでは、配列内の i 番目に小さい要素を見つけるため(2/e, page 191, section 9.3)のアルゴリズムの分析は、次の帰納法証明で提示されます。SELECT

アルゴリズムは理解できましたが、証明の 2 つの操作に少し戸惑いました。

質問 1 : 2 行目で、余分な c 項 (第 2 項) はどこから来ましたか? c 項を掛けると(7n/10 + 6)が得られ7cn/10 + 6cます。

質問 2 : 4 行目で、どうやって から9cn/10にたどり着きましたcn + (-cn/10 ...)か? 9 係数はどこに行ったのですか?

これは宿題ではありません

ありがとうございました！

CLRS によるアルゴリズム入門を読んでいます。本は、単純な分割統治行列乗算の擬似コードを示しています。

たとえば、A11 はサイズ n/2 xn/2 の A の部分行列です。著者は、部分行列を表すために新しい行列を作成する代わりに、インデックス計算を使用する必要があることも示唆しているため、次のようにしました。

間違った結果が得られますが、何が間違っているのかわかりません...

この質問は、動的計画法、特にCLRS Pg 362のロッド切断問題に関連しています

全体の最適解には、関連する 2 つの部分問題に対する最適解が組み込まれています。

全体的な最適解は、個々の部分問題に対する最適解を見つけて、何らかの方法でそれらをクラブ化することによって得られます。直感と概念が理解できません。リンク、例はありますか？

ありがとう

CLRS の 264 ページの下部で、著者は、 を取得した後r0 = 17612864、 の最上位 14 ビットがr0ハッシュ値 を生成すると述べていますh(k) = 67。1000011バイナリの67は7ビットなので、なぜ67になるのかわかりません。

編集 教科書では: 例として、 があるとしますk = 123456, p = 14, m = 2^14 = 16384, and w = 32。Knuth の提案を適用して、A を にs/2^32最も近い形式の分数として選択(\sqrt(5) - 1) / 2しますA = 2654435769/2^32。それからk*s = 327706022297664 = (76300 * 2^32) + 17612864、などr1 = 76300 and r0 = 17612864。の最上位 14 ビットがr0値を生成しますh(k)=67。

赤黒木の挿入では、ツリーの黒の高さを変更しないように、常に新しいノードを赤として追加することを選択します。ブラックノードを追加するよりも、これが望ましいのはなぜですか？