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