到達目標
・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・データ構造各種の特性や効率的なデータアクセス法を理解できる．
・問題ごとに効率的アルゴリズムの設計や評価ができる．
ルーブリック
| 理想的な到達レベルの目安 | 標準的な到達レベルの目安 | 未到達レベルの目安 |
| 基本的なアルゴリズムや再帰アルゴリズムの動作や計算量解析の理解ができる． | 基本的なアルゴリズムや再帰アルゴリズムの動作を理解できる． | 基本的なアルゴリズムの動作を理解できない． |
| データ構造各種の特性や効率的なデータアクセス法を理解できる． | データ構造各種の効率的なデータアクセス法を理解できる | データ構造のデータアクセスの特性を理解できない． |
| 与えられた問題ごとに最適・効率的アルゴリズムの設計や評価ができる． | 与えられた問題ごとに効率的アルゴリズムの設計や評価ができる． | 与えられた問題に対するアルゴリズムの設計ができない． |
学科の到達目標項目との関係
教育方法等
概要:
この授業の目標を以下に示す．
・各データ構造の特徴とそれらの適用領域の違いを理解できること．
・計算量の概念を応用して各種アルゴリズムの評価，解析を行えるようになること．
・探索やソーティング，文字検索等の基本的なアルゴリズムを理解できること．
・最適化問題の定式化や効率的解を習得すること．
・プログラミング言語実習に必要な基礎知識を習得すること．
授業の進め方・方法:
プレゼンスライドと黒板板書の両方を使った講義形式でおこなう．
小セクションごとに演習問題を与える．
定期試験直前には総合的な演習を行う．
暗記ではなく論理の積み重ねで問題を考える習慣をつける．
成績評価方法：
定期試験2回の成績で行う．
中間試験(50%)，期末試験(50%)
合否判定：最終評価（または再試験の素点）≧60％を合格とする．
注意点:
基本的な離散数学の知識が必要である．
手続き型プログラミング言語の知識があること．
講義は基本的にプロジェクタを利用して行う．
授業計画
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
計算理論 1 |
アルゴリズム・手続きの概念を理解できる．
|
| 2週 |
計算理論 2 |
O記号の意味と，多項式時間，指数式時間の差異を理解できる．
|
| 3週 |
計算理論 3 |
様々なアルゴリズムの計算量解析を行える．
|
| 4週 |
データ構造 1 |
配列，リスト，スタック，キューなどの基本的なデータ構造を理解できる．
|
| 5週 |
データ構造 2 |
スタックを活用した逆ポーランド表記の記述ができる．
|
| 6週 |
データ構造 3 |
木構造と木のなぞりアルゴリズムを理解できる．
|
| 7週 |
探索アルゴリズム 1 |
様々な基本的なデータ探索技法を理解できる．
|
| 8週 |
中間試験 |
これまでの学習の理解度を深める．
|
| 2ndQ |
| 9週 |
探索アルゴリズム 2 |
平衡木を活用した探索技法を理解できる．
|
| 10週 |
探索アルゴリズム 3 |
ハッシュを活用した探索技法を理解できる．
|
| 11週 |
ソーティング 1 |
基本的なソート手法(選択・挿入・バブルソート)を理解できる．
|
| 12週 |
ソーティング 2 |
改良されたソート手法(シェーカー・シェル・自書式順序)を理解できる．
|
| 13週 |
ソーティング 3 |
高速なソート手法(ヒープ・マージ・クイック)を理解できる．
|
| 14週 |
文字列探索 1 |
力まかせの方法・KMP法を理解できる．
|
| 15週 |
文字列探索 2 |
BM法を理解し，計算量解析を行える．
|
| 16週 |
期末試験 |
この講義の理解度・目標達成度を確認するため，試験を実施する．
|
モデルコアカリキュラムの学習内容と到達目標
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 代入や演算子の概念を理解し、式を記述できる。 | 3 | |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | |
| 変数の概念を説明できる。 | 3 | |
| データ型の概念を説明できる。 | 3 | |
| 制御構造の概念を理解し、条件分岐を記述できる。 | 3 | |
| 制御構造の概念を理解し、反復処理を記述できる。 | 3 | |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 3 | |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 3 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 3 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 3 | |
| 情報数学・情報理論 | 離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。 | 4 | |
| コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。 | 4 | |
評価割合
| 試験 | 発表 | 相互評価 | 態度 | ポートフォリオ | その他 | 合計 |
| 総合評価割合 | 100 | 0 | 100 |
| 専門的能力 | 100 | 0 | 100 |