到達目標
１．代表的なデータ構造（スタック、キュー、リスト、木、ヒープ）の概念を説明でき、それらの一部をプログラムとして実現できること
２．整列、探索等の問題を解くためのアルゴリズムを説明でき、それらの一部をプログラムとして実現できること
３．計算量、再帰等について説明できること
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安(可) | 未到達レベルの目安 |
| 評価項目1 | 代表的なデータ構造（スタック、キュー、リスト、木、ヒープ）の概念を明確に説明でき、それらの一部を実用的なプログラムとして実現できる | 代表的なデータ構造（スタック、キュー、リスト、木、ヒープ）の概念を説明でき、それらの一部をプログラムとして実現できる | 代表的なデータ構造（スタック、キュー、リスト、木、ヒープ）の概念を説明できない。また、それらの一部をプログラムとして実現できない |
| 評価項目2 | 整列、探索等の問題を解くためのアルゴリズムを明確に説明でき、それらの一部を実用的なプログラムとして実現できること | 整列、探索等の問題を解くためのアルゴリズムを説明でき、それらの一部をプログラムとして実現できる | 整列、探索等の問題を解くためのアルゴリズムを説明できない。また、それらの一部をプログラムとして実現できない |
| 評価項目3 | 計算量、再帰等について明確に説明できる。また、主要なアルゴリズムの計算量を求めることができ、比較的複雑な再帰関数を記述できる。 | 計算量、再帰等について説明できる。また、基本的なアルゴリズムの計算量を求めることができ、簡単な再帰関数を記述できる。 | 計算量、再帰等について説明できない。また、基本的なアルゴリズムの計算量を求めることができず、簡単な再帰関数を記述できない。 |
学科の到達目標項目との関係
学習教育到達目標 B-2
説明
閉じる
学習教育到達目標 C-1
説明
閉じる
教育方法等
概要:
本授業では、情報科学分野の基礎であるアルゴリズムならびにデータ構造について学習する。コンピュータに何らかの問題を解かせる場合、計算の手順（アルゴリズム）を設計する必要がある。その際、問題に適したデータ構造（メモリ上のデータ表現形式）を採用することになる。アルゴリズムをプログラムとして表現し、コンピュータで実行して問題の解を得る。
授業の進め方・方法:
本授業では、アルゴリズムに関する基本概念である計算量、再帰、基本的なデータ構造、整列や探索のアルゴリズムについて学ぶ。
注意点:
理論だけではなく、プログラミング演習を通して実践的な力を付けることも目指す。
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
ガイダンス，再帰 |
・再帰とは何であるかを説明できる
|
| 2週 |
再帰 |
・再帰関数が記述できる
|
| 3週 |
再帰 |
・再帰関数が記述できる
|
| 4週 |
再帰 |
・再帰関数の呼び出し回数がカウントできる
|
| 5週 |
アルゴリズムの基本概念 |
・アルゴリズムの概念を説明できる
・データ構造とは何かを説明できる
|
| 6週 |
アルゴリズムの基本概念 |
・計算量を説明できる
・O記法を説明できる
|
| 7週 |
前期中間試験 |
|
| 8週 |
試験返却
アルゴリズムの基本概念 |
・問題の解答を通じて理解を深める
・アルゴリズムの計算量を求めることができる
|
| 2ndQ |
| 9週 |
スタック |
・データ構造の一つであるスタックを説明できる
|
| 10週 |
スタック |
・スタックのプログラムを記述できる
|
| 11週 |
スタック |
・スタックのプログラムを記述できる
|
| 12週 |
キュー |
・データ構造の一つであるキュー（待ち行列）を説明できる
|
| 13週 |
キュー |
・キューのプログラムを記述できる
|
| 14週 |
キュー |
・キューのプログラムを記述できる
|
| 15週 |
前期末試験 |
|
| 16週 |
テスト返却と解説 |
・問題の解答を通じて理解を深める
|
| 後期 |
| 3rdQ |
| 1週 |
リスト |
・データ構造の一つであるリストを説明できる
|
| 2週 |
リスト |
・リストのプログラムを記述できる
|
| 3週 |
リスト |
・リストのプログラムを記述できる
|
| 4週 |
リスト |
・リストのプログラムを記述できる
|
| 5週 |
整列 |
・整列とは何かを説明できる
・素朴な整列アルゴリズム（交換法、選択法、挿入法）を説明できる。
|
| 6週 |
整列 |
・素朴な整列アルゴリズムの関数を記述できる
・素朴な整列アルゴリズムにおける比較回数、交換回数等をカウントできる
|
| 7週 |
後期中間試験 |
|
| 8週 |
テスト返却
整列 |
・問題の解答を通じて理解を深める
・整列のプログラムを記述できる
|
| 4thQ |
| 9週 |
整列 |
・洗練された整列アルゴリズム（クイックソート、ヒープソート）を説明できる
・ヒープソートで使われる、データ構造の一つであるヒープを説明できる
・クイックソートの関数を記述できる
|
| 10週 |
整列 |
・CPU時間で各アルゴリズムを比較し、その計算量について考察できる
|
| 11週 |
探索 |
・探索とは何かを説明できる
・線形探索を説明できる
・二分探索を説明できる
・線形探索と二分探索の関数を記述できる
|
| 12週 |
探索 |
・データ構造の一つである木を応用した二分探索木を説明できる
|
| 13週 |
探索 |
・二分探索木のプログラムを記述できる
|
| 14週 |
探索 |
・ハッシュ法を説明できる
|
| 15週 |
学年末試験 |
|
| 16週 |
テスト返却と解説 |
・問題の解答を通じて理解を深める
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | |
| 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。 | 3 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 3 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 3 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 3 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 2 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 2 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 80 | 0 | 0 | 0 | 20 | 0 | 100 |
| 専門的能力 | 80 | 0 | 0 | 0 | 20 | 0 | 100 |