| 授業の目標と概要 |
・この授業の目標は，各データ構造の特徴とそれらの適用領域の違い
を理解すること．さらに，探索やソーティング，文字検索等の基本的
なアルゴリズム学習し，計算量の概念を応用して各種アルゴリズムの
評価，解析を行えるようになること．また，最適化問題の定式化や効
率的解を習得することである．
・プログラミング言語実習に必要な基礎知識を習得する．
|
履修上の注意
(準備する用具・
前提とする知識等)
|
・本科低学年で履修する情報（離散）数学の基礎知識を必須とする．
・手続き型のプログラミング言語の知識を習得していると望ましい．
・関数機能付き電卓を必要とする．
・章ごとに演習問題を与える．小テストは実施しない．
|
| 到達目標 |
・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・データ構造各種の特性や効率的なデータアクセス法を理解できる．
・基本的アルゴリズムの設計や評価ができる．
|
| 成績評価方法 |
定期試験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. 整数最適化問題の最適化解法を理解する．
|
| 後期期末試験 |
実施する
|