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