| 科目コード | 科 目 名 | |||||||||
| 3155 | プログラミング論III : Algorithms and Data Structure Systems | |||||||||
| 教 員 名 | 武藤義彦 : MUTO Yoshihiko | |||||||||
| 学年 | 単位・時間 | 科目区分 | 授業形態 | 学修単位 | ||||||
| 4B | 1・100分 | 必修 | 講義・後期 | ○ | ||||||
| 授業概要 | 代表的なデータ構造とアルゴリズムを学ぶと同時に，それらをJavaプログラムにおいてクラスとして実現する手法を身につける．前半は基本的なデータ構造を扱い，後半では整列や探索（照合）などのアルゴリズムの考え方および実装を説明する． | |||||||||
| 到 達 目 標 | 評 価 方 法 | |||||||||
| (1)
それぞれのデータ構造とアルゴリズムを論理的に理解できる． (2) データ構造を Java のクラスとして実装できる． (3) それぞれのアルゴリズムの特徴を説明できる． |
評価方法は，（１）中間試験，（２）期末試験，（３）レポートを評価する．評価配分は，（１）35％、（２）35％，（３）30％とする． | |||||||||
| 学習・教育目標 | D① | JABEE基準１（１） | (d)-(3) | |||||||
| 授 業 計 画 | 回 | 項 目 | 内 容 | |||||||
| イントロダクション | データ構造とアルゴリズムの必要性，OOPの用語や考え方の整理，this オブジェクト，オーダ記法 | |||||||||
| 第１ | ||||||||||
| 計算量 | 線形探索，二分探索を例とした計算量の求め方 | |||||||||
| 第２ | ||||||||||
| 連結リスト(1) | 単方向連結リストの概念，基本メソッドの理解 | |||||||||
| 第３ | ||||||||||
| 連結リスト(2) | 単方向連結リストへのメソッドの追加（要素の探索，削除） | |||||||||
| 第４ | ||||||||||
| 連結リスト(3) | 双方向連結リストの概念の理解と実装 | |||||||||
| 第５ | ||||||||||
| ハッシュ(1) | ハッシュ関数，チェイン法（分離連鎖法）の概念と実装の理解 | |||||||||
| 第６ | ||||||||||
| ハッシュ(2) | 再ハッシュ，オープンアドレス法（空き番地法）の概念と実装の理解 | |||||||||
| 第７ | ||||||||||
| 中間まとめ | 中間まとめとして試験を実施する | |||||||||
| 第８ | ||||||||||
| ハッシュ(3) | ハッシュ法の実問題への適用（演習） | |||||||||
| 第９ | ||||||||||
| 整列(1) | バブルソート，選択ソート，挿入ソートの概念と実装の理解 | |||||||||
| 第１０ | ||||||||||
| 整列(2) | シェルソート，クイックソートの概念と実装の理解 | |||||||||
| 第１１ | ||||||||||
| 整列(3) | 基数ソートの概念と実装の理解 | |||||||||
| 第１２ | ||||||||||
| 文字列照合 | bruto-force アルゴリズム，Boyer-Moore法の概念と実装の理解 | |||||||||
| 第１３ | ||||||||||
| 動的計画法 | 動的計画法によるナップザック問題の解法 | |||||||||
| 第１４ | ||||||||||
| まとめ | 全体の学習事項のまとめと授業評価アンケート調査を行う | |||||||||
| 第１５ | ||||||||||
| 関連科目 | ||||||||||
| 教 科 書 | 近藤嘉雪，Javaプログラマのためのアルゴリズムとデータ構造，ソフトバンク | |||||||||
| 参 考 書 | 広瀬貞樹，あるごりずむ，近代科学社 | |||||||||
| 授業評価・理解度 | 最終回に授業評価アンケートを行う． | |||||||||
| 副担当教員 | ||||||||||
| 備 考 | 適宜プリントを配布する | |||||||||