シラバス GRADUATE SCHOOL
アルゴリズム基礎（前期2単位）
教授 盛合 敏
１．授業のねらい
アルゴリズムとは、問題を解くための手順を曖昧な点が残らないように定めたものである。本授業では、さまざまなプログラムで利用される基本的なアルゴリズムとアルゴリズムの解析手法について学ぶ。それによって、効率が良く、セキュアなシステムを構築するために、問題に即した優れたアルゴリズムを設計・選択できることを目指す。
２．到達目標
データ構造とそれを操作するアルゴリズムの基礎、そして、さまざまなソートアルゴリズムの仕組みと実行時間の違いについて理解する。また、分割統治法、動的計画法、および、貪欲法などの設計パラダイムについて理解する。
３．授業計画と開講形態
第1回 アルゴリズム基礎概論
第2回 データ構造(1)
配列、挿入ソート、スタック・キュー、連結リスト
第3回 データ構造(2)
ハッシュ表、ハッシュ関数
第4回 データ構造(3)
2分探索木
第5回 データ構造(4)
赤黒木
第6回 アルゴリズムの解析、漸近記法
第7回 ソートアルゴリズムと実行時間(1)
マージソート、クイックソート
第8回 漸化式の解き方
置き換え法、再帰木法、分類法
第9-10回 ソートアルゴリズムと実行時間(2)
順序統計量、ヒープソート、計数ソート
第11回 グラフアルゴリズム(1)
グラフの表現、幅優先探索、深さ優先探索
第12回 再帰と動的計画法
第13回 ハフマン符号と情報圧縮
第14回 文字列アルゴリズム
第15回 グラフアルゴリズム(2)
トポロジカルソート、最短経路探索
なお順序は、進度等によって変更することがある。
４．教科書
特に指定しない。
５．参考書
- 杉原厚吉、“データ構造とアルゴリズム”、共立出版、2001年、ISBN 978-4320120341
- エイホ、ホップクロフト、ウルマン、“データ構造とアルゴリズム”、培風館、1987年、ISBN 978-4563007911
- ナラシンハ・カルマンチ、“入門 データ構造とアルゴリズム”、オライリージャパン、2013年、ISBN 978-4873116341
- コルメン、ライザーソン、リベスト、シュタイン、“アルゴリズム イントロダクション 第4版”、近代科学社、2024年、ISBN 978-4764906495
- Donald Knuth, “The Art of Computer Programming, Vol.1,2,3,4A,4B”、KADOKAWA、2015～2023年
６．関連科目
コンピュータ及びプログラミング言語（C、C++、Java、Javascript、Python 等）に関する基礎知識を有することが望ましい。
７．成績評価の方法
毎回の小テスト(40%)とレポート（40％）により総合的に評価する。
なお、ディスカッションなど講義への積極的な参加も評価対象とする（20％）。
８．その他
小テストには、Google Classroom を用いる。