○データ構造とアルゴリズム（Data Structure and Algorithm）[5G18]

＜学位授与の方針＞

○	1. 基礎知識の習得
◎	2. 専門分野知識の習得
	3. 汎用的問題解決技能
○	4. 道徳的態度と社会性
○	5. 創成能力

＜授業のねらい＞

プログラムを作るときに必要になるのは，取り扱うデータに構造を与えること，および，それを取り扱う手順，すなわちアルゴリズムです．つまり，
　　　プログラム＝データ構造＋アルゴリズム
が成り立ちます．本講義では，基本的なデータ構造とアルゴリズムを理解することにより，プログラミング能力向上の一助とします．

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

前期のプログラミング言語および演習，後期のＣプログラミングおよび演習とともに，連携しながら講義を進める．

＜具体的な到達目標＞

基本的なデータ構造とアルゴリズムを理解する．
理解したアルゴリズムを，学修したデータ構造を用いて，プログラムを作成できる．

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

１．アルゴリズムとは何か：アルゴリズムの表現，時間計算量と領域計算量
　準備学習：アルゴリズムとは何かを調べておくこと

２．アルゴリズムと計算量：漸近評価，最大計算量と平均計算量，基本的なアルゴリズム
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

３．基本的なデータ構造:基本データ構造，問題向きデータ構造，論理構造とその表現，リスト，リストの作成
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

４．基本的なデータ構造：リストの操作，双方向リスト
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

５．基本的なデータ構造：スタック，キュー
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

６．基本的なデータ構造：木，木の用語，木の走査，２分木，２分木の表現，一般の木の表現，木への操作，ヒープソート
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

７．基本的なデータ構造：グラフ，用語，部分グラフ，グラフの表現，グラフの探索，最短路問題
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

８．ソーティング:順序関係，ソートとは，内部ソートと外部ソート，安定性，選択ソート，バブルソート
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

９．ソーティング：クイックソート，マージソート，挿入ソート
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

１０．最大公約数，最小公倍数，ユークリッドの互除法
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

１１．探索：線形探索，二分探索，文字列の探索
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

１２．ハノイの塔，８クイーン問題，ナップザック問題など
　準備学習：前回配布した今回の授業内容に関する資料を読んでおくこと．

１３．総復習
　今までの総復習として，特に理解の浅い点を解説する．
　準備学習：前回の復習をして出された問題を解くこと．また，今までの授業内容を
振り返り，理解が不十分な点をまとめておくこと

１４．学習内容の振り返り
　　準備学習：期末試験で解けなかった問題の解き方を考えておく

＜成績評価方法＞

試験およびレポート課題によって到達目標に照らして，
6段階のGrade(A+,A,B,C,D,F)で評価し，D以上の者に単位を認める．

＜教科書＞

指定教科書なし

＜参考書＞

講義の中で，紹介する．

＜オフィスアワー＞

月曜３限，田中輝雄居室（A2477)で行う．
あるいは，teru@cc.kogakuin.ac.jpに連絡し，日程を調整すること．

＜学生へのメッセージ＞

今回は再履修クラスです．
通常クラスより，実践的なプログラミングを増やす予定です．