| 授業の目標と概要 |
・この授業の目標は，各データ構造の特徴とそれらの適用領域の違いを理解すること．さらに，探
索やソーティング，文字検索等の基本的なアルゴリズム学習し，計算量の概念を応用して各種アル
ゴリズムの評価，解析を行えるようになること．また，最適化問題の定式化や効率的解を習得する
ことである．
・この授業ではプログラミング言語実習に必要な基礎知識を習得する．
|
履修上の注意
(準備する用具・
前提とする知識等)
|
・本科低学年で履修する情報数学（離散数学）の基礎知識を必須とする．
・手続き型のプログラミング言語の知識を習得していると望ましい．
・関数機能付き電卓を必要とする．
・章ごとに演習問題を与える．小テストは実施しない．
|
| 到達目標 |
・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・データ構造各種の特性や効率的なデータアクセス法を理解できる．
・基本的アルゴリズムの設計や評価ができる．
|
| 成績評価方法 |
定期試験4回の成績で行う．
前期中間(25%)，前期期末(25%)，後期中間(25%)，学年末(25%)
合否判定：最終評価（または，再試験の素点）≧60％を合格とする．
|
| テキスト・参考書 |
教科書：データ構造とアルゴリズム 五十嵐健夫 数理工学社
参考書：コンピュータアルゴリズム 津田和彦 共立出版
参考書：アルゴリズムとデータ構造 平田富夫 森北出版
自習用：アルゴリズム論 浅野哲夫 オーム社
|
| メッセージ |
・基本的な離散数学の知識が必要である．
・手続き型のプログラミング言語についての知識を習得していると望ましい．
・講義は基本的にプロジェクタを利用して行う．
|
| 授業の内容 |
授業項目 | 授業項目ごとの達成目標 |
1. アルゴリズム・手続きの定義，その優劣(2)
2. 計算量理論，O記号，多項式時間，指数式時間(4)
3. 計算量解析，再帰的アルゴリズムの計算量(4)
4. データ構造 基本データ構造，配列，リスト(4)
5. スタック，キュー, 逆ポーランド表記法(2)
|
1. アルゴリズムと手続き，その評価を理解する．
2. オーダ記号による時間的計算量の評価ができる.
3. 各種アルゴリズムの計算量解析ができる．
4. 配列，リストの特性やアクセス法を理解する．
5. キューやスタックの応用例を理解する．
|
| 前期中間試験 |
実施する
|
6. 木構造 木のアルゴリズム(8)
7. ソーティング1 バケット，基数，選択(2)
8. ソーティング2 挿入，バブル，シェーカ(2)
9. ソーティング3 シェル，ヒープ，マージ(2)
|
6. 木の構築や平衡木を利用した探索アルゴリズムを理解する．
7. 各種ソート法の原理と計算量を理解する．
8. 各種ソート法の原理と計算量を理解する．
9. 各種ソート法の原理と計算量を理解する．
|
| 前期期末試験 |
実施する
|
10. 文字列探索1 力まかせの方法，KMP法(2)
11. 文字列探索2 ボイヤームーア法(2)
12. ダイナミックプログラミング(4)
13. スケジューリングアルゴリズム(6)
|
10. KMP法の文字列探索とその計算量を理解する．
11. BM法の文字列探索とその計算量を理解する.
12. DPによる効率的なアルゴリズム構造を理解する．
13. スケジューリングの定式化と解法を理解する．
|
| 後期中間試験 |
実施する
|
14. 離散最適化アルゴリズム(8)
15. 整数離散最適化アルゴリズム(8)
|
14. 最大化，最小化問題の最適化解法を理解する．
15. 整数最適化問題の最適化解法を理解する．
|
| 後期期末試験 |
実施する
|