問題タブ [clrs]

StackOverflow Podcast のエピソード 57 の推奨事項に基づいて、「コンピューター プログラムの構造と解釈」、「C プログラミング言語」、「Unix プログラミング環境」、および「アルゴリズム入門」を購入しました。基本的なプログラミング スキルを向上させ、いくつかのオープン ソース プロジェクトに貢献し、将来の雇用の見通しを改善したいと考えています。選択したテキストの推奨される読む順序はありますか? また、書籍のどの特定の主題/セクションにもっと注意を払う必要がありますか? ありがとう。

確率 p で 1 を生成し、確率 (1-p) で 0 を生成するバイアス付き乱数ジェネレーターがあります。p の値がわかりません。これを使用して、確率 0.5 で 1 と確率 0.5 で 0 を生成する偏りのない乱数ジェネレーターを作成します。

注: この問題は、Cormen、Leiserson、Rivest、Stein による Introduction to Algorithms の演習問題です。(clrs)

私は宿題として、次のようなアルゴリズム入門演習を与えられました。11.1-3

格納された要素のキーを区別する必要がなく、要素がサテライト データを持つことができる直接アクセス テーブルを実装する方法を提案してください。3 つの辞書操作 (挿入、削除、検索) はすべて O(1) 時間で実行する必要があります。Delete は、キーではなく、削除するオブジェクトへのポインタを引数として取ることを忘れないでください。

Insert は問題ありません。テーブル内の適切な場所にリンク リストを作成し (存在しない場合)、それに要素を追加するだけです。キーが与えられた検索は、キーに一致する要素のいずれかを返すことができるため、テーブル内の一致するリストの先頭を返す必要があることを意味します。

私の問題は削除操作にあります。リンクされたリスト内のノードへのポインターを追加するようにオブジェクトを変更すると、O(1)で削除できますが、オブジェクトを変更できるかどうかはわかりません。指定されたオブジェクトを変更せずにこれを行う方法はありますか?

コンピュータサイエンスの文脈における「祖先」の定義についてのコンセンサスは何であるのか疑問に思います。

アルゴリズム入門、第2版、p。Tree-Successor(x)259奇妙に思われるアルゴリズムの説明があります。ノードxの後継を見つける際に、

[...]ノードxの右側のサブツリーが空で、xに後続のyがある場合、yはxの最も低い祖先であり、その左側の子はxの祖先でもあります。

2キーと子1を持つルートを持つ二分探索木では3、の後続1はその親2です。この場合、xはxの後継子yの左の子です。したがって、本の定義によれば、私が何かを見逃していない限り、xはそれ自体の祖先でなければなりません。

これについての正誤表には何も見つかりませんでした。

私の最後のCLRSの質問で成功したので、ここに別の質問があります。

アルゴリズム入門、第2版、p。501-502では、互いに素な集合のリンクリスト表現が記述されており、各リストメンバーは次の3つのフィールドを維持しています。

• セットメンバー
• nextオブジェクトへのポインタ
• 最初のオブジェクト（セット）に戻るポインタrepresentative。

リンクリストは、単一の「リンク」オブジェクトタイプのみを使用して実装できますが、教科書には、「ヘッド」リンクと「テール」リンクへのポインタを含む補助的な「リンクリスト」オブジェクトが示されています。「テール」へのポインタがあると操作が簡単になるため、小さいセットのリンクをそれに追加し始めるためにUnion(x, y)、大きいセットのすべてのリンクをトラバースする必要はありません。xy

ただし、テールリンクへの参照を取得するには、各リンクオブジェクトが4番目のフィールド（リンクリスト補助オブジェクト自体への参照）を維持する必要があるように思われます。その場合は、リンクリストオブジェクトを完全に削除し、その4番目のフィールドを使用してテールを直接ポイントしてみませんか？

これは本文の省略だと思いますか？

CLRS の「アルゴリズム入門」を読んでいます。第 2 章で、著者は「ループ不変条件」について言及しています。ループ不変条件とは

「アルゴリズムの概要、第3版」の演習24.3-5では、これが間違っている（常に正しいとは限らない）例が必要です。それは可能ですか？私の考えでは、現在の頂点へのパスがすでに決定されているときにすべてのエッジが緩和されるため、これは不可能です。

一言一言：

N教授は、ダイクストラのアルゴリズムが正しいことを証明していると主張しています。彼は、ダイクストラのアルゴリズムは、グラフ内のすべての最短パスのエッジを、パスに表示される順序で緩和するため、パス緩和プロパティは、ソースから到達可能なすべての頂点に適用されると主張しています。ダイクストラのアルゴリズムが最短経路のエッジを順不同に緩和できる有向グラフを作成して、教授が間違っていることを示します。

代わりにこれを math stackexchange に置くべきかどうかはわかりませんが、まあまあです。

CLRS の 300 ページに...

彼らは3つの確率変数を定義しています...

そして指標確率変数Zn,1 Zn,2 Zn,3 ... Zn,n...

そこで彼らは証明を続けますが（テキストを参照）、その途中で次の主張をします...

Yn-iも同様。私の問題はその部分です。含まれるキーの数以外...はい、サブツリーの構造はRnの影響を受けませんが、Rnがサブツリー内のキーの数に影響を与えるという事実は、サブツリーの高さを制限します。

私は明らかにいくつかの重要な関係を欠いています。どんな助けでも大歓迎です、ありがとう。

Algorithms Third Edition の紹介では、赤黒木削除の疑似コード実装があります。ここにあります...

TREE-MINIMUM はツリー内の最小値を見つけるだけで、RB-TRANSPLANT は 2 番目のパラメーターの親を取得して 3 番目のパラメーターを指し、3 番目のパラメーターの親を 2 番目のパラメーターの親にします。

私のコメントによると、彼らは yp が z であるかどうかをテストし、そうであれば xp を y に設定します。しかし、x はすでに y.right なので、これは y.right.p = y と言っているようなものですが、y.right.p はすでに y です! なぜ彼らはこれをしているのですか？

これが彼らの説明です...

「しかし、y の元の親が z の場合、xp が y の元の親を指すことは望ましくありません。これは、そのノードをツリーから削除しているためです。ノード y は上に移動してツリー内の z の位置を取るため、13 行目で xp を y に設定すると、x == T.nil であっても、xp は y の親の元の位置を指すようになります。」</p>

したがって、彼らは x の親を y のままにしたいと考えています...それはすでに y です...

この実装は、CLRS第2版（ページ番号894）から派生しています。while(1)私には疑わしいようです。whileループの終了条件はどうあるべきですか？

試しk<=nましたが、うまくいかないようです。セグメンテーション違反が発生します。コードの欠陥とその修正方法は何ですか？