概要:
プログラムを作成する上で大切なアルゴリズムとデータ構造の関係について学習する。データ構造を実現するモデル言語としてC言語を使い,実際にプログラムとして表現することによって,理論だけではなく,応用面も学習する。対象となるデータの性質から,適切なデータ表現方法・アルゴリズムを選択できる能力を学習する。
授業の進め方・方法:
教科書に沿った講義形式で授業を行うが,理解を深めるために課題(自学・自習)レポートの提出がある。
関連する授業科目にアルゴリズム演習があり,実際にプログラムを作成することで,データ構造とアルゴリズムの理解を深めることが重要である。
中間試験 40%,期末試験 40%,課題(自学・自習)20%で総合評価し,60点以上を合格とする。
注意点:
前提として,C言語によるプログラミングを理解できることが望ましい。データ構造は,プログラムにおけるデータの表現方法について学ぶ学問である。知識として理解するだけでなく,プログラムを実際に動作させることで理解を深めることが大切である。
|
|
週 |
授業内容 |
週ごとの到達目標 |
前期 |
1stQ |
1週 |
アルゴリズムの基本概念 |
アルゴリズムとデータ構造の関係を説明できる。 アルゴリズムとプログラムの関係を理解できる。
|
2週 |
アルゴリズムの評価基準 |
アルゴリズムの複雑さを表す計算量を理解できる。アルゴリズムによって計算量が変わることが理解できる。最大計算量と平均計算量の考え方が理解できる。
|
3週 |
配列と構造体 |
配列と構造体を理解し,配列と構造体の使い分けができる。
|
4週 |
連結リスト ・配列による実現 ・ポインタによる実現 ・循環リスト ・双方向リスト |
連結リストの考え方を理解できる。ポインタを使った実装方法を理解できる。循環リスト・双方向リストを説明できる。
|
5週 |
スタックとキュー
|
スタック,キュー,ハッシングを理解し,説明できる。スタックを使った数式評価の方法を説明できる。
|
6週 |
木構造の基本概念 |
木構造に関する基本的な用語を理解できる。順序木,無順序木が説明できる。3つの代表的な方法で木を探索することができる。
|
7週 |
木の探索 ・2分木探索木 ・平衡木 |
2分木を理解し,説明できる。2分探索木,平衡木を理解できる。
|
8週 |
中間試験 |
|
2ndQ |
9週 |
探索の基本概念 線形探索 2分探索 |
表を用いた代表的探索法である線形探索と2分探索を理解し,説明できる。
|
10週 |
ハッシュ法 |
ハッシュ法の考え方を理解し,説明できる。ハッシュ関数に求められる性質を理解できる。
|
11週 |
ソートの基本概念 選択ソート・挿入ソート・バブルソート クイックソート |
ソートの基本概念を理解できる。 代表的なソートアルゴリズムの特徴を説明できる。
|
12週 |
ヒープソート ソートアルゴリズムの比較 |
ソートアルゴリズムの性能評価ができる。
|
13週 |
分割統治法 ・分割統治法の考え方 ・分割統治法の例 |
分割統治法の考え方を理解できる。 分割統治法の例を理解できる。
|
14週 |
深さ優先探索 幅優先探索 |
解の列挙によるアルゴリズムについて,深さ優先探索と幅優先探索の考え方を理解する。それぞれのアルゴリズムとデータ構造の関係を理解する。
|
15週 |
正規表現 |
正規表現が表す文字クラスが理解できる。正規表現のパターンマッチを行う有限オートマトンが理解できる。
|
16週 |
|
|
分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
専門的能力 | 分野別の専門工学 | 情報系分野 | ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
アルゴリズムの概念を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
システムプログラム | 形式言語の概念について説明できる。 | 4 | |
形式言語の概念について説明できる。 | 4 | |
オートマトンの概念について説明できる。 | 4 | |
オートマトンの概念について説明できる。 | 4 | |
形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | |
形式言語が制限の多さにしたがって分類されることを説明できる。 | 4 | |
正規表現と有限オートマトンの関係を説明できる。 | 4 | |
正規表現と有限オートマトンの関係を説明できる。 | 4 | |