概要:
プログラムを作成する上で大切なアルゴリズムとデータ構造の関係について学習する。データ構造を実現するモデル言語としてＣ言語を使い，実際にプログラムとして表現することによって，理論だけではなく，応用面も学習する。対象となるデータの性質から，適切なデータ表現方法・アルゴリズムを選択できる能力を学習する。
授業の進め方・方法:
教科書に沿った講義形式で授業を行うが，理解を深めるために課題（自学・自習）レポートの提出がある。
関連する授業科目にアルゴリズム演習があり，C言語を使ってプログラムを作成することで，データ構造の理解を深める．
注意点:
前提として，Ｃ言語によるプログラミングを理解できることが望ましい。データ構造は，プログラムにおけるデータの表現方法について学ぶ学問である。知識として理解するだけでなく，プログラムを実際に動作させ理解を深めることが大切である。
中間試験 40%，期末試験 50%，課題（自学・自習）10%で総合評価し，60点以上を合格とする。
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
データ構造とアルゴリズムの関係
データの構造的関係
メモリ上でのデータの表現
データ型とデータ構造 |
アルゴリズムとデータ構造の関係を説明できる。
|
| 2週 |
データ操作のプログラム
・アルゴリズムの効率 |
アルゴリズムによって計算量が変わることが理解できる。アルゴリズムの複雑さを表す計算量を理解できる。最大計算量と平均計算量の考え方が理解できる。
|
| 3週 |
グラフと木 |
グラフと木構造の違いを理解できる。
|
| 4週 |
表と情報探索
・逐次探索
・線形順序と２分探索 |
配列を使った表探索手法である逐次探索と２分探索を理解でき，その計算量を説明できる。番兵の考え方を理解できる。
|
| 5週 |
リスト
・結合リスト
・配列による実現
・ポインタによる実現
・循環リスト
・双方向リスト
|
結合リストの考え方を理解できる。ポインタを使った実装方法を理解できる。循環リスト・双方向リストを説明できる。
|
| 6週 |
スタック
・算術式の評価
キュー
ハッシング |
スタック，キュー，ハッシングを理解し，説明できる。スタックを使った数式評価の方法を説明できる。
|
| 7週 |
中間試験 |
|
| 8週 |
木構造
木の基本概念 |
木構造に関する基本的な用語を理解できる。順序木，無順序木が説明できる。３つの代表的な方法で木を探索することができる。
|
| 2ndQ |
| 9週 |
木の探索
・２分木の探索
・一般の木の探索
２分木の表現 |
２分木を理解し，説明できる。ポインタを用いた２分木の表現方法を理解できる。
|
| 10週 |
一般の木の表現
・ポインタによる木の表現
・木の環状表現
・配列による木の表現 |
木構造の表現方法を理解できる。ポインタを用いた木の表現および配列を用いた木の表現を理解できる．
|
| 11週 |
木の再帰的定義
算術式と逆ポーランド記法
木構造に基づくデータ構造
・ヒープ
・２分探索木 |
木構造を再帰的に定義できる。算術式の木を理解できる。数式の逆ポーランド記法を理解できる。
ヒープおよびヒープの配列表現を理解できる。２分木を使った探索法を理解できる。
|
| 12週 |
深さ優先探索
幅優先探索 |
深さ優先探索と幅優先探索が，スタック，キュートと関連が深いことを理解できる。
|
| 13週 |
整列
・バブルソート
・挿入ソート
・シェルソート
・クイックソート
・マージソート |
整列に関する基本的用語を理解できる。代表的な整列アルゴリズムの特徴を説明でき，それぞれの計算量を説明できる。
|
| 14週 |
正規表現
有限オートマトン |
正規表現が表す文字クラスが理解できる。正規表現のパターンマッチを行う有限オートマトンが理解できる。
|
| 15週 |
期末試験 |
|
| 16週 |
|
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 変数とデータ型の概念を説明できる。 | 4 | |
| 代入や演算子の概念を理解し、式を記述できる。 | 2 | |
| 制御構造の概念を理解し、条件分岐や反復処理を記述できる。 | 4 | |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 3 | |
| 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 2 | |
| ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 4 | |
| プログラミング言語は計算モデルによって分類されることを説明できる。 | 2 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 2 | |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | |
| 時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。 | 4 | |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | |
| ソフトウェアを中心としたシステム開発のプロセスを説明できる。 | 2 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | |
| 計算機工学 | 整数・小数を2進数、10進数、16進数で表現できる。 | 3 | |
| 整数・小数をコンピュータのメモリ上でディジタル表現する方法を説明できる。 | 3 | |
| 基数が異なる数の間で相互に変換できる。 | 3 | |