動的な記憶域の管理手法について学び、その処理速度やメモリの 使用量などの効率を考慮しながら、最適なデータ構造を設計するための 手法について学び、その効率について解析を行なう。
概要:
動的な記憶域の管理手法について学び、その処理速度やメモリの 使用量などの効率を考慮しながら、最適なデータ構造を設計するための 手法について学び、その効率について解析を行なう。
尚、全体を通して企業等の実務経験者が指導を行う。
授業の進め方・方法:
講義を通し、そのデータ構造の手法について解説し、例題のプログラミングを通し理解する。
またそのプログラムを解析することを通して 速度やメモリの利用における効率について検討をする。
理解を深めるために、より実践的な例でのプログラム作成を演習として実施し、時間外学修において理解不足の復習や独自性のある課題テーマへの取り組む。
注意点:
本科目は学修単位科目である。本科目は企業で情報システムの開発・プログラミングを担当していた教員が、その経験を活かし、データ構造の設計手法等について講義を行い、テスト前の時期に演習・課題作成を交えながら授業を行う。
本科(準学士課程)の学習教育目標：RB2(◎)
環境生産システム工学プログラムの学習教育目標：JB2(◎)
関連科目：プログラミング基礎(電子情報2年)、プログラミング応用(電子情報3年)
学習教育目標の達成度評価方法：各4回の中間確認試験または期末試験では、テスト100%もしくはテスト60%+レポート40%の合計点の良い方とする。この方式による4回の評価値を平均する。
各定期試験が実施できない場合は、課題レポート50%,別途実施の小テスト50%にて評価を行う。
学習教育目標の達成度評価基準：最終評価値が60%を越えること。
この科目は、学修単位B（３０時間の授業で１単位）の科目である。(ただし、授業外学修の時間を含む。)
|
|
週 |
授業内容 |
週ごとの到達目標 |
| 前期 |
| 1stQ |
| 1週 |
概要説明、プログラミング応用の復習・構造体とポインタ |
構造体やポインタを使ったプログラムについて復習し、基本的なプログラムを理解する。
【授業外学修】C言語の内容を復習しておくこと。
|
| 2週 |
処理時間の見積もり(検索やソート) |
検索処理やデータの並び替えのアルゴリズムで、データ量と処理時間の関係を理解する。
【授業外学修】各種の検索やソートの処理時間について理解すること。
|
| 3週 |
オーダ記法と再帰的プログラミングの計算量 |
データ量と処理時間を表現するためのオーダ記法について理解し、簡単な再帰プログラムについて理解する。
【授業外学修】オーダ記法から処理時間などの見積りができること。
|
| 4週 |
再帰的プログラミングと再帰方程式 |
再帰的プログラムの計算量を再帰方程式から求める方法を理解する。
【授業外学修】再帰呼び出しのプログラムについて復習しておくこと。
|
| 5週 |
ポインタとメモリ領域と動的メモリ管理 |
アルゴリズムとメモリ資料量との関係を理解し、動的メモリの必要性を理解する。
【授業外学修】動的メモリについて予習しておくこと。
|
| 6週 |
mallocとfreeの理解 |
動的メモリを扱うmalloc関数やfree関数の使い方を理解する。
【授業外学修】mallocやfreeを使った演習を行うこと。
|
| 7週 |
動的メモリ管理のプログラミング演習 |
動的メモリを使った演習およびレポート作成
【授業外学修】mallocやfreeを使った課題のレポート作成
|
| 8週 |
理解度確認テスト |
|
| 2ndQ |
| 9週 |
単純リスト構造 |
配列を使ったプログラムの問題点を理解し、単純リスト構造の考え方を理解する。
【授業外学修】ポインタについて復習しておくこと。
|
| 10週 |
単純リストの処理 |
単純リストのプログラムとそのデータ処理のプログラムを理解する。
【授業外学修】基礎的なリスト処理プログラムの予習をしておくこと。
|
| 11週 |
リストを用いたスタックと待ち行列 |
配列やリスト構造を使ったスタックや待ち行列のプログラムや利点欠点を理解する。
【授業外学修】リスト構造を使った演習を行うこと。
|
| 12週 |
リスト構造のプログラミング演習 |
リスト構造を扱う課題とレポート作成
【授業外学修】リスト構造を使った課題のレポート作成
|
| 13週 |
双方向リスト |
双方向リストの考え方とそのプログラムを理解する。
【授業外学修】双方向リストへのデータ挿入などを復習しておくこと。
|
| 14週 |
データの型を通して、ポインタなどの復習 |
ポインタなどを使ったプログラムをデータの型を使って理解する。
【授業外学修】ポインタを使ったプログラムの理解度を確認しておくこと。
|
| 15週 |
前期期末試験 |
|
| 16週 |
学習のまとめ |
テスト問題の解説を通して前期内容を総括
|
| 後期 |
| 3rdQ |
| 1週 |
2分探索法と2分探索木 |
2分探索法を通して2分木の特徴を理解する。
【授業外学修】2分探索法などのプログラムを理解しておくこと。
|
| 2週 |
2分探索木のプログラムの基本 |
2分探索木の基本的な処理プログラムを通して再帰や深さ優先探索処理を理解する。
【授業外学修】再帰呼び出しについて復習をしておくこと。
|
| 3週 |
2分探索木の生成と木の最適化 |
生成された木の問題点を考察し、木構造の最適化について理解する。
【授業外学修】2分木のプログラムを理解し問題点を考えておくこと。
|
| 4週 |
2分探索木の課題 |
2分探索木の課題とレポート作成
【授業外学修】2分探索木を使った演習を行うこと。
|
| 5週 |
2分木と構文木 |
2分木を構文解析処理に使うための考え方を理解する。
【授業外学修】演算子などの評価順序などを予習しておくこと。
|
| 6週 |
構文木と字句解析と構文解析 |
構文木を通して、コンパイラにおける字句解析と構文解析などについて理解する。
【授業外学修】式の処理のプログラムについて演習をしておくこと。
|
| 7週 |
B木 |
辞書とB木構造について理解する。
【授業外学修】B木の構造について予習しておくこと。
|
| 8週 |
理解度確認テスト |
|
| 4thQ |
| 9週 |
ハッシュ法 |
データ探索とハッシュ法・ハッシュ関数の考え方を理解する。
【授業外学修】ハッシュ法について復習しておくこと。
|
| 10週 |
ハッシュ法と衝突処理 |
オープンアドレス法やチェイン法について理解し、その課題とレポート作成
【授業外学修】２つの手法について違いを理解しておくこと。
|
| 11週 |
動的メモリの管理法(参照カウンタ法) |
データ構造の共有がある場合の問題点を理解し、その解決法の参照カウンタ法を理解する。
【授業外学修】リストを用いた集合計算などのプログラムについて復習しておくこと。
|
| 12週 |
動的メモリの管理法(ガベージコレクタ法) |
参照カウンタ法以外の、ガベージコレクタ法の仕組みを理解する。
【授業外学修】参照カウンタ法などの問題点を理解しておくこと。
|
| 13週 |
ヒープ領域の管理法 |
ヒープ領域がどのように管理されているのか手法を理解する。
【授業外学修】mallocやfreeなどの機能について理解しておくこと。
|
| 14週 |
実例を通した情報構造の設計 |
データ構造の設計によりデータ件数と処理時間・メモリ使用量との関係を理解する。
【授業外学修】今までのデータ構造について全体的に復習しておくこと。
|
| 15週 |
最近のプログラム言語でのアルゴリズム記述方法 |
応用事例の理解として、オブジェクト指向を用いたプログラムの事例を理解する。
【授業外学修】オブジェクト指向の用語や利点などを理解しておくこと。
|
| 16週 |
まとめ |
テスト問題の解説と全体の総括
|
| 分類 | 分野 | 学習内容 | 学習内容の到達目標 | 到達レベル | 授業週 |
| 専門的能力 | 分野別の専門工学 | 情報系分野 | プログラミング | 変数の概念を説明できる。 | 4 | |
| データ型の概念を説明できる。 | 4 | 前1 |
| 代入や演算子の概念を理解し、式を記述できる。 | 4 | |
| 制御構造の概念を理解し、条件分岐を記述できる。 | 4 | |
| 制御構造の概念を理解し、反復処理を記述できる。 | 4 | |
| プロシージャ(または、関数、サブルーチンなど)の概念を理解し、これらを含むプログラムを記述できる。 | 4 | |
| 与えられた問題に対して、それを解決するためのソースプログラムを記述できる。 | 4 | |
| 与えられたソースプログラムを解析し、プログラムの動作を予測することができる。 | 4 | |
| ソフトウェア生成に必要なツールを使い、ソースプログラムをロードモジュールに変換して実行できる。 | 4 | |
| 主要な言語処理プロセッサの種類と特徴を説明できる。 | 4 | |
| ソフトウェア開発に利用する標準的なツールの種類と機能を説明できる。 | 4 | |
| プログラミング言語は計算モデルによって分類されることを説明できる。 | 4 | |
| 主要な計算モデルを説明できる。 | 4 | |
| 要求仕様に従って、いずれかの手法により動作するプログラムを設計することができる。 | 4 | |
| 要求仕様に従って、いずれかの手法により動作するプログラムを実装することができる。 | 4 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを設計できる。 | 4 | |
| 要求仕様に従って、標準的な手法により実行効率を考慮したプログラムを実装できる。 | 4 | |
| ソフトウェア | アルゴリズムの概念を説明できる。 | 4 | 前2 |
| 与えられたアルゴリズムが問題を解決していく過程を説明できる。 | 4 | |
| 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。 | 4 | 前2,前3 |
| 時間計算量によってアルゴリズムを比較・評価できることを説明できる。 | 4 | 前2,前3,前4 |
| 領域計算量などによってアルゴリズムを比較・評価できることを説明できる。 | 4 | 前2,前3,前4 |
| 整列、探索など、基本的なアルゴリズムについて説明できる。 | 4 | 前2,前3 |
| コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。 | 4 | 前3,前4 |
| 同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。 | 4 | 前3,前4 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。 | 4 | 前9,前10,前11,前12,前13,後1 |
| リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。 | 4 | 前9,前10,前11,前12,前13,後1 |
| ソフトウェアを中心としたシステム開発のプロセスを説明できる。 | 2 | |
| ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。 | 4 | 前3,前4 |
| 同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。 | 4 | 前3,前4 |
| その他の学習内容 | データモデル、データベース設計法に関する基本的な概念を説明できる。 | 2 | 後7,後9 |