CourseraでComputer Scienceを学ぶ
Courseraとは？
スタンフォード大学コンピュータサイエンス教授Andrew NgとDaphne Kollerによって創立された教育技術の営利団体である。世界中の多くの大学と協力し、それらの大学のコースのいくつかを無償でオンライン上に提供している。2012年11月の時点で196カ国から1,900,241人もの生徒が一つ以上の授業に登録をした(Wikipedia)
Data Structures and Algorithms Specializationコースについて
カリフォルニア大学サンディエゴ校とHSE UNIVERSITYが提供している6つのコースから構成されていて、個別に受講することもできる。コースへの参加は無料だがそもそもCoursera自体が月額¥5,000ぐらいかかる。
- Algorithmic Toolbox
- Data Structures
- Algorithms on Graphs
- Algorithms on Strings
- Advanced Algorithms and Complexity
- Genome Assembly Programming Challenge
https://www.coursera.org/specializations/data-structures-algorithms
なぜこのコースを選んだのか
ずっとエンジニアとして働いているが、現在は以前ほどプログラミングに集中する職種というわけではない。
過去にはそこそこ規模の大きいWEBシステムの開発・運用の経験はあるが、Computer Science(以下CS)の学位を持っていないこともあり、なんとなくCSの基礎を学んでいないことがコンプレックスとしてあった。(大学の専攻は経済学)
が、今からCSを学ぶために大学にチャレンジするのは家庭的にもキャリア的にも覚悟が必要だと思っているし、そもそも自分の性格で数年単位での学業をやりきれるとは思えないと感じていた。
とはいえ、何もしないわけにもいかない。
CSといっても範囲が広いらしいので、ある程度それっぽい範囲を抑えていて現実的な修了スケジュールが見える量のコースだとこのコースが魅力的だった。
そしてこのコースすら修了できないなら、大学なんてもってのほかだと自分に言い聞かせる目的もあった。
コースは全て英語なので自分の英語力で通用するか不安だったが駄目ならそれまでと諦めて挑戦してみることにした。
コース全体の感想
先にコース修了後の感想を書いておく
- スパニッシュ系やロシア系の先生なのか独特の訛りがあって、英語力が高くない自分には相当しんどかった
- 週毎の最終課題(プログラミング)が後半かなり難しくなってくるので、もうちょっと細かい頻度で課題設定が欲しかった
- 課題を提出したときに、そのコードが正しく動くかその場で判定される仕組みになっているが、誤りのときに原因がわからないのが辛い。テストコードを開示してほしい。「このテストコードを通るようなコードを書け」の課題にしてもらえると捗る気がする。
- サイトがちょいちょいバグってる（今は直ってるっぽい）
- フォーラムが過疎り過ぎ。全然参考にならない。月額課金にプラスで有料でいいから、メールで相談できるようなサービスあると嬉しい。
以下にコースの内容を走り書きしたキーワードのメモと修了後の所感を記載する
Algorithmic ToolBox
- アルゴリズムを学ぶ目的など。
- フィボナッチ数列の単純実装の計算量とその簡単な改善方法について紹介。
- 最大公約数を求める処理について単純実装とユークリッド互除法による計算量について。
- BigO記法(ランダウの漸近記法 (asymptotic notation))について。
- 貪欲(Greedy)アルゴリズムについて
- 給油問題の最適化について貪欲アルゴリズムでの解説。
- 貪欲法はSubProblemに分解してそれを解くことで答えに導くことが重要
- ナップサック問題を貪欲法で解く。
- 事前にソートしておくことで O (n2) を O(knapsack荷物選択 * 並び替え)でO(n log n)まで最適化できる。
- Divide-and-Conquer (分割統治法) について
- 線形探索 (Linear Search) O(n)
- 二分探索 (Binary Search) O(log n)
- 多項式の掛け算を分割統治法で解く
- マスター定理(Master Theorem) とは
- マスター定理を使うことで分割統治法、漸化式を効率的に解ける
- 選択ソート、マージソート、及び比較ソートの場合の閾値の決め方
- クイックソートにおけるランダムピボット値などのポイントについて
- 動的計画法 (Dynamic Programming)について
- 両替問題
- 文字列の類似度計算（編集距離、Edit Distance)
- 動的計画法による2つのナップサック問題（荷物が同一複数か、一つずつだけか）
- 動的計画法のメモ化のテクニック
- 1 + 2 - 3 * 4 - 5 みたいな式をどの順番で計算すれば最大化できるか問題
しょっぱなから数学的な素養が必要で非常に厳しかった。
アルゴリズムが苦手ということが身にしみたコースだった。
特に動的計画法はより深く想像力が必要で全然太刀打ちできなかったので、自習にめちゃくちゃ時間がかかった。
復習するなら漸化式と動的計画法をがっちり身につけたいところ。
Data Structures
- 配列と片方向リスト（singly-linked list) と 双方向リスト（Doubly Linked List）
- スタックとキュー
- 木構造と探索
- 動的配列 (Dynamic Array)
- 償却（ならし）解析について
- 償却解析で平均計算量や最悪計算量
- Aggregate Method
- Banker's Methodは恐らくwikipediaで言うところのAccounting_method
- Physicist's Method (Potential Method)
- 優先度付きキューについて
- ヒープと二分木と木の高さ
- ヒープソートの仕組みと実装
- 素集合 (Disjoint Sets)
- 素集合における操作、ランク付けによる統合と経路圧縮
- ハッシュとは
- IPアドレスをハッシュに変換する
- ハッシュの紐付け(Chaining)について
- ユニバーサルハッシュ
- JavaのHash Stringの紹介
- ラビン-カープ文字列検索アルゴリズム
- ローリングハッシュ
- Binary Search Treeの仕組みと要件
- Balanced Binary Searchの必要性について
- Binary Search Treeの実装の一つであるAVL木の解説
プログラマとしてそこそこの経験があれば比較的スムーズに進められるコースだった。
ただし、償却（ならし）解析の漸化式など数式がバンバン出てくる箇所は直感で理解することができなかったので腰を据えて向き合わなければいけないので苦しかった。
配列操作はLinkedListなど実践で経験したところがあったのは助かった。
個人的には
- ヒープの仕組みをちゃんと理解できたのはプログラマとして実践で有益に感じたのでこの機会で改めて理解できたのはよかった
- 各データ構造の計算量を改めて整理できたことで、実装する上で計算量をなんとなくではなく具体的にイメージできるようになった（気がする）のはとても良い体験だった。また計算量を考慮して実装する癖がつくだけでなく、その解決方法の糸口も考えられるようになれた気がする
- Binary Searchがどれだけ強力なのか、またその実装アイデアが複数あることに奥の深さを垣間見れたのは良かった
Algorithms on Graphs
- グラフ構造とは
- 2次元配列での表現、1ノードに対してエッジ配列を持つ表現
- 深さ優先探索
- 到達の深さを保持して探索する
- 幅優先探索。
- キューの使い所
- 有向非巡回グラフ
- 強連結成分とその検出
- トポロジカルソート
- 重みがある最短経路はDijkstra 法、重みがない場合はBFS
- 重み付き有向グラフで、負の重みを含む場合はベルマンフォード法を使う。
- 負経路（無限ループ）の検知
- MST (Minimum Spanning Trees) 全域木
- Prim（プリム法）
- Kruscal（クラスカル法）
- UnionFind構造
専門用語が英語だとぴんとこなかったが、日本語で調べたらすぐに理解できた。
全体的に理解しやすい授業でスムーズに進んだ。課題もわかりやすいので実装もそんなに手間がかからずに比較的楽だった。
グラフ構造周辺は検索すると日本語での解説も多くて自習も捗ってとても助かった。
Kruscal法でUnifonFindの使い所があって「そうやって使うのか」感があってよかった。
Algorithms on Strings
- 文字列検索の基礎
- Trie構造とその特徴
- BWT変換
- Suffix Array
- Cyclic Shift
まぁまぁ難しいのと、そもそも期間が空いてしまったのでだいぶモチベーションが下がっている中でこのアルゴリズムをやるのはかなり精神的に厳しい。。。
Suffix ArrayとSuffix Treeは日本語で調べてすぐに理解はできる。
Suffixを抜き出した文字列のソートをCyclic Shiftとして説明のは癖があって全然わからんかった。（自分で調べて他の方法での解説を見て理解に持っていった）
Advanced Algorithms and Complexity
- Network Flowsとは
- Ford Fulkerson アルゴリズム
- 残余ネットワーク
- Edmonds-Karpアルゴリズム
- 線形計画法
- 最適最小化問題
- ガウス消去法
- 線形最適化問題
- Simplex method
- NP完全問題
- Conjunctive Normal Form (CNF)
- 充足可能性問題（Satisfiability Problem, SAT)
- TSP = Traveling Salesman Problem（巡回サラリーマン問題）
- MST = Minimum Spanning Tree Problem
- Hamiltonian Graph ハミルトン路
- Eulerian Graph オイラー路
- Longest Path Problem 最長パス問題
- 線形計画問題
- Independent set 独立集合
前半は直感的にイメージしやすくわかりやかった、最適化問題も以前別のコースで機械学習の講義を受けたときのイメージがあったのでスムーズに理解できた。
後半で突然NP完全の話(数理論理、記号論理の分野？)が出てきて完全に取り残された感があって、そこの自習と復習でだいぶ疲弊した。
アルゴリズムや数理問題でどのような問題があって、限界があるのかを知ることができて興味深かった
Genome Assembly Programming Challenge
- メモなし
過去に流行した疫病の解決のために大腸菌のゲノム配列を調べるためのプログラミングチャレンジ。
正直難しすぎて課題理解にほとんどの時間を費やした。（主に英語がボトルネック）
グラフや文字列探索や各種アルゴリズムを思い出しながら実装して心が折れて、他の人の実装からヒントをもらいつつなんとかクリアできたレベル。
コースを終えて
時間のとり方
30週なので7ヶ月〜8ヶ月かかる計算だけど、これだけに集中できれば4ヶ月で達成することも不可能ではなさそうな印象（自分の場合は家族もいるので年末年始や子供との時間で気づくと取り組む時間空いてしまったり、仕事で忙しい時期があったり、Coursera以外の優先して取り組む事が一時期あったりで時間がかかってしまった。
できれば少なくとも3ヶ月がっつり「これだけ」やることを決めて集中するほうがよさそう。
対象者
実践向けプログラミングを学びたい人向けではない。
どちらかというと
- 独学でプログラミングはできるが、将来に向けて基礎となる理論を固めておきたい
- プログラマーとして仕事している(していた)けど改めてその理論を体系的に学びたい
のような人向けだと感じた。(自分は後者)
この対象の人であればCourseraの月額料金（¥5,171）だけで受講できるのは素晴らしい内容だと思う
取り組み方
個人的な取り組み姿勢としては
1. 授業のビデオ(英語)をしっかり見て「なるべく」理解しようとがんばる
2. ビデオの中でぴんと来ない箇所を日本語で調べる
3. 日本語の本や動画を探してしっかり理解に落とし込む
の流れ。
というか、1. で理解できるところはせいぜい2割程度。
「全編英語 + 独特の英語訛り + 自分の前提知識が足りてない」ので、2. と 3. でリカバリーする。むしろ2. と 3. が全てな気もする。
得られるもの
「CSを勉強したい」と漠然と考えていても、CSといっても広すぎるし何から勉強すればいいのかわからない（CS学位持っている人はみんな言っている事違うし）、かと言ってソートアルゴリズムを本で読んで理解するぐらいではCSとは到底思えない。
そんなときにこのコースはCSの一部を体系的にカバーしてくれていると思う。このコースを受講しただけで「CS完全に理解した」には当然ならないし、実践で使うような機会がなければ一年も立てばその内容はきれいさっぱり忘れている可能性が高いけど、そういう理論や解法、考え方、アプローチが存在するというポインタは得られたと思う。
例えば「残余ネットワーク」って言葉を見たときに今までは「はい？」って思うけど、とりあえず「あー詳しく覚えてないけどなんかネットワークの流量を最適化するときに出てくるやつ」ぐらいには感じられると思う。
得られないもの
学位(単位)。
結果、やはり仕事をしながらCSの勉強を高いレベルで取り組み続けるのは自分に難しいと思った。
仕事をしながら学位を目指すのは考えていた以上に自分には難しそうだなと感じた。
実際、このコースの卒業要件もかなりギリギリでのクリアとなったし、正直に言うといくつかの内容は深堀りで行き詰まり表層の理解に留めた箇所もある。
プログラミング課題も最後のほうは、他の生徒のコードを参考にして課題の意図を理解するというショートカットをしたところもある。
なので、実際の大学で言うところの友達からノート借りてコピーさせてもらったり、先輩から過去問もらったりしたノリで乗り切ったところもあるので、優秀な卒業生とは思えないのでこれも学位にチャレンジするのは難しいと判断した理由になった。
英語について
仕事でお客様に技術的な説明したり、同僚とコミュニケーションできている（はず）ぐらいの英語力だけど、その英語レベルだとこのコースは相当時間的なボトルネックになった。
とはいえ、ここまで体系的にまとまっているコースを他に知らないのでどうしようもないが、もし日本語で同じようなコンテンツがあるなら悪いことは言わないのでそちらを選んだほうがいい。
決して、「英語とCSの勉強ができて一挙両得やん♪」とか考えないこと。
最後に
上智大学 理工学部 情報理工学科の准教授 宮本 裕一郎先生が公開されている講義が今回のコースで扱っている内容に近く非常に参考になった。
Youtubeで公開されている講義がめちゃくちゃわかりやすいし、淡々と講義をすすめる中で所々にジョークが入ってて親しみやすい。
こんな素晴らしい内容を無料で視聴できるなんてテクノロジーの進化の恩恵を受けられるいい時代なんだなと感じた。
自分も少しでも貢献できるように先々がんばっていきたいと思う。
この記事が気に入ったらサポートをしてみませんか？