データ構造論（Data Structures）[4752]

＜授業のねらい及び具体的な達成目標＞

計算機科学の基本の１つであるアルゴリズムを考える上で、必要となる原理や概念を習得し、アルゴリズムの分析や設計を行い、プログラミングに反映させる能力の育成を目指す。
具体的には、基礎的なデータ構造であるリスト、キュー、木構造などの理解し、ソーティングアルゴリズムやグラフアルゴリズムとして活用し、プログラミング言語を用いて具現化できることを達成目標とする。
データ構造の実装などにおいて、「プログラミング演習」等プログラミングの基礎科目合格程度の基本的な知識や経験が必要となるので、それらを有していることを前提とする（配列や関数などの理解が不足している場合は、まずはプログラミングの学習を行う事を勧める）。

＜授業計画及び準備学習＞

1. アルゴリズムとデータ構造の基礎
準備学習：電車の乗り換え案内などの身近な問題解決のアルゴリズムと時間計算量について考察をしておくこと。
2.ソート(1)
　準備学習：配列について使い方などの復習をしておくこと。
3.ソート(2)
　準備学習：１章を読み、ソーティングアルゴリズムの種類とその特徴を調べておくこと。
4.サーチ
　準備学習：２章を読み、サーチの種類とその特徴を調べておくこと。
5.リスト
　準備学習：３章を読み、リスト構造の特徴を調べておくこと。
6.スタック
　準備学習：４章を読み、スタックの特徴を調べておくこと。
7.キュー
　準備学習：４章を読み、キューの特徴を調べておくこと。
8.再帰
　準備学習：５章を読み、再帰予備出しについて調べておくこと。また、関数の書き方など、プログラミングの復習をしておくこと。
9.ツリー構造
　準備学習：６章を読み、ツリー構造の種類や特徴を調べておくこと。
10.マップとハッシュ
　準備学習：７章を読み、探索やハッシュについての理解を深めておくこと。
11.文字列検索
　準備学習：９章を読み、文字列探索の方法やそれを実現するためのデータ構造について検討をしておくこと。
12.バックトラック法と幅優先探索
　準備学習：１０章を読み、幅優先探索と深さ優先探索について調べておくこと。
13.動的計画法
　準備学習：前回の復習をすると共に、１１章を読み分割統治法について調べておくこと。
14.グラフ構造(1)
　準備学習：１３章を読み、有向グラフ、無向グラフ、重み付きグラフについて調べておくこと。
15.グラフ構造(2)
　準備学習：前回の復習をすると共に、グラフを用いたアルゴリズムにどんなものがあるか調べておくこと。

＜成績評価方法及び水準＞

原則として、中間試験１回と定期試験１回の合計２回の試験の平均点が６０点以上を合格とする。ただし平均点が６０点に満たないものでも、どちらかの試験が６０点以上でかつ演習および宿題の内容が十分であると認められる場合には合格とすることもある。なお、5回以上欠席した学生は履修放棄とみなし成績評価を行わない。

＜教科書＞

「プログラミングの宝箱 アルゴリズムとデータ構造 第2版」紀平 拓男 (著), 春日 伸弥 (著) (ソフトバンククリエイティブ）

＜参考書＞

「アルゴリズムの設計と解析 I」 A.V.エイホ (著), 野崎 昭弘（訳）（サイエンス社）
「珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造」 Jon Bentley（著）小林 健一郎（訳）（ピアソンエデュケーション）
「The Art of Computer Programming Volume1 Fundamental Algorithms Third Edition」 Donald E. Knuth（著）有澤 誠 , 和田 英一(監訳), 青木 孝, 筧 一彦, 鈴木 健一, 長尾 高弘(訳)　（アスキー）

＜オフィスアワー＞

ありません

このページの著作権は学校法人工学院大学が有しています。 Copyright(c)2013 Kogakuin University. All Rights Reserved.