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

＜授業のねらい＞

計算機科学の基本の一つであるアルゴリズムを考える上で、必要となる原理や概念を習得し、アルゴリズムの分析や設計を行い、プログラミングに反映させる能力を身につけることを目指す。

＜受講にあたっての前提条件＞

データ構造の実装などにおいて、「プログラミング演習」等のプログラミング基礎科目合格程度の基本的な知識や経験が必要となるので、それらを有していることを前提とする（配列や関数などの理解が不足している場合は、まずはプログラミング関連科目の履修を勧める）。

＜具体的な到達目標＞

●時間計算量の考え方を理解し、実際の問題解決の場で計算量の観点から考察できる。
●基礎的なデータ構造である配列、リスト、キュー、木構造などを理解できる。
●基礎的なデータ構造をソーティングアルゴリズムやグラフアルゴリズムとして活用できる。
●プログラミング言語を用いて具現化できる。

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

1. アルゴリズムとデータ構造の基礎
　計算量の評価やO表記法について解説する。
準備学習：教科書Part2 「基礎編]2章までを読み、身近な問題解決のアルゴリズムと時間計算量について考察をしておくこと。
2.整列(1)
　データの並び替えを行うための基礎知識について解説する。また、挿入ソートを例に、配列を使った整列方法について説明する。
　準備学習：教科書Part2 「基礎編]3章初等的整列の3.1から3.2までを読むとともに、配列について使い方などの復習をしておくこと。
3.整列(2)
　バブルソートを例に、配列の操作の復習と、効率化について解説する。
　準備学習：教科書Part2 「基礎編]3章初等的整列の3.3を読むとともに、ソーティングアルゴリズムの種類とその特徴を調べておくこと。
4.整列(3)
　配列を用いた様々なソーティングアルゴリズムを紹介する。
　準備学習：教科書Part2 「基礎編]3章初等的整列の3.4から3.5を読み、それぞれのソーティングアルゴリズムの特徴を調べておくこと。
5.スタック
　LIFO(Last In First Out)などのスタックの特徴について解説する。
　準備学習：教科書Part2 「基礎編]4章データ構造とはの4.1から4.2を読み、スタックについて調べておくこと。
6.キュー
　FIFO(First In First Out)などのキューの特徴について解説する。
　準備学習：教科書Part2 「基礎編]4章データ構造とはの4.3を読み、配列によるキューの問題点や解決方法について調べておくこと。
7.学習成果の確認（中間試験）
　準備学習：前回までの総復習を行う。
8.リスト(1)
　リスト構造の説明と、配列による実現方法について解説する。
　準備学習：二次元配列の操作方法について、プログラミング演習などの復習をしておくこと。
9.リスト(2)
　構造体を用いたデータの扱い方について解説する。
　準備学習：structやtypedefについて、プログラミング演習などの復習をしておくこと。
10.リスト(3)
　ポインタを用いたリスト構造の実現方法について解説する。
　準備学習：教科書Part2 「基礎編]4章データ構造とはの4.4を読み、ポインタの使い方やmalloc関数の使い方などを復習しておくこと。
11.探索(1)
　データの集合から目的のデータを探す処理を実現する方法について解説する。
　準備学習：教科書Part2 「基礎編]5章探索の5.1から5.3を読み、探索方法について調べておくこと。
12.探索(2)
　木構造について解説する。
　準備学習：教科書Part2 「基礎編]8章木構造の8.1から5.3を読み、木構造に関する用語や実装方法等について調べておくこと。
13.探索(3)
　二分探索木を用いた探索について解説する。
　準備学習：教科書Part2 「基礎編]9章二分探索木を読み、二分探索木の特徴や要素の追加・削除の方法等について調べておくこと。
14.グラフ
　グラフを用いたモデル化の方法と、グラフの実装方法について解説する。
　準備学習：教科書Part2 「基礎編]12章グラフを読み、グラフと木構造の違いやグラフを用いたアルゴリズムについて調べておくこと。
15.学習成果の確認（期末試験）
　準備学習：リスト(1)から前回までの総復習を行う。

＜成績評価方法＞

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

＜教科書＞

「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」渡部 有隆（著）（マイナビ）

＜参考書＞

「プログラミングの宝箱 アルゴリズムとデータ構造 第2版」紀平 拓男 (著), 春日 伸弥 (著) (ソフトバンククリエイティブ）
「アルゴリズムの設計と解析 I」 A.V.エイホ (著), 野崎 昭弘（訳）（サイエンス社）
「珠玉のプログラミング―本質を見抜いたアルゴリズムとデータ構造」 Jon Bentley（著）小林 健一郎（訳）（ピアソンエデュケーション）

＜オフィスアワー＞

ありません。授業時間以外での質問などは、第1回の授業で配付するガイダンス資料に書かれたメールアドレスに送信してください。