シラバス
アルゴリズム基礎(前期2単位)
教授 大久保隆夫 教授 松井俊浩
1.授業のねらい・到達目標
コンピュータの内部では与えられた手順に従い膨大な計算処理が行われている。アルゴリズムとはその計算手順のことであり、アルゴリズム論は「より良い」計算手順を研究する学問である。よりよいプログラミング、セキュリティシステムの構築にもアルゴリズムが設計できることが必要であり、また暗号理論等でもアルゴリズム解析は必要となる。本授業はアルゴリズムの設計解析手法、効率的な基本アルゴリズム等について解説する。
2.到達目標
データ構造の基礎、および、データ構造を活用した既存のソーティングアルゴリズムの仕組み、およびその実行時間の違いについて理解する。
また、実行時間の求め方と基礎的なグラフアルゴリズムについて理解する。
3.授業計画
第1回 | アルゴリズム基礎概論 |
第2回 | データ構造(1) 配列、挿入ソート,スタック・キュー、連結リスト |
第3回 | データ構造(2) ハッシュ表、ハッシュ関数 |
第4-5回 | データ構造(3) 2分探索木、2色木 |
第6回 | アルゴリズムの解析、漸近記法 |
第7回 | ソートアルゴリズムと実行時間(1) マージソート、クイックソート |
第8回 | 漸化式の解き方 置き換え法、再帰木法、分類法 |
第9-10回 | ソートアルゴリズムと実行時間(2) 順序統計量、ヒープソート、計数ソート |
第11回 | グラフアルゴリズムの基礎 BFS,DFS |
第12回 | Lispによる再帰と動的計画法 |
第13回 | ハフマン符号と情報圧縮 |
第14回 | 文字列アルゴリズム -Boyer-Moore文字列検索アルゴリズム、動的計画法による文字列の変換 |
第15回 | トポロジカルソートとDijkstraの最短経路アルゴリズム |
4.教科書
特に指定しない。
5.参考書
- ニクラウス ヴィルト、 アルゴリズムとデータ構造、近代科学社、1990年
- Cormen, Leisrson, Rivest, Stein. Introduction to Algorithms 2nd ed., MIT Press, 2001.
- トーマス H. コルメン、アルゴリズムの基本、日経BP社、2016年
- 杉原厚吉、データ構造とアルゴリズム、共立出版、2001年
- Donald Knuth, The Art of Computer Programming, Vol.1~4、(訳)有沢誠、和田英一、その他、ASCII出版、2015
6.関連科目
コンピュータ及びプログラミングに関する基礎知識を有することが望ましいが、これらについての知識を適宜補いながら授業を進める。
7.成績評価の方法
毎回の小テスト(45%)、それぞれの担当ごとのレポート(45%)により評価する。
なお、ディスカッションなど講義への積極的な参加も評価対象とする(10%)。
Copyright © INSTITUTE of INFORMATION SECURITY. All rights Reserved.