Yandex、HSE、UC San Diego、CSCのアルゴリズムとデータ構造の専門化

ソーシャルネットワークがフレンドグラフの検索に使用するアルゴリズムは何ですか？ テレビ会社は、利益を最大化するためにどの広告を表示するかをどのように選択しますか？ 数百万の断片からゲノムを組み立てる方法は？ ニューヨークからマウンテンビューへの最短経路を、従来のアルゴリズムよりも数千倍速く計算する方法は？



Yandexの参加で作成された別の便利な専門分野- コースアルゴリズムとデータ構造 -がCourseraに登場しました。 教師の中には、Yandex、HSE、サンクトペテルブルクコンピューターサイエンスセンターの代表者だけでなく、カリフォルニア大学サンディエゴ校の講師もいるため、今回はすべての専門コースが英語を話します。











そのうちの5つがあり、聴衆の終わりに最終プロジェクトを待っています。 そのうちの1つはバイオインフォマティクスに関連し、2つ目は実際の道路網とグラフの最短経路の検索です。 専門の形式では、すべての資料が無料で利用できます。 確認のために宿題を送り、証明書を取得する場合にのみ、支払いが必要になります。 次に、約100のタスクをプログラムし、テストシステムに送信する必要があります。 これは、C、C ++、C＃、Haskell、Java、JavaScript、Python2、Python3、Ruby、およびScalaで実行できます。



今日は最初のコースであるAlgorithmic Toolboxを開始します。 カットの下には、専門プログラム、教師に関する情報、およびそれが誰に役立つか、そしてその理由に関する意見があります。

先生方

ミハイル・レビン。 Yandex、HSEコンピュータサイエンス学部。 Yandex Data Factoryのビッグデータ分析責任者。 彼はデータ分析学部で「アルゴリズムとデータ構造」コースを教え、HSEとYandexのコンピューターサイエンス学部でトレーニングプログラムの作成に参加しています。 モスクワ州立大学のチームの一員として、ACM ICPCで2回メダルを獲得しました。 M.V. ロモノソフ。 Habréの多くは、数学でYandexが広告収入を得るのにどのように役立つかに関するミーシャの講義を覚えています。

アルゴリズムとデータ構造はコンピューターサイエンスの基礎であるため、これはどのコンピューターサイエンスプログラムでも必須のコースです。 データベース、分散システム、ストレージ自体を作成するためだけでなく、たとえば検索やナビゲーターなどのサービスを作成するためにも、それらを知っておく必要があります。 アルゴリズムはデータサイエンスで使用され、機械学習の重要な部分は機械学習アルゴリズムです。



私たちの専門は、SHADのコースとは、エントリーのしきい値が大幅に低いこと、プルーフが少ないこと（多くはオプションです）、トピックのセット、実用的な例と最新のアプリケーションに重点を置いていること、およびCapstoneプロジェクトの存在です。



この専門化は、プログラマーと研究者の両方に役立ちます。 彼女は、トップテクノロジー企業とのインタビューを受け、より複雑な問題を解決する方法を学び、それによって職場での昇進を得るために、彼女のスキルをアップグレードするのを最初に支援します。 また、たとえば、研究者は、手で実験を処理する代わりに、コンピューターの計算能力を使用できます。

ダニエルケイン 、カリフォルニア大学サンディエゴ校 。 CSEおよび数学科の准教授。 ダニエルはアルゴリズムの紹介を教えています。 彼の科学的関心の中には、数学のさまざまな分野とコンピューター科学の理論があり、彼の仕事のほとんどは、数論、計算の複雑さ、および組み合わせ論に関するものです。 ダニエルケインはハーバード大学を卒業し、MITで博士号を取得しました。

ソフトウェア開発、ゲノム解析、渋滞予測、推奨システムなど、あらゆる場所でアルゴリズムが使用されています。 インターネットを使用するだけでアルゴリズムに遭遇します。 これらはコンピューターサイエンスのあらゆる分野で使用されているため、アルゴリズムとデータ構造のコースはCSプログラムの基本的な部分です。

Pavel Pevzner、カリフォルニア大学サンディエゴ、アルゴリズム生物学研究所、SPbAU。 PavelはPhysTechを卒業し、現在はサンディエゴのCSE部門の教授であり、12年間バイオインフォマティクスのアルゴリズムを教えています。 2011年、彼はサンクトペテルブルクのアルゴリズム生物学研究所の設立に参加し、ロザリンドプラットフォームを開発しました。 彼の科学的業績が認められ、ポールはACMおよびISCBの正会員の称号を授与されました。

アルゴリズムはどこにでもあります！ 体内の数兆個の細胞のそれぞれは、まだ十分に研究されていないアルゴリズムの複合体全体を実行します。 それらは、どの突然変異が人々を互いに区別し、彼らが私たちの病気とどのように関係しているかについての重要な生物医学的質問への答えへの鍵です。 この専門分野では、アルゴリズムの理論に精通することに加えて、独自のアルゴリズムを開発します。 彼らは、100万個の小さな断片から最大のパズルであるゲノムを収集するなどのタスクを解決する必要があります。

カリフォルニア大学サンディエゴ校Googleのニールロードス 彼はUCSDを卒業し、コンピューターサイエンスを学びました。 彼はすでに博士号を取得していましたが、大学を辞め、自身の会社であるPalomar Softwareの開発を開始することにしました。 10年以上にわたり、ニールロードスはサンディエゴでアルゴリズム、機械学習、離散数学、および計算可能性理論のコースを教えてきました。 彼はAppleとPalmの従業員向けのトレーニングプログラムを開発しました。 過去7年間、彼はGoogleの開発者でした。

使用するアルゴリズムが効率的であることは非常に重要です。 マシンが何十億ものページを検索する場合でも、人は瞬く間に検索結果を必要とします。 よく考えられていないアルゴリズムは、文字通りインデックス化された検索エンジンページまたは何世紀にもわたるすべてのFacebook投稿を処理できます。 これらのサービスを使用できるようにするには、アルゴリズムを継続的に改善する必要があります。 そのため、テクノロジー企業はインタビューで常にアルゴリズムに関する質問をたくさんします。

アレクサンダー・クリコフ、数学研究所 V.A. YandexのコンピューターサイエンスセンターSteklova。 彼はサンクトペテルブルク州立大学の数学を卒業し、ステクロフ数学研究所で物理学と数学の博士号を擁護しました。 彼の研究対象は、NP困難な問題と回路の複雑さのアルゴリズムです。 アレクサンダーは、サンクトペテルブルクのコンピューターサイエンスセンターを率いており、それに基づいてYandex Data Analysis Schoolの支部が運営されています。 彼は、ロシアで会議と学生コンピューターサイエンススクールを開催しています。

アルゴリズムはコンピューターサイエンスのすべてのセクションで必要とされるため、技術面接では常にアルゴリズムに関する質問があります。 Kurserにはすでに2つの優れたアルゴリズムコースがあります。1つはスタンフォードのTim Rafgardenから、もう1つはプリンストンのRobert Sajwickからです。 私たちの専門は、その点で彼らと比較して有利です

実用的なコンポーネントに大きな重点を置いています。 全部

学生は、学習したアルゴリズムを実装して、大量のデータに対しても非常に迅速に作業する必要があります。 これにより、アルゴリズムの理解が深まり、高速で信頼性の高いプログラムを作成およびデバッグする際の貴重な経験が得られます。 私たちの専門分野の2番目の利点はより一般的です-それはより多くの材料を持っています。



始めるには、基本的な数学的トレーニング（帰納法による証明、矛盾による証明）、プログラミング経験（C、C ++、C＃、Haskell、Java、JavaScript、Python2、Python3、RubyまたはScala）が必要です。リストの操作方法を想像してください/配列と再帰の仕組み。 スペシャライゼーションは、より多くの需要になり、より複雑な問題を解決する方法を学びたいプログラマーに役立ちます。

プログラム

専門分野は、5つのコースと最終プロジェクトで構成されます。

1. アルゴリズムツールボックス

初年度、私たちはあなたが知ることができないアルゴリズムと、実際に頻繁に発生するタスクについて話しました：並べ替えと検索、分割統治アプローチ、貪欲なアルゴリズム、動的プログラミング。 貪欲なアルゴリズムを使用することが理にかなっている場合と、ゲノムの研究で動的プログラミングがどのように使用されるかを学習します。 新しいアルゴリズムの作成とその効果的な実装を練習できます（1秒以内に機能するように）。

2. データ構造

効率的なアルゴリズムは、ほとんどの場合、効率的なデータ構造を使用します。 このコースでは、さまざまな問題を解決するために使用できる主なものを扱います。 基本的な構造から始めましょう：配列、キュー、スタック、ツリー。 どのような状況で使用するかについて説明します。 次に、辞書を実装する2つの方法を検討します-ハッシュテーブルとバイナリ検索ツリーを使用します。 これらの構造は、プログラミング言語とデータベースで一般的に使用されています。 実際には、ほとんどすべての重要なプログラムが何らかの形でハッシュテーブルまたは検索ツリーを使用します。 また、これらの構造は通常プログラミング言語のライブラリに実装されますが、プログラムで効果的に使用し、既存の実装を拡張できるようにするには、その長所と短所を理解することが重要です。



さらに、このコースでは、Yandex.Diskが多くのスペースを節約する方法と、大きなファイルをDropboxにダウンロードすることがほぼ瞬時に行われる理由について学習します。 ビッグデータを保存するために使用される分散ハッシュテーブルを構築する原理を理解します。



最後に、このコースでは、「最小要素の抽出」や「2つの要素が同じセットに属しているかどうかの確認」などのクエリを実行できるデータ構造について説明します。

3. グラフ上のアルゴリズム

ナビゲーターを起動してルートを構築したり、おおよその移動時間を見つけたりした場合、グラフのアルゴリズムを使用しました。 グラフは、道路ネットワーク、コンピューターネットワーク、さらに最近ではソーシャルネットワークなど、さまざまな現実に現れます。 仕事を始めるための簡単な方法、複数のコンピューターをネットワークに接続する最も安価な方法、またはFacebookで人気のある人を見つけるための効果的な方法を探している場合、グラフのアルゴリズムを使用する必要があります。



このコースでは、グラフとは何か、グラフのプロパティ、グラフを回避する方法、グラフが役立つ場所を見つけます。 最短経路を見つけるためのアルゴリズムを検討します：さまざまなナビゲーションサービスで使用される最短経路から。 最短パスでプロジェクトを選択する場合、最終プロジェクトを完了するときに後者が必要になります。 コースは、道路、電話、およびコンピューターネットワークの設計で使用され、クラスタリングアルゴリズムで使用される最小スパニングツリーの説明で終わります。

4. 文字列のアルゴリズム

コンピューターサイエンスの観点から見ると、私たちを取り巻くすべてのテキストは線です。 効果的な検索を作成するために、開発者は回線上でアルゴリズムを積極的に使用します。 それらは医学でも使用されています。研究者は、彼らの助けを借りて、特定の疾患を引き起こすヒトゲノムの突然変異を見つけます。 専門分野の4番目のコースは、回線上のアルゴリズムに専念します。

5. 高度なアルゴリズムと複雑さ

基本的なアルゴリズムの研究はこれまでに完了し、高度なアルゴリズムに進みます。 コースは、ネットワークとそのアプリケーションのフローから始まります-明らかなもの（最適な対応、分離されたパス、スケジューリングの検索）、およびより予期しないもの（コンピュータービジョンでの画像のセグメンテーション、グラフでの密集したクラスターの検索）です。 次に、線形計画法を実行して、最適な予算を作成する問題、与えられたパラメーターに従って最も安い食事を見つける、電気通信での通話をルーティングするなどの問題を解決します。



その後、適切な解決策が見つからず、ほとんどの場合、見つからない困難なタスクが残ります。 生徒は実際にそれらを解決する方法を学びます。 最後に、ビッグデータと機械学習におけるアルゴリズムの適用について説明します。