【備忘録】Algorithms: Design and Analysis, Part 2

スタンフォード大学のオンライン講座”Algorithms:DesignandAnalysis,Part2“。後で見る。

以下、Google翻訳の結果をコピペ。ちょっとだけ変更。

コースについて

このコースでは、アルゴリズム設計のいくつかの高度な基本原則を学びます。あなたは良いコンピューティング·ネットワークバックボーンへのアプリケーション（すなわち、スパニングツリー）とデータ圧縮のための良いコードで、貪欲アルゴリズム設計パラダイムを学びます。あなたは、インターネットおよびゲノム配列の断片でルーティングへの応用と、トリッキーまだ広く適用可能な動的計画法のアルゴリズム設計パラダイムを学びます。あなたは何NP完全と “P対有名学びますNP “問題は、アルゴリズム設計者にとっての意味。最後に、我々は経験則の設計と解析を含むハード（すなわち、NP完全問題）に対処するためのいくつかの戦略を勉強します。学ぶどのようにあなたのインターネットトラフィックが今日ルーティングされる方法を規定する1950（すなわち、事前にアルパネット！）から最短パスアルゴリズムは、効率的なアルゴリズムは、現代のゲノミクスの基礎となるのはなぜ、どのように “だけで賞金百万ドルを作る方法”数学の問題を解く！

講師について

Tim Roughgardenはスタンフォード大学の情報科学・経営工学の准教授です。

コース概要

第1〜2週

：貪欲なアルゴリズム設計パラダイム。最適キャッシングとスケジューリングへの適用。最小限のスパニング・ツリーと集まることへの適用。合併検索データ構造。最適データ圧縮。

第3〜4週

：動的計画法設計パラダイム。シーケンス調整への適用は、ルーティングと最適探索木を最も不足して行きます。

第5〜6週

：困難な問題とそうすることは、彼らについてします。NP-完全性とP対NP質問。解決できる特例。証明できる高性能保証による発見的教授法。ローカル検索。暴力的な検索を打つ指数時間アルゴリズム。

前提知識

C、JavaまたはPythonなど少なくとも1つのプログラミング言語を知っていること。そして、誘導による、そして、矛盾による証明を含む証明の熟知。スタンフォード大学では、このコースのバージョンは二年生、ジュニア、シニアレベルのコンピュータサイエンス専攻の学生によって行われる。コー​​スはアルゴ1から話題に精通していることを仮定した。 —特に漸近解析、基本的なデータ構造、基本的なグラフアルゴリズム。