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