POMI RASのコンピューターサイエンスクラブコースのビデオを引き続きアップロードします。 最初の部分はこちらです。 このコレクションには、「コミュニケーションの複雑さ」、「エキスパンダーとその応用」、「機械翻訳」、「フロー理論の選択された章」の4つのコースがあります。
通信の複雑さ
講師 ：
ニコライ・コンスタンティノヴィッチ・ベレシチャギン、モスクワ州立大学教授、欧州アカデミー会員。
注釈
通信の複雑さの理論における最も単純なモデルは次のとおりです。 特定の問題を一緒に解決したい2人の参加者（コンピューターまたは人）がいます。 それらのどれも自分で問題を解決することはできません（たとえば、それぞれに十分なデータやリソースがありません）。 したがって、彼らは通信する必要があります。 通信の複雑さは、問題を解決するために参加者が交換する必要がある最小ビット数を測定します。 各参加者がローカル計算を実行するのに必要な時間は考慮されていません-これは計算の複雑さの理論との根本的な違いです。 通信の複雑さの結果は、理論的なコンピューターサイエンスの他の分野で非常に広く使用されています。
コースの資料とビデオ。
エキスパンダーとそのアプリケーション
講師 ：
Andrey Evgenievich Romashchenko、モスクワのロシア科学アカデミーの情報伝達問題研究所、およびモンペリエの情報科学、ロボット工学、マイクロエレクトロニクス研究所（LIRMM）の研究者。
注釈
エキスパンダー（拡大グラフ）は、理論情報学および離散数学における強力で高度なツールです。 どうやら、エキスパンダーの有効性の一部は、それらの定義によって、組み合わせ幾何学的、代数的、および確率論的推論を自然に組み合わせることができるという事実によるものです。 エキスパンダーは1970年代に特定されました。 過去30年にわたって、彼らは多くの美しい用途を見つけてきました。 エキスパンダーは、さまざまなデランダム化設計で使用されます。 エクスパンダーを使用して、エラー訂正コードと信頼性の高い計算スキームが構築されます。 拡張手法は、計算の複雑さの理論のさまざまな証明（たとえば、有名なPCP定理の証明）で使用されます。 このコースでは、アルゴリズムの理論の観点からエキスパンダーに興味があります。 エキスパンダーの組み合わせ特性とスペクトル特性の関係を研究し、そのようなグラフを構築するための効果的なアルゴリズム手法を検討し、エキスパンダーのさまざまなアプリケーションについて説明します。 また、エキスパンダーと他のすばらしいクラスのグラフとの接続についても説明します：抽出器、分散器、圧縮器。
コースの資料とビデオ。
機械翻訳
講師 ：
英国でGoogleを代表する研究者であるDavid Talbot氏は、データ分析学部の教授です。
注釈
コースの初日は、自動翻訳のための並列データから機械学習の問題を学生に紹介します。 学生は、単語の整列のための簡単なアルゴリズムを実装するよう求められます。 コースの2日目は、神経機械翻訳の基礎に専念します。 学生は、簡単なコーデックデコーダモデルで実用的な経験を積むことができます。 基本的なPythonスキルと、githubを使用してコードをコンパイルおよび実行する能力が役立ちます。 コースは英語で行われます。
コースの資料とビデオ。
フロー理論の選択された章
講師 ：
マキシム・アレクサンドロヴィッチ・バベンコ、経済学高等学校の准教授、データ分析学部の講師、Yandexの従業員。
注釈
流れの理論は、間違いなく、組み合わせ最適化の最もよく研究されているセクションの1つであり、理論的および実用的なさまざまな用途があります。 コースは、主題の簡単な紹介から始まり、最大流量問題の基本的なアルゴリズムを分析してから、より現代的なトピックであるプリフローとパラメトリック流量の問題をプッシュすることを迅速に進めます。 コースの最後の部分では、フローの概念の一般化に触れます。最も単純なタイプのマルチストリーム問題を検討し、スキュー対称および双方向グラフのフローについても話します。 学生から、彼らはアルゴリズムのグラフ理論の基本概念に精通することになっています。
コースの資料とビデオ。