到達目標
１．アルゴリズムの効率（計算量）を理解できる。（A4)
２．基本整列法が理解でき、プログラム化できる。（A4)
３．２分探索法を理解でき、プログラム化できる。（A4)
４．再帰処理について理解でき、プログラム化できる。（A4)
５．リスト・木構造について理解でき、プログラム化できる。（A4)
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目1
達成目標１ | アルゴリズムの効率（計算量）を理解できる。 | アルゴリズムの効率（計算量）大体理解できる。 | アルゴリズムの効率（計算量）を理解できない。 |
| 評価項目2
達成目標２ | 基本整列法が理解でき、プログラム化できる。 | 基本整列法がおおよそ理解でき、簡単なプログラムが作成できる。 | 基本整列法が理解できず、プログラム化できない。 |
| 評価項目3
達成目標３ | ２分探索法を理解でき、プログラム化できる。 | ２分探索法の考え方を大凡理解でき、簡単なプログラムが作成できる。 | ２分探索法を理解できず、プログラム化できない。 |
学科の到達目標項目との関係
教育方法等
概要:
Ｃ言語の上級コースとして、整列、探索などの基本アルゴリズムから始めて、リスト、木などのデータ構造とそのアルゴリズムにいたるまでを習得させる。その問題解決技術習得のため、Ｃ言語処理系による実習を行い、それらについてのレポートを課す。
授業の進め方・方法:
予備知識：Ｃ言語の初級コースである１、２年次の情報処理をきちんと習得しておく必要がある。そのため、各自で復習しておくこと。
講義室：３Ｓ教室
授業形態：講義 および 情報処理センターでの実習
学生が用意するもの：ノート、電卓
参考書・補助教材：アルゴリズムとデータ構造 （石畑 清 岩波書店）
注意点:
評価方法：定期の試験（４回）80％、課題レポート20％により評価、60点以上を合格とする。
自己学習の指針：授業内容を復習し、毎回配布する資料の課題を解くこと。また、プログラミング技術も理解しておくこと。
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
講義の目的、開発環境設定 |
開発環境設定を行うことができる.
|
| 2週 |
Ｃ言語の復習（１） 演算子、制御構造 |
Ｃ言語の演算子、制御構造を理解し、利用できる.
|
| 3週 |
Ｃ言語の復習（２） 関数、ポインタ |
Ｃ言語の関数、ポインタを理解し、利用できる.
|
| 4週 |
アルゴリズムの効率（計算量）、設計、解析 |
アルゴリズムの効率を理解し、その優劣を判断できる.
|
| 5週 |
基礎アルゴリズム（１） 漸化式 |
漸化式を理解し、各種の式の計算ができる.
|
| 6週 |
基礎アルゴリズム（２） モンテカルロ法 |
モンテカルロ法を理解し、面積に応用計算できる.
|
| 7週 |
最大公約数（ユークリッド互除法） |
ユークリッド互除法を用いて、最大公約数を計算できる.
|
| 8週 |
中間試験 |
|
| 2ndQ |
| 9週 |
試験答案の返却と解答、整列（１）交換法・選択法 |
整列交換法・選択法を理解し、数列の整列に応用できる.
|
| 10週 |
整列アルゴリズム（２） 挿入法 |
整列挿入法の動作と高速化の原理を理解し、応用できる.
|
| 11週 |
整列アルゴリズム（３） シェルソート |
シェルソートの動作と高速化の原理を理解し、応用できる.
|
| 12週 |
整列アルゴリズム（４） マージソート |
マージソートの原理を理解し、応用できる．
|
| 13週 |
探索アルゴリズム（１） 逐次探索 |
逐次探索法を理解し、探索に応用できる.
|
| 14週 |
探索アルゴリズム（２） 番兵法 |
探索における番兵の効果を理解し、応用できる.
|
| 15週 |
探索アルゴリズム（３） ２分探索法 |
２分探索法の原理を理解し、実際の問題にに応用できる.
|
| 16週 |
期末試験 |
|
| 後期 |
| 3rdQ |
| 1週 |
試験答案の返却と解答、文字列探索アルゴリズム（１）単純法 |
文字列探索法の単純法を理解し、文字列探索に応用できる.
|
| 2週 |
文字列探索アルゴリズム（２）KMP法 |
文字列探索法の改良版KMP法を理解し、応用できる.
|
| 3週 |
文字列探索アルゴリズム（３）ボイヤ・ムーア法 |
文字列探索法の改良版ボイヤ・ムーア法を理解し、応用できる.
|
| 4週 |
ハッシュ法と衝突 |
探索法のハッシュ法と衝突を理解し、文字列探索に応用できる
|
| 5週 |
再帰処理の概要 |
再帰処理の考え方を理解し、再帰的な式の計算ができる．
|
| 6週 |
再帰解と非再帰解 |
いくつかの問題について再帰と非再帰による実装の得失を理解し応用できる．
|
| 7週 |
クイックソートの再帰実装 |
再帰によるクイックソートを理解し整列に応用できる．
|
| 8週 |
中間試験 |
|
| 4thQ |
| 9週 |
試験答案の返却と解答、データ構造とアルゴリズム（１） スタック、キュー |
データ構造のスタック、キューを理解し，実装することができる．
|
| 10週 |
データ構造とアルゴリズム（２） リスト構造 |
データ構造のリスト構造を理解し、簡単な挿入・削除ができる．
|
| 11週 |
データ構造とアルゴリズム（３） リスト構造 |
データ構造のリスト構造を、応用することができる．
|
| 12週 |
データ構造とアルゴリズム（４） 逆ポーランド記法 |
逆ポーランド記法を理解し、式の計算に応用できる．
|
| 13週 |
データ構造とアルゴリズム（５） ２分探索木 |
２分探索木を動的に作成し、文字列の探索に応用できる．
|
| 14週 |
データ構造とアルゴリズム（６） ２分探索木 |
２分探索木を再帰的に作成し、文字列探索に応用できる．
|
| 15週 |
データ構造とアルゴリズム（７） ゲーム木探索への応用 |
基本的なゲーム木探索を実装できる．
|
| 16週 |
期末試験 |
|
評価割合
| 試験 | 課題 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 80 | 20 | 0 | 0 | 0 | 0 | 100 |
| 基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 専門的能力 | 80 | 20 | 0 | 0 | 0 | 0 | 100 |
| 分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |