到達目標
1. 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している．
2. 整列，探索など，基本的なアルゴリズムについて説明できる．
3. リスト構造，スタック，キューなどの基本的なデータ構造の概念と操作を説明できる．
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 評価項目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 |
| 計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | 前1 |
| コンピュータ内部でデータを表現する方法（データ構造）にはバリエーションがあることを理解し、基本的なデータ構造の概念と操作を説明できる。 | 4 | 前3,前4 |
評価割合
| 試験 | 授業中の演習課題 | 相互評価 | 態度 | ポートフォリオ | 課題 | 合計 |
| 総合評価割合 | 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 |