情報構造論

科目基礎情報

学校 福井工業高等専門学校 開講年度 令和02年度 (2020年度)
授業科目 情報構造論
科目番号 0144 科目区分 専門 / 必修
授業形態 講義 単位の種別と単位数 学修単位: 2
開設学科 電子情報工学科 対象学年 4
開設期 通年 週時間数 2
教科書/教材 「Cデータ構造とプログラム」(オーム社)
担当教員 斉藤 徹

到達目標

動的な記憶域の管理手法について学び、その処理速度やメモリの 使用量などの効率を考慮しながら、最適なデータ構造を設計するための 手法について学び、その効率について解析を行なう。

ルーブリック

理想的な到達レベルの目安標準的な到達レベルの目安未到達レベルの目安
アルゴリズムの理解参考書を見ずに様々なアルゴリズムの利点欠点を説明できる。参考書を見ながら様々なアルゴリズムの利点欠点を説明できる。参考書を見てもアルゴリズムの説明ができない。
計算量の分析参考書を見ずに様々なアルゴリズムの計算量を見積もれる。参考書を見ながら様々なアルゴリズムの計算量を見積もれる。アルゴリズムの計算量の見積もりができない。
基礎的プログラムの作成参考資料を見ながら様々なアルゴリズムの基礎的プログラムが作成できる。様々なアルゴリズムの基礎的プログラムの説明ができる。様々なアルゴリズムの基礎的なプログラムが理解できない。

学科の到達目標項目との関係

学習・教育到達度目標 RB2
JABEE JB2

教育方法等

概要:
動的な記憶域の管理手法について学び、その処理速度やメモリの 使用量などの効率を考慮しながら、最適なデータ構造を設計するための 手法について学び、その効率について解析を行なう。
尚、全体を通して企業等の実務経験者が指導を行う。
授業の進め方と授業内容・方法:
講義を通し、そのデータ構造の手法について解説し、例題のプログラミングを通し理解する。
またそのプログラムを解析することを通して 速度やメモリの利用における効率について検討をする。
理解を深めるために、より実践的な例でのプログラム作成を演習として実施し、時間外学修において理解不足の復習や独自性のある課題テーマへの取り組む。
注意点:
本科目は学修単位科目である。本科目は企業で情報システムの開発・プログラミングを担当していた教員が、その経験を活かし、データ構造の設計手法等について講義を行い、テスト前の時期に演習・課題作成を交えながら授業を行う。
本科(準学士課程)の学習教育目標:RB2(◎)
環境生産システム工学プログラムの学習教育目標:JB2(◎)
関連科目:プログラミング基礎(電子情報2年)、プログラミング応用(電子情報3年)
学習教育目標の達成度評価方法:各4回の中間確認試験または期末試験では、テスト100%もしくはテスト60%+レポート40%の合計点の良い方とする。この方式による4回の評価値を平均する。
各定期試験が実施できない場合は、課題レポート50%,別途実施の小テスト50%にて評価を行う。
学習教育目標の達成度評価基準:最終評価値が60%を越えること。
この科目は、学修単位B(30時間の授業で1単位)の科目である。(ただし、授業外学修の時間を含む。)

授業計画

授業内容・方法 週ごとの到達目標
前期
1週 概要説明、プログラミング応用の復習・構造体とポインタ 構造体やポインタを使ったプログラムについて復習し、基本的なプログラムを理解する。
【授業外学修】C言語の内容を復習しておくこと。
2週 処理時間の見積もり(検索やソート) 検索処理やデータの並び替えのアルゴリズムで、データ量と処理時間の関係を理解する。
【授業外学修】各種の検索やソートの処理時間について理解すること。
3週 オーダ記法と再帰的プログラミングの計算量 データ量と処理時間を表現するためのオーダ記法について理解し、簡単な再帰プログラムについて理解する。
【授業外学修】オーダ記法から処理時間などの見積りができること。
4週 再帰的プログラミングと再帰方程式 再帰的プログラムの計算量を再帰方程式から求める方法を理解する。
【授業外学修】再帰呼び出しのプログラムについて復習しておくこと。
5週 ポインタとメモリ領域と動的メモリ管理 アルゴリズムとメモリ資料量との関係を理解し、動的メモリの必要性を理解する。
【授業外学修】動的メモリについて予習しておくこと。
6週 mallocとfreeの理解 動的メモリを扱うmalloc関数やfree関数の使い方を理解する。
【授業外学修】mallocやfreeを使った演習を行うこと。
7週 動的メモリ管理のプログラミング演習 動的メモリを使った演習およびレポート作成
【授業外学修】mallocやfreeを使った課題のレポート作成
8週 理解度確認テスト
9週 単純リスト構造 配列を使ったプログラムの問題点を理解し、単純リスト構造の考え方を理解する。
【授業外学修】ポインタについて復習しておくこと。
10週 単純リストの処理 単純リストのプログラムとそのデータ処理のプログラムを理解する。
【授業外学修】基礎的なリスト処理プログラムの予習をしておくこと。
11週 リストを用いたスタックと待ち行列 配列やリスト構造を使ったスタックや待ち行列のプログラムや利点欠点を理解する。
【授業外学修】リスト構造を使った演習を行うこと。
12週 リスト構造のプログラミング演習 リスト構造を扱う課題とレポート作成
【授業外学修】リスト構造を使った課題のレポート作成
13週 双方向リスト 双方向リストの考え方とそのプログラムを理解する。
【授業外学修】双方向リストへのデータ挿入などを復習しておくこと。
14週 データの型を通して、ポインタなどの復習 ポインタなどを使ったプログラムをデータの型を使って理解する。
【授業外学修】ポインタを使ったプログラムの理解度を確認しておくこと。
15週 前期期末試験
16週 学習のまとめ テスト問題の解説を通して前期内容を総括
後期
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週 理解度確認テスト
9週 ハッシュ法 データ探索とハッシュ法・ハッシュ関数の考え方を理解する。
【授業外学修】ハッシュ法について復習しておくこと。
10週 ハッシュ法と衝突処理 オープンアドレス法やチェイン法について理解し、その課題とレポート作成
【授業外学修】2つの手法について違いを理解しておくこと。
11週 動的メモリの管理法(参照カウンタ法) データ構造の共有がある場合の問題点を理解し、その解決法の参照カウンタ法を理解する。
【授業外学修】リストを用いた集合計算などのプログラムについて復習しておくこと。
12週 動的メモリの管理法(ガベージコレクタ法) 参照カウンタ法以外の、ガベージコレクタ法の仕組みを理解する。
【授業外学修】参照カウンタ法などの問題点を理解しておくこと。
13週 ヒープ領域の管理法 ヒープ領域がどのように管理されているのか手法を理解する。
【授業外学修】mallocやfreeなどの機能について理解しておくこと。
14週 実例を通した情報構造の設計 データ構造の設計によりデータ件数と処理時間・メモリ使用量との関係を理解する。
【授業外学修】今までのデータ構造について全体的に復習しておくこと。
15週 最近のプログラム言語でのアルゴリズム記述方法 応用事例の理解として、オブジェクト指向を用いたプログラムの事例を理解する。
【授業外学修】オブジェクト指向の用語や利点などを理解しておくこと。
16週 まとめ テスト問題の解説と全体の総括

評価割合

試験レポート課題合計
総合評価割合6040100
アルゴリズム理解302050
計算量理解12820
プログラム作成181230