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

＜授業のねらい＞

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

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

特になし

＜具体的な到達目標＞

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

第７回以降の講義、ならびに、試験は、ハイブリッド留学時の現地校にて、
実施する。内容は、基本は変わらないが、プログラミングなどに
重点を置く

＊試験期間中に試験を実施する.

＜成績評価方法＞

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

＜教科書＞

指定教科書なし

＜参考書＞

講義の中で，紹介する．

＜オフィスアワー＞

講義の前後、講義室にて行う．
あるいは，teru@cc.kogakuin.ac.jpに連絡し，日程を調整すること．

ハイブリッド留学時も講義の前後、講義室にて行う．

＜学生へのメッセージ＞

プログラミング１〜４で得た知識をもとに，実践的なアルゴリズムとして理解する．
プログラミング４まで取得していなくても本講義を受講できる．
ただし，プログラミング４までの未取得科目を開講に合わせて必ず履修し，
プログラミング４までの取得を目指すこと