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