このコースでは、ハッシュ、複雑さ、計算モデル、検索ツリー、Bツリー、幾何学的検索問題、グラフの動的接続性など、基本的なアルゴリズムとデータ構造を扱います。
過去のコースのコメントで尋ねられた内容を考慮しました-希望する場合は、講義を個別に視聴/ダウンロードできるだけでなく、すべてをYandex.Diskのオープンフォルダとして一度にアップロードすることもできます。 ちなみに、以前の投稿にも同じ更新が表示されました（便宜上、「 機械学習 」、「 離散分析と確率理論 」、「 並列分散コンピューティング 」のリンクがあります）。
講義はマキシム・アレクサンドロヴィッチ・バベンコ、コンピューター・サイエンスの副所長、モスクワ州立大学の数学と数学の数理論理学とアルゴリズム理論学部のアシスタントによって行われます。 M.V.ロモノソバ、物理学および数理科学の候補。
Yandex.Diskのフォルダー形式のフルコース
講義1.複雑さと計算モデル。 会計値の分析（開始）
主なリソース：メモリと時間。 O記号。 計算モデルの例：チューリングマシン、RAMマシン。 平均および最悪の場合の難しさ。 例：並べ替えタスク。 選択順に並べ替えます。 複雑さの情報理論的下限。 木を許可します。 ツリーを解決するモデルの複雑さの下限。 可変サイズの配列：加法および乗法分布スキーム。 バンキング法を使用した可変サイズの配列の乗法スキームの分析。
講義2.会計値の分析（終了）
取引会計費用の分析：潜在的な機能、真の会計値。 スタックとキュー。 可変サイズの配列およびリンクリストに基づく実装。 2つのスタックを使用したキューのモデリング。 スタックとキューの動的な最大値を維持するタスク。 可変および不変のデータ構造。 永続的なデータ構造。 不変スタックと不変キュー。 永続構造の会計値を分析する際の複数の未来の問題。
講義3.クイックソートとマージソートの機能
分割統治法の概念。 マージソートアルゴリズム。 2つの順序付きリストをマージします。 複雑さの評価。 外部メモリで作業するためのK-way Merge-Sort。 追加メモリを使用せずにソートをマージします。 Quick-Sortアルゴリズムの一般的なスキーム。 パーティションを実装するための2つのオプション。 サポート要素の選択に失敗した例。 サポート要素のランダム化された選択。 最悪および中程度のケースでのクイックソートの複雑さ。 最悪および中程度の場合の再帰の深さ。 テール再帰の排除。 最適なマージツリーの問題。 ハフマンコード。 異なる長さの2つの順序付けられたシーケンスの融合。 情報理論的な下限。 「エッジから」のバイナリ検索（ギャロッピング）。
講義4.順序統計。 ヒープ（開始）
Quick-Sortアルゴリズムのランダム化された修正を使用した順序統計の検索。 稼働時間の予想の線形性。 おおよその中央値。 最悪の場合の線形のk番目の順序統計の選択。 ヒーププロパティを持つツリー。 ほぼ完全なバイナリツリー：頂点の番号付け、ナビゲーション。 バイナリヒープ。 スクリーニング操作の上下。 挿入、削除、および最小検索操作の実装。 キーの任意の配列を束に変換（Make-Heap操作）、線形操作時間。 ヒープソートソートアルゴリズム。
講義5.ヒープ（開始）。 ハッシュ（開始）
k-aryヒープ、kの選択に対する操作の複雑さの依存性。 二項（二項）、左翼（左リスト）、および斜め（スキュー）ヒープ。
講義6.ハッシュ
ハッシュ関数。 衝突 チェーン方式、シーケンシャルプローブ方式、ダブルハッシュ方式を使用した衝突解決。 単純な均一ハッシュの仮説、チェーンの平均長の推定。 ハッシュ関数のユニバーサルファミリーは、チェーンの平均長を推定します。 整数キーのユニバーサルファミリを構築します。 完全なハッシュ関数。 ユニバーサルファミリを使用して完全なハッシュ関数を構築します。 エラーのあるインターフェイスを設定します。 ブルームフィルター 偽陽性の確率の推定。 エラー辞書インターフェイス。 ブルームフィルター（bloomierフィルター）の変更。
レクチャー7.ツリーの検索（開始）
検索ツリーの定義。 アイテムを挿入および削除します。 順序ツリートラバーサル。 赤黒木：定義と基本的なプロパティ。 赤と黒の木材の挿入操作の実装。 スプレイツリー。 スプレイ操作：ジグ、ジグジグ、ジグザグステップ。 スプレイツリーの挿入、削除、マージ、分割操作を実装します。
講義8.ツリーの検索（終了）。 デカルトの木
デカルトの木（duchi）。 異なるキーと優先順位の特定のセットに対するデカルトツリーの一意性。 魂の高さの期待値の対数推定、魂の融合と分離の操作。 ダッチの要素を挿入および削除するための操作。 キーの予備ソートを前提とした線形時間でのデカルトツリーの構築。
講義9. Bツリー。 ばらばらの集合システム
B +ツリー：定義と基本プロパティ。 B +ツリーの検索、挿入、および削除操作。 素集合のシステム。 フォレストを使用した実装。 ピークランク、ヒューリスティックランク。 要素数による対数ランク推定。 ランダム化されたランクヒューリスティック。 ヒューリスティック圧縮パス。 操作の簿価の推定（証拠なし）。
講義10. RMQおよびLCAの目的
タスクRMQ（範囲最小クエリ）およびLCA（最小共通祖先）。 RMQからLCA、デカルトツリーへの削減。 LCAタスクのオフラインバージョン用のTarjanアルゴリズム。 LCAタスクのオンラインバージョンの最も単純なアルゴリズム：完全でスパースな応答テーブル。 ±1-RMQの問題に対するFarah-Colton-Benderアルゴリズム。 LCA問題の±1-RMQ問題への還元：オイラーツリートラバーサル。
講義11.幾何探索の問題
場所の問題、刺すような問題。 インターバルツリー。 区間のシステムを2次元問題に縮小します。 廊下でポイントを見つけるタスク。 優先検索ツリー。 長方形内のポイントを見つけるタスク。 X座標に沿ったセグメントのツリー。各頂点のポイントのYリストによって順序付けられます。 複雑さは、構築の場合はO（n log n）、クエリの場合はO（log ^ 2 n）です。 検索時間をO（log n）に短縮します。 順序付きリストのセットを同時に検索するタスク。 フラクショナルカスケード。
講義12.グラフの動的接続性
動的な接続の問題：エッジの挿入と削除、接続クエリ。 森林の場合の問題の特別な場合。 オイラーバイパスツリー：マージと分割。 減価償却とスパニングフォレストのセットを使用して、複雑度O（log ^ 2 n）で解決します。