約束どおり、アルゴリズムコースのトレーニング
に関する記事の続きを書いています。
コースの構造がわからない人は、最初の記事で質問します。そこで、私は仕事の様子を描きました。 ここで、最後の3週間の学習プログラムと最終試験についてお話します。
週4- 優先度キュー。 優先度キュー、それらの基本操作が調べられ、それぞれの複雑さが推定されます。 バイナリヒープ（バイナリヒープ）を介したキューの実装、およびこのデータ構造に基づく並べ替え（ヒープソート）を検討します。
- エレメンタリシンボルテーブル（シンボルテーブル）。 この章は、「シンボルテーブル」（このような直接的な翻訳についてはすみません）、つまり、キーと値のペアの保存に専念します。 リンクリストおよびバイナリツリーを使用したシンボルテーブルの実装における基本的な操作とその複雑さを考慮します。 私の意見では、この章はバイナリツリーとそれらに対して実行される操作の優れたガイドと考えることもできます。 概して、それらが何を格納するかはそれほど重要ではありません。この章は基本シンボルテーブルとBSTと非常によく呼ばれます。
- 実際的なタスクとして、ゲームの「タグ」の解決策を見つけるためのプログラムを実装することが提案されます。
週5- バランスの取れた検索ツリー（バランスの取れた検索ツリー、直接の翻訳をおagainびします。検索ツリーではなく、バイナリツリー）。 おそらく、コース全体で最も役立つ章の1つです。 基本的なデータ構造の1つである赤黒木が考慮されます。 分析は非常に詳細かつわかりやすく考えられており、分析は2〜3本のツリーから始まり、その後、その開発として赤黒木が考慮されます。 驚いたことに、彼はコースの作成者であるロバート・セジェビクが、私たちが知っている形で赤黒の黒檀を作ることに直接関与していることを知りました。
- BSTの幾何学的アプリケーション（幾何学的問題を解決するためのバイナリツリーのアプリケーション）。 このセクションは私にとって啓示でした。以前考えられていたすべてがある程度理解していれば、ここではほとんどすべてが新しく、特にkdツリーは非常に興味深いデータ構造です。 一般に、平面上の点のセット（または点）が別の点のセット（セグメントまたは長方形）に属しているかどうかを見つけるために二分木を使用する可能性が考慮されます。 KDツリーや間隔検索ツリーなど、さまざまなバイナリツリーを考慮します。
- 実際のタスクでは、kdツリーを使用して、平面上の最も近い点の検索と、平面上の点の特定の長方形への所属を実現することが提案されています。
週6- ハッシュテーブル（ハッシュテーブル）。 名前が示すように、この章ではハッシュテーブルに焦点を当てています。 最初の講義では、ハッシュ関数と、Javaでハッシュ関数を実装する方法について説明します。 次に、ハッシュテーブル自体についての会話が行われます。ハッシュテーブルの実装が考慮され、操作の複雑さが評価されます。 ハッシュテーブル内のハッシュの衝突を解決する方法に多くの注意が払われています。 方法の1つはすべての人に知られており、ハッシュ関数の各値のリストに基づいています。たとえば、2番目の方法も発見でした。これはこれまで見たことがありません（1つのリンクリストを使用してすべての値を格納します）。
- コースの最後の週には、実用的なタスクはありませんが、代わりに最終試験があります。
最終試験最終試験は非常に難しいことです。 20の質問。その多くは公開されています。 回答オプションなし（たとえば、指定された並べ替えのnステップを実行した後に数値の配列を書き込む）。 ほとんどの質問はすでにコースの前の演習で行われましたが、いくつかの新しいタイプのタスクがあります。 たとえば、いくつかのステートメントまたは質問が与えられ、いくつかの回答が与えられた場合、回答を対応するステートメントと比較する必要があります。 タスクは、各オプションを1つ以上のステートメントに使用できるか、まったく使用できないという事実によって複雑になります。 または別の例：10個の単語の配列が与えられ、最初の配列が示され、この配列またはその配列をソートする中間状態を決定する必要があります（割り当てはきちんと私に負担をかけました、そして私はそれを最後にやろうとしたので、私は長い時間と吐き気のために十分ではありませんでした、いくつかのオプションを入れましたランダムに）。
最終試験には3回の試行が与えられますが、最高の回数がカウントされます（残念ながら、最終締め切りの直前に試験の自由時間があったため、1回の試行しかありませんでした）。 やがて、穏やかな環境で2〜3時間の仕事に集中する必要があります。注意と正確さが非常に重要です。 最終回答を論文から入力フィールドに正しく転送しなかったため、2つのタスクに圧倒されました。1つのタスクでは配列の最後の要素を追加せず、もう1つでは番号90ではなく92を書きました。最大20ポイント、私は20点中14.77点を獲得することができましたが、上で書いたように、もう少し注意を払って、16-17点を得ることができました。 残念ながら、最終テストの後、コース全体の評点の計算はありませんでした（または、たぶん見つけられなかったのでしょうか？）。しかし、演習と実際のタスクの採点により、最終評点の存在が示唆されました。 コース全体を最初から最後まで責任を持って受講する場合、最終テストで問題が生じることはありません。
全体として、私はこのコースがとても気に入り、多くの新しいことを学び、私のさまざまな知識を単一のシステムに取り入れました。 11月に発表されたこのコースの第2部に既にサインアップしています。 最初の部分をまだ聞いていない人には、強くお勧めします。 残念ながら、このサイトにはまだコースの正確な開始日がありませんが、登録して開始の通知を受け取ることができます。
参照：ourseraウェブサイト
-www.coursera.orgコース「アルゴリズム。 パート1」
-www.coursera.org/course/algs4partIコース「アルゴリズム。 パート2」
-www.coursera.org/course/algs4partII