授業目的及び達成目標

授業目標

計算機を用いて問題を効率的に解くために必要となる基本的なアルゴリズムと，さらにその基本となるデータ構造について学ぶ．本講義では単に方法を習得するだけではなく，その理論的裏付けを理解することを重視する．

達成目標

Ａ．アルゴリズムと計算量

1. 問題と問題例の区別，アルゴリズムの計算量をオーダーで表記することができる．
2. データ構造を理解するために必要な程度のグラフ理論の用語が使える．

Ｂ．基本的な基本データ構造

1. リスト/スタック/キューのデータ構造の特徴と実現方法を示すことができる．

Ｃ．集合の取り扱い

1. 辞書のサポートする基本演算が理解でき，ハッシュ表を用いて辞書を実現することができる．
2. 集合族の併合処理をサポートするデータ構造として，配列による実現，ポインタによる実現，木による実現が行える．

Ｄ．順序つき集合の処理

1. 優先度つき待ち行列を連結リストやヒープを使って実現できる．
2. 2分探索木のサポートする基本演算が理解でき，これを実現することができる．
3. 平衡木の原理が理解でき，これを実現することができる．

Ｅ．整列アルゴリズム

1. バブルソート/バケットソート/ヒープソート/クイックソートのアルゴリズムのメカニズムが理解でき，これらの計算時間の評価，適当なデータ構造を用いた実現が行える．
2. 計算の下界値の議論が理解できる．

Ｆ．アルゴリズムの設計手法と実現例：

1. アルゴリズムの代表的な設計手法である，縮小法，分割統治法，動的計画法，貪欲算法，最大最小性の基本原理が理解できている．
2. 上記手法によりアルゴリズムが設計されている第q要素選択，マージソート，SUBSET-SUM問題，最短路問題，最小木問題に対して，実装のために適切なデータ構造を選択することができる．

授業項目

1. アルゴリズムとその計算量（問題と問題例/計算量の評価/オーダー表記）
2. 基本的なデータ構造（リスト，スタック，キュー）
3. グラフと木，木の用語，木のデータ構造，動的木，木の高さの解析
4. 探索のためのデータ構造（順序つき集合）：2分探索，2分探索木，平衡探索木，ハッシング（辞書）
5. 整列（ソーティング）：バケットソート（基数ソート)，ヒープソート，分割統治法(クイックソート，マージソート)，クイックソートの平均計算量，計算量の下界
6. その他，発展的話題：順序統計量，Union-Find問題，最小全域木問題など

成績評価方法と評価基準

達成目標全体の達成度を総合的に評価する定期試験により評価する．
定期試験では，データ構造やアルゴリズムの仕組み（メカニズム）を理解しているかどうかに重点を置く．

S:90点以上

A:80点以上

B:70点以上

C:60点以上

教科書

平田富夫，「アルゴリズムとデータ構造―改訂C言語版」森北出版，2002

参考書

茨木俊秀，「Cによるアルゴリズムとデータ構造」昭晃堂，2000