スタンフォード大学のアルゴリズムコースとは
今年2018年の4月頃から勉強をはじめたアルゴリズムのプログラムを無事に修了する事が出来ました。
このコースはMOOCと呼ばれるオンライン講座の一つで、その中でも有名なCourseraで受講しました。
“Algorithms, a 4-course specialization by Stanford University”という名称で開講しており、その名の通りスタンフォード大学のアルゴリズムの授業をオンラインで受講可能にしたものです。
１ヶ月のコースが４つあり、トータルで４ヶ月で完了できます。 目安としては、毎週約８時間ほどの時間を確保して望めば、良いと思います。
僕は自分自身でアルゴリズムに関して独学で勉強したものの、知っている事と知らない事が混在しており、ちゃんと網羅的に学びたいという思いから受講する事にしました。
ちなみに費用は、毎月$49ドルでした。内容に比して全然安いと思います。
詳細はこちらの公式サイトを見てみてください。 => https://www.coursera.org/specializations/algorithms
Tim Roughgarden教授
スタンフォード大学で教えているTIm Roughgarden教授がすべての授業を担当してます。
話すのが結構早く、字幕を上手く見ながら聞かないと置いて行かれてしまう事も結構ありました。 でも、アルゴリズムの難しい所は丁寧に教えてくれるので、とても良い先生でした。
授業の内容
Course 1: Divide and Conquer, Sorting and Searching, and Randomized Algorithms
- “big-oh” notation and asymptotic analysis
- Divide-and-conquer basics
- The master method for analyzing divide and conquer algorithms
- The QuickSort algorithm and its analysis
- probability review
- Linear-time selection
- graphs, cuts, and the contraction algorithm
いわゆるビッグ・オー記法から始まり、分割統治法やマスター・メソッドの考え方を学びます。 クイック・ソートのアルゴリズムや、グラフのミニマムカットについても扱います。
Course 2: Graph Search, Shortest Paths, and Data Structures
- Breadth-first and depth-first search
- computing strong connected components(SCC) ; applications
- Dijkstra’s shortest-path algorithm
- Heaps
- balanced binary search trees
- Hashing; bloom filters
グラフの探索アルゴリズムである、BFS（幅優先探索）やDFS（深さ優先探索））、SCC、ダイクストラ法、ヒープやハッシュ関数の衝突、ブルームフィルタなどについて学びます。 この辺りは、アルゴリズムの基礎ですし、データ構造という意味でもソフトウェア・エンジニアとして知っておくべき事と思います。
Course 3: Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
- Two motivating applications;
- introduction to greedy algorithms; a scheduling application;
- Prim’s MST algorithm.
- Kruskal’s MST algorithm and applications to clustering
- Huffman codes
- introduction to dynamic programming
- Advanced dynamic programming: the knapsack problem, sequence alignment, and optimal binary search trees.
Greedyアルゴリズム（貪欲法）、プリム法、クラスカル法を用いたMST（Minimum Spanning Tree: 最小全域木）の解法、ハフマン符号、ダイナミック・プログラミング（動的計画法）を用いてナップサック問題等に取り組みます。
Course 4: Shortest Paths Revisited, NP-Complete Problems and What To Do About Them
- The Bellman-Ford algorithm
- all-pairs shortest paths.
- NP-complete problems and exact algorithms for them
- Approximation algorithms for NP-complete problems
- Local search algorithms for NP-complete problems
ベルマン・フォード法、APSP (All-pairs shotest paths)、NP完全問題への取り組み方を学びます。 NP困難な問題だと多項式時間での解法はない（とされている）が、そういった問題に対してベターなアルゴリズムを考えて行きます。NP困難な問題は難しい部分が多かったです。
証明書
毎週の課題をクリアし、４つのコースを完了するとこのような証明書がもらえます。
まとめ
振り返るとたくさんのテーマを学んだ気がします。
Tim Roughgarden教授が言っていた事ですが、アルゴリズムの授業では、これまでのアルゴリズムの歴史の中のグレイテストヒットを学んで行きます。学んだアルゴリズムが自分のツールボックスの１つに加えられて行くわけです。
今後、現実の問題を解くときに、それらのアルゴリズムを自分のツールとして使いこなし、より良い解法を見つけられるように出来れば素晴らしい事ですね。
まだ理解の浅い部分もあるので、それらは追々また学んで行きたいと思います！