概要:
基礎事項として,ポインタおよび再帰について学習する。次にデータの表現方法や効率の良いアルゴリズムの実装能力を身につけるため,基本的かつ代表的なアルゴリズムとデータ構造について学習する.
授業の進め方・方法:
原則として,毎回の授業で課題の説明を行い,残りの時間はプログラムを作成する演習時間とする.ただし,計算量の解説などの一部の項目では,座学中心の授業を行う.
注意点:
原則として授業の後半でC言語によるプログラミング演習を行なう.課題が授業時間内に終わらないことも予想されるので,自宅にプログラム開発環境を構築することが望ましい.また本科目の単位を修得するためには,全ての課題を期限内に提出することが必要条件となるので注意すること.
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
ガイダンス データー構造とは アルゴリズムとは |
データ構造およびアルゴリズムの概要を理解できる
|
2週 |
単純ソート(1) バブルソート・選択ソート アルゴリズムの解説と実装 |
バブルソート・選択ソートのアルゴリズムを理解し実装できる.
|
3週 |
単純ソート(1) 選択ソート・挿入ソート アルゴリズムの解説と実装 |
選択ソート・挿入ソートのアルゴリズムを理解し実装できる.
|
4週 |
シェーカーソート アルゴリズムの解説と実装 |
シェーカーソートのアルゴリズムを理解し実装できる.
|
5週 |
シェルソート アルゴリズムの解説と実装 |
シェルソートのアルゴリズムを理解し実装できる.
|
6週 |
プログラミング演習 第5週までのプログラミング課題を引き続き作成する. |
単純ソート・シェーカーソート・シェルソートのアルゴリズムを実行効率の面で比較できる.
|
7週 |
ポインタ C言語のポインタの解説 |
C言語におけるポインタの概念を理解し使うことができる.
|
8週 |
再帰呼び出し 再帰関数の解説と簡単な例題プログラムの演習 |
再帰呼び出しの概念を理解し,簡単な再帰呼び出しプログラムが実装できる.
|
2ndQ |
9週 |
クイックソート アルゴリズムの解説と実装 |
クイックソートのアルゴリズムを理解し実装できる.
|
10週 |
計算量(1) 単純ソートの計算量の解説 |
計算量の概念を理解し,単純ソートの計算量を導き出すことができる.
|
11週 |
計算量(2) クイックソートの計算量の解説 |
クイックソートの計算量を導き出すことができる.
|
12週 |
マージソート アルゴリズムの解説と実装 |
マージソートのアルゴリズムを理解し実装できる.
|
13週 |
ヒープソート アルゴリズムの解説と実装 |
ヒープソートのアルゴリズムを理解し実装できる.
|
14週 |
単純探索と二分探索 アルゴリズムの解説と実装 |
単純探索・二分探索のアルゴリズムを理解し実装できる.
|
15週 |
計算量(3) 二分探索の計算量の解説 |
二分探索の計算量を導き出すことができる.
|
16週 |
|
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 3 | |
プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | |
主要な計算モデルを説明できる。 | 4 | |
要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 1 | |
ソフトウェア | アルゴリズムの概念を説明できる。 | 3 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 3 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 3 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 3 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 3 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 1 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 3 | |
ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |