コンピュータサイエンス学習マップ2

前回はコンピュータサイエンス学習マップとして、大学1～2年で習う科目と前提となる科目(数学含む)を紹介しました。

今回はより専門的な知識が必要となる学部3年生で習う科目とその前提科目を紹介します。専門領域に入ってくるので、自分の興味のある専門領域に進むのにどういう勉強をすべきか、ということの参考になれば幸いです。量が一気に増えてるのでちょっと細かく区切ります。

また、個人的に引っ越しの準備や、CourseraのMachine Learningの受講(無料＆復習)をしていることもあり、更新遅れています。Machine Learningは正直、入門編を簡単にしたレベル(数学的に深入りしすぎない＆実装が穴埋め)なので、難しくはないのですが、動画の視聴に一日30〜45分とクイズを解く場合＋15程度使ってます。ちょっと記事を書く時間がそれで持っていかれている感じです。Machine Learningと言っても内容は2年生向けの入門クラスの課題を簡単にした感じに思えます。というか、Stanfordは1,2年辺りにMachine Learningあったので、そこで学ぶ内容かも知れません。うちはStanfordよりだいぶレベルはしたですが、4年生と院生向けの入門ではないクラスで同じような内容をもう少し深く、また実装は穴埋めでなく全部各感じでやりました。

8月の引越し後は書斎ができるので、新婚というのもあり、家であまり時間を割けてなかったのですが、少し執筆の時間が取りやすくなるかもです。

学習マップ(3年まで)

CS学習マップ(3年まで)

大学3年レベル

計算理論入門

前提科目：データ構造、離散構造(もしくは離散数学)
教科書：An Introduction to Formal Languages and Automata, 6th ed. by Peter Linz

計算理論の入門編です。おそらく3年次で一番重要かも知れません。
計算理論とOSが3年生の柱かと思います。

内容として下記がシラバスであげられています。この科目は履修しましたが、結構面白かったです。

• 有限オートマトン

• 正規文法

• 正規表現

• 正規言語の表現

• ポンピング補題(Pumping Lemma)

• Context-Free 言語のオートマトンとの変換

• 言語が正規かContext-Freeか

• 文法の曖昧さ

• チューリングマシンのためのシンプルなプログラム生成

• 非決定性の概要

• 判別不能な問題

課題は証明とか論述でほぼ毎週問題が出ました。正規表現の理解とか、音声認識等で使われるWFSTなんかの基礎にもなるような話で、状態遷移とかをちゃんと理解するなら、計算理論はやっておいた方が良いと思います。また、P≠NPとかにもつながる科目なので、セキュリティを専門にしたい場合は計算理論は必須かと思います(入門編だけでなく)。

アルゴリズム分析

前提科目：データ構造、離散構造(もしくは離散数学)
教科書： Introduction to Algorithms, 3rd Edition
                Cormen, Leiserson, Rivest, Stein著
　　　　=>日本語版：アルゴリズムイントロダクション

3年生の柱の一つ、アルゴリズムに関する授業です。
うちの大学では大学院生も含め必修で一定以上のGradeが求められる科目でした。

色んなところで勘違いされてたりしますが、アルゴリズムの授業というのはレシピのように作りたいものの作業の順序を書いたりするような類ではなく、アルゴリズムの分析としてビッグオー記法(Big-O notation)での計算量の分析であったり、再帰や動的計画法、分割統治法などのような高速化のアルゴリズムの技法を学びます。FizzBuzzの解き方を列挙するような話ではないです。

シラバスに書いてあるのは下記です。

• 正しさと処理速度に関するアルゴリズム分析

• 分割統治法と再帰を用いた再帰アルゴリズムの分析

• 動的計画法

• グラフアルゴリズム

• 複雑性クラス(P, NP, NP-complete, NP-hardなど）

• ヒューリスティクスと近似アルゴリズム

基本的なアルゴリズムと分析を習います。証明が中心で、実装課題は1，2個でした。オンラインクラスだとほぼ毎週課題とクイズ。

大事なクラスなので、キーワードを挙げておきます。授業で取り上げるトピックです。

• クイックソート(ランダム/非ランダム)

• マージソート

• 安定ソート

• 挿入ソート

• 選択ソート

• クイックセレクト

• 末尾再帰

• スタック

• キュー

• BST(二分探索木)

• 優先度付きキュー

• ヒープ

• フィボナッチ

• ナップザック問題

• 複数回利用可能ナップザック問題

• トポロジカルソート

• ダイクストラ法

• ビタビアルゴリズム

入門編なので基本どころですね。
ここに上がってる内容はビタビはちょっと特殊ですが、それ以外はソフトウェアエンジニアなら調べなくても答えられて欲しい、基本中の基本です。

人工知能入門

前提科目：アルゴリズム分析
教科書：Artificial Intelligence A Modern Approach (3rd edition)
               Russell, Norvig著
　　　　日本語版：エージェントアプローチ人工知能

機械学習ではなく、人工知能(AI)です。前回の図が間違ってました。修正します。こちらの授業で取り上げるのは下記です。

• Agent

• 検索/探索

  • BFS/DFS/Uniform-cost Search/Depth-limited Search/Bidirectional Search

• Informed Search

  • Best-First Search/A*

• 局所探索

  • 山登り法/疑似アニーリング/ビームサーチ/遺伝子アルゴリズム/勾配降下

• 敵対探索

• 命題論理

• 確率(不確実性/推論/独立 etc…)

• ベイジアンネットワーク

• ゲーム理論

データベース入門

前提科目：Web開発
教科書：Fundamentals of Database Systems, 7th Edition 2016.
　　　　Elmarsi著

データベースの入門ですね。前提にWeb開発があるのはWebフレームワークで先にModelとかに触れてから、という感じでしょうか。
この授業では下記が身に付くとされています。

1. RDBと通常ファイルの違いが説明できる

2. ER図やUMLダイアグラムを使ってやや複雑なデータをモデル化し、そのダイアグラムからの関係スキーマを導き出せる

3. 関係スキーマからRCBを作成できる

4. RDBに複数のインデックスを作成でき、どんな時にまた何故インデックスが適切か説明できる

5. SQL文を構成し、データを操作する

6. 選択・射影・結合を使い関係代数の式を構成する

7. Web ベースのデータベースシステムのコンポーネントとインターフェースを説明する

8. PHPのようなスクリプト言語を用いてWebベースのRDBシステムをデザイン・実装する

開発者としてのRDB利用という感じですね。DBAまで踏み込んでない印象。

オペレーティングシステムI

前提科目：データ構造、アーキテクチャ＆アセンブリ言語

オペレーティング・システム、OSです。こちらはC言語の主にシステムコール周りの部分を触ってOSのファイルディスクリプタとかのファイルシステム周りであったり、Unixコマンドであったりを学びます。下記が身につくとされています。

• なぜ現代のOSでは多重プログラム実行が重要か説明できる

• 多重プログラミングOSの一般的な構成が説明できる

• システムコールの目的と処理が説明できる

• システムコールを利用するプログラムを書ける

• スクリプト言語を使ってプログラムを書ける

• 正規表現で入力データを解析する方法を説明できる

• プロセスを生成して、プロセス間で共有する変数やその他のリソースに相互排他を提供するプログラムが書ける

• ソケットを使ってクライアント・サーバーシステムの実装ができる

• 構造やI/O処理、セキュリティを含めどう一般的なファイルシステムが機能しているか説明できる

• 一般的なOSでの典型的なプロセスのメモリ構成を説明できる。

プログラミング苦手な友達がヒーヒー行ってましたが正直言うほど難しくなかったです。独学からプログラミングを始めて、見えなかった部分がかなり見えたのがこの授業です。

ソフトウェアエンジニアリングI

前提科目：データ構造

クライアントと開発会社でのロールプレイングをやったりディスカッションをメインとするクラスです。

下記のトピックを扱います。

• ソフトウェアエンジニアの紹介

• ソフトウェア開発のプロセス

•  要求分析

• ソフトウェアデザインとアーキテクチャ

• 構成とプロジェクトのマネジメント

• ソフトウェアの仕様(詳細設計？)とテスト

• ソフトウェア倫理

またコースの目的として下記が定義されています。

• 特定の状況で最も適したソフトウェアプロセスモデルを選択できる

• ソフトウェア要件をまとめ要求仕様書を作成できるUML、データフロー図、エンティティ関係図、状態図などややフォーマルな記法でシステム要件をモデル化できる

• オブジェクト指向設計やアジャイルなど、複数の手法を用いて、ソフトウェアシステムをアーキテクチャレベルかそれ以下のレベルで設計し、その設計を設計仕様書に表現することができる

• 設計を検証し、必要があれば仕様や設計を調整できる

• プログラミングのコスト見積もりとスケジュール策定の方法を説明できる

• チーム開発の環境に効果的に参加できる

• プロフェッショナル品質のソフトウェア関連ドキュメントを作成できる

• フォーマルな文書やカジュアルな文書を頻繁に作成することを通じて専門的な内容の知識やクリティカルシンキングを明確にできるようになる

• スピーチの聞き手の期待、ジャンル、学問分野でのコミュニケーションに適した慣習についての知識・理解を示せる

かなり実践的なクラスです。下手な会社よりちゃんとしてたりします。

ソフトウェアエンジニアリングII

前提科目：データ構造

バックエンド開発、特にテストやデバッグなどに絞ったソフトウェアエンジニアリングの授業です。コースの要素は下記です。

• ソフトウェア検証と妥当性確認

  • テスト計画作成

  • テストのデザインと構築

  • テスト自動化

  • ホワイトボックステスト

  • ブラックボックステスト

  • リグレッションテスト

  • ソフトウェア検査

• ソフトウェアメンテナンス

  • メンテナンスの種類

  • 構成管理

  • 構成コントロールツールの使用

  • 自動ビルドツール

  • 障害局所化戦略

  • 自動デバッグツールの使用

トピックとしては

• バージョンコントロールシステム

  • Forks, Pull requests, Branching

  • Git, GitHub

• ソフトウェアテスト概要

  • テストの考え方

  • メンテナンスとソースコントロール

  • ビルドと静的解析

  • ソフトウェアテスト紹介：テストの種類

• Code Coverage

  • カバレージメトリックス

• Softwareテスト

  • バグ報告

  • プラント戦略

  • テストの役割

  • テスターのように考える

  • テスト技法
    

• ランダムテスト

  • コンセプト

  • 簡潔なランダムテスターの書き方

• デバッグ入門

  • デバッガーの簡単な紹介

  • オープンソースプロジェクトの紹介

• 因果関係とローカライズ
  

• デバッグ

  • Agansのデバッグのルール

• Software検査

  • 統合テスト

• リグレッションテスト

  • Search based software Testing (SBST)の紹介

  • Symbolic Execution Testingの紹介

プログラミングスクールでもソフトウェアエンジニアリングI/IIみたいなことは教えるんですかね。学校も結構実用的な授業はあります。

コンピュータ・ネットワーク入門

前提科目：データ構造、コンピュータアーキテクチャとアセンブリ言語

ネットワークはなかなかディープな世界で開発者として知っていればいい部分とネットワークの専門家が知っているべき内容は差があると思います。しかし、授業になる単位だと、プログラミングに知っていればいいレベルを超えてる気がします。入門編だけどデータリンク層を意識することとか少ないのでは。

こちらの授業を受けると下記が身につきます。

• パケットスイッチングされたネットワークで

  • パケットスイッチングのコンセプトが説明できる

  • 異なる種類のパケット遅れを認識し、分析できる

• トランスポート層の基本原理(信頼性の高いデータ転送、フロー制御、輻輳制御)を背逸名できる

• ネットワーク層のパケット伝達に関し、IPアドレスを使い、最短距離のパスを見つけるルーティングアルゴリズムを適用できる

• データリンク層のサービスと複数のアクセス技法を説明し、比較できる

• ネットワークセキュリティの問題点とそれに対応するいくつかの手法を説明できる

• ネットワークプロトコルの振る舞いを監視し分析するツールを利用できる

システム管理(System Administration)

前提科目：OS I, コンピュータネットワーク入門

システム管理者に関する授業です。こんなのあったのか。
コンテンツは下記です。

• Computer

  • ハードウェアアセンブリとトラブルシューティング

  • OSインストール

  • 起動

  • シャットダウン

  • ユーザー管理

  • 権限

  • ソフトウェアトラブルシューティング

  • ログファイル

  • バックアップ手法

  • メンテナンスの要件と手法

  • レジストリとシステムファイル

  • セキュリティ

• ネットワーク

  • ハードウェア

  • 計画

  • 設置

  • WANと LAN

  • インターネット

  • トラブルシューティング

  • セキュリティ

• サーバー

  • ハードウェア

  • ユーザー管理

  • リソース管理

  • 権限

  • コマンドとコントロール

  • ドメインとグループ

  • ファイルシステム

  • 共有ファイル

  • システム仮想化

  • リモート管理

• プロジェクト

  • 計画

  • 評価

  • クライアントとの交渉と期待

  • サービスレベルアグリーメント

  • レコード管理

なかなか地味な授業…。

プログラミング言語の基礎

主にHuskelを使ったプログラミング言語自体を学ぶ授業です。

ここに関しては資料が公開されていないので、宿題をリバースエンジニアリングしながら、追記します。

内容としては授業で学んだことのHuskelの実装をもとにグループで相互にコメントしあい、それをベースにディスカッションという感じでした。実装したのは

• 木構造の実装と1増やす1減らすの構造体で再帰を学ぶ

• 末尾再帰の最適化について(末尾とそうでない場合の比較)

• 4方向に動く(仮想の)ロボットの実装と制御

• 続く・・・

ユーザビリティ工学入門

前提科目：CS概論Iもしくはシステム管理
教科書： Interaction Design, 4th Ed, Preece著

ユーザビリティを学ぶ授業です。受講していませんが、デザインやUIに関する授業です。下記の内容を学びます。

• 要求収集および分析

• プロトタイピングとインタラクティブデザイン

• ユーザビリティテスト手法と法的倫理的要求

• インターフェースの進化

このコースを受講すると下記ができるようになるとされています。

• システム設計・開発における人を中心とした設計プロセス、ユーザビリティエンジニアリングプロセスとその役割について説明できる

• ユーザビリティ設計のガイドライン、その基礎、前提、利点、弱点についてディスカッションできる

• 人を対象とした研究の基本を説明できる

• 被験者研究基本証明書を完成させられる

• 人のニーズの分析に基づくUIの設計とプロトタイプシステムの作成ができる

• ユーザビリティエンジニアリングの手法を用いてUIを評価できる

• デザインの決定の正当性を証明できる

個人的にあまり得意じゃない(深入りしたくない)分野ですが、Webでフリーランスやるなら理論的な部分もちゃんと身につけておきたいですね。

ハッキング対策

前提科目：OS I, データベース入門, コンピュータ・ネットワーク入門

新しい授業ですが、内容が公開されていません。情報がわかり次第修正します。カタログには下記とあります。

アンチマルウェア、コンピュータフォレンジック、ネットワーキング、メッセージング、Webセキュリティの現状を紹介する。コンピュータセキュリティの分野を広く紹介する。

セキュリティ

前提科目：OS I(同時受講もOK)

この授業も公開ないですね。セキュリティ関連の授業だけにセキュリティ厳し目になってるんでしょうか。

カタログには下記とあります。

コンピュータ・セキュリティの入門コースで、コンピュータ・システムのセキュリティの概念と原理を紹介することが目的。セキュリティの概念、基本的な暗号化プリミティブとその応用、認証とアクセス制御の基礎、鍵管理の基礎、マルウェアとソフトウェアセキュリティの基礎を学びます

というわけで、ちょっと今月は1本しか書けませんでしたが、4年の授業を軽く説明したら、それぞれの授業の内容を解説していきたいと思います。

今週中は少し推敲すると思いますが、時間かかってしまっているので早めに公開しておきます。