到達目標
1. 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。
2. 整列、探索など、基本的なアルゴリズムについて説明できる。
3. リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明できる。
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
評価項目1 | アルゴリズムの時間計算量や領域計算量を正確に計算し、適切にアルゴリズムの比較・評価できる。 | アルゴリズムの時間計算量や領域計算量を計算し、ある程度アルゴリズムの比較・評価を行うことができる。 | アルゴリズムの時間計算量や領域計算量を計算することができず、アルゴリズムの比較・評価を行うことができない。 |
評価項目2 | 整列、探索などの基本的なアルゴリズムについて適切に説明でき、独力でプログラムとして実装できる。 | 整列、探索などの基本的なアルゴリズムについて説明でき、例題が与えられればプログラムとして実装できる。 | 整列、探索などの基本的なアルゴリズムについて説明することができず、プログラムとして実装することができない。 |
評価項目3 | リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を適切に説明でき、独力でプログラムとして実装できる。 | リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明でき、例題が与えられればプログラムとして適切に実装できる。 | リスト構造、スタック、キューなどの基本的なデータ構造の概念と操作を説明することができず、プログラムとして実装することができない。 |
学科の到達目標項目との関係
教育方法等
概要:
アルゴリズムとデータ構造の基礎概念を理解し、例題や演習を通してアルゴリズムを設計する能力を身につけ、効率のよいプログラムを作成する能力を習得する。アルゴリズムの概念や与えられたアルゴリズムが問題を解決していく過程を説明できること、データ構造にはバリエーションがあることを理解し、基本的なデータ構造の概念と操作を説明できることを到達レベルとする。
授業の進め方・方法:
注意点:
C言語を用いて説明するので,プログラミング入門及びプログラミング基礎で学習した内容を十分復習しておくこと。
関連する科目:
プログラミング入門,プログラミング基礎,応用プログラミングA,オブジェクト指向プログラミング,プログラミング言語論,オペレーティングシステム,数値解析
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
ガイダンス (1h) アルゴリズムの基礎 (コア) ・アルゴリズムの評価基準 |
アルゴリズムの善し悪しについて説明できる。
|
2週 |
・計算量の漸近的評価 |
アルゴリズムの計算量を説明できる。
|
3週 |
基本データ構造 (コア) ・スタック,キュー、連結リスト |
スタック,キュー、連結リストについて説明できる。
|
4週 |
・木構造 |
木構造について説明できる。
|
5週 |
データの探索 (コア) ・線形探索、2分探索 |
線形探索,2分探索によるデータ探索を説明できる。
|
6週 |
・2分探索木 |
2分探索木によるデータ探索を説明できる。
|
7週 |
・ハッシュ法 |
ハッシュ法によるデータ探索を説明できる。
|
8週 |
前期中間試験 |
|
2ndQ |
9週 |
試験答案返却・解答解説 (1h) ソートアルゴリズム (コア) ・ソートの定義、選択ソート (1h) |
・間違った問題の正答を求めることができる
ソートの定義、選択ソートの動作を説明できる。
|
10週 |
・バブルソート、挿入ソート |
バブルソート、挿入ソートの動作を説明できる。
|
11週 |
・シェルソート、シェーカーソート |
シェルソート、シェーカーソートの動作を説明できる。
|
12週 |
・ヒープ |
データ構造ヒープを説明できる。
|
13週 |
・ヒープソート |
ヒープソートの動作を説明できる。
|
14週 |
・クイックソート |
クイックソートの動作を説明できる。
|
15週 |
前期期末試験答案返却・解答解説 |
・間違った問題の正答を求めることができる
|
16週 |
|
|
後期 |
3rdQ |
1週 |
アルゴリズムの設計手法 ・分割統治法 |
分割統治法、マージソートについて説明できる。
|
2週 |
・グリーディ法 |
グリーディ法について説明できる。
|
3週 |
・動的計画法 |
動的計画法について説明できる。
|
4週 |
・動的計画法 |
動的計画法を用いて問題が解ける。
|
5週 |
・バックトラック法 |
バックトラック法について説明できる。
|
6週 |
・分枝限定法 |
バックトラック法および分枝限定法を用いて問題が解ける。
|
7週 |
・演習問題 |
分割統治法、グリーディ法、動的計画法、バックトラック法を用いて問題が解ける。
|
8週 |
後期中間試験 |
|
4thQ |
9週 |
試験答案返却・解答解説 (1h) 文字照合アルゴリズム ・基本的なアルゴリズム (1h) |
もっとも基本的なアルゴリズムを説明できる。
|
10週 |
・KMP法 |
KMP法による文字照合について説明できる。
|
11週 |
・BM法 |
BM法による文字照合について説明できる。
|
12週 |
・BM法 |
BM法による文字照合について説明できる。
|
13週 |
・連結リスト |
C言語で連結リストを実装できる。
|
14週 |
・連結リスト |
C言語で連結リストを実装できる。
|
15週 |
後期期末試験答案返却・解答解説 |
・間違った問題の正答を求めることができる
|
16週 |
|
|
モデルコアカリキュラムの学習内容と到達目標
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | 前1 |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | 前1 |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | 前1 |
時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。 | 3 | 前2 |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | 前5 |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | 前3 |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | 前3 |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 3 | 前3 |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | 課題 | 合計 |
総合評価割合 | 80 | 0 | 0 | 0 | 0 | 20 | 100 |
基礎的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
専門的能力 | 80 | 0 | 0 | 0 | 0 | 20 | 100 |
分野横断的能力 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |