| 授業の目標と概要 |
・ソフトウエア開発やプログラミングにおいて，ソフトウエア化の対象となる実モデルや関係をグ
ラフツールを用いて定式化，解析する能力や，その問題に最適なデータ構造とアルゴリズムの構築
を行える能力の習得を目的とする．
・探索やソーティング，文字検索等の基本的なアルゴリズムを学習し，計算量の概念を応用して各
種アルゴリズムの評価，解析を行う．また，グラフ理論の技法を使って問題の定式化や解析を行
う．
|
履修上の注意
(準備する用具・
前提とする知識等)
|
・本科低学年で履修する情報数学（離散数学）の基礎知識を必須とする．
・手続き型のプログラミング言語の知識を習得していると望ましい．
|
| 到達目標 |
・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・データ構造各種の特性や効率的なデータアクセス法を理解できる．
・グラフ構造の名称や基本的な特性について理解できる．
・パス問題，木構築問題，彩色問題に関する定理や解法を理解できる．
|
| 成績評価方法 |
定期試験4回の成績で行う．
前期中間(25%)，前期期末(25%)，後期中間(25%)，学年末(25%)
合否判定：最終評価≧60％
|
| テキスト・参考書 |
教科書：アルゴリズムとデータ構造 C言語版 平田富夫著 森北出版
参考書：グラフ理論入門 R.J.ウイルソン 近代科学社
|
| メッセージ |
・基本的な離散数学の知識が必要である．
・手続き型のプログラミング言語についての知識を習得していると望ましい．
・講義は基本的にプロジェクタを利用して行う．
|
| 授業の内容 |
授業項目 | 授業項目ごとの達成目標 |
1. アルゴリズム・手続きの定義，その優劣(2)
2. 計算量理論，O記号，多項式時間，指数式時間(2)
3. 計算量解析，再帰的アルゴリズムの計算量(2)
4. データ構造 基本データ構造，配列，リスト(2)
5. スタック，キュー, 逆ポーランド表記法(2)
6. 木構造 木のなぞりアルゴリズム(2)
7. 線形探索，二分探索，ハッシング(2)
|
1. アルゴリズムと手続き，その評価を理解する．
2. オーダ記号による時間的計算量の評価ができる.
3. 各種アルゴリズムの計算量解析ができる．
4. 配列，リストの特性やアクセス法を理解する．
5. キューやスタックの応用例を理解する．
6. 先行順，後行順，中間順のなぞりができる．
7. 各種探索や最適なデータ構造について理解する．
|
| 前期中間試験 |
実施する
|
8. ニ分木探索，平衡木，AVL木探索(2)
9. ソーティング1 バケット，基数，選択(2)
10. ソーティング2 挿入，バブル，シェーカ(2)
11. ソーティング3 シェル，ヒープ，マージ(2)
12. 文字列探索1 力まかせの方法，KMP法(2)
13. 文字列探索2 ボイヤームーア法(2)
14. ダイナミックプログラミング(2)
|
8. 平衡木を利用した探索アルゴリズムを理解する．
9. 各種ソート法の原理と計算量を理解する．
10. 各種ソート法の原理と計算量を理解する．
11. 各種ソート法の原理と計算量を理解する．
12. KMP法の文字列探索とその計算量を理解する．
13. BM法の文字列探索とその計算量を理解する.
14. DPによる効率的なアルゴリズム構造を理解する．
|
| 前期期末試験 |
実施する
|
15. グラフ理論概論 単純グラフ，一般グラフ(2)
16. 握手定理，同形，除去，縮約(2)
17. グラフの種類（完全，二部，星，連結）(2)
18. 歩道，小道，道，カットセット，橋(2)
19. オイラーグラフ，セミオイラーグラフ(2)
20. ハミルトングラフ，セミハミルトングラフ(2)
21. 最短経路問題，郵便配達員問題(2)
|
15. グラフ理論における用語や定義を学習する．
16. 同形の意味や除去，縮約等の操作を理解する．
17. グラフの種類やその特性について理解する．
18. 歩道，小道，道，カット，橋の定義を理解する．
19. オイラーグラフの必要十分条件を理解する.
20. ハミルトン問題の困難性を理解する.
21. 最短経路問題，郵便配達員問題の解を導出できる.
|
| 後期中間試験 |
実施する
|
22. 木，林の定義 木の性質，全域木，閉路階級(2)
23. 深さ優先探索木，幅優先探索木(2)
24. 最小全域木問題，電気回路解析の応用(2)
25. 平面グラフ，交差数，オイラーの公式(2)
26. グラフの厚さ 平面グラフに関する定理(2)
27. グラフの彩色問題，彩色数，Brooksの定理(2)
28. 面彩色と辺彩色，Vizingの定理(2)
|
22. 基本的な木構造の特性を理解する．
23. 深さ優先探索木，幅優先探索木を構築できる．
24. 最小全域木問題の解法や電気回路解析ができる．
25. 平面グラフの特性や，その応用例を理解する．
26. 平面グラフに関する様々な定理を理解する．
27. 彩色問題の困難性やBrookの定理を理解する．
28. 面辺彩色の特性やVizingの定理を理解する．
|
| 後期期末試験 |
実施する
|