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