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

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

プログラムを作るときに必要になるのは，取り扱うデータに構造を与えること，および，それを取り扱う手順，すなわちアルゴリズムです．本講義では，問題をどう解くかという観点から，いわばトップ・ダウンにソフトウェアを眺めていきます．

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

１．アルゴリズムとは何か：定義，表現(文章，擬似コード，フローチャート，プログラム)，時間計算量と領域計算量
２．アルゴリズムと計算量：漸近評価，最大計算量と平均計算量，基本的なアルゴリズム
３．ソーティング:順序関係，ソートとは，内部ソートと外部ソート，安定性，計算量の下限，選択ソート，バブルソート
４．ソーティング：クイックソート，マージソート，挿入ソート
５．最大公約数，最小公倍数，ユークリッドの互除法
６．探索：線形探索，二分探索，文字列の探索
７．基本的なデータ構造:基本データ構造，問題向きデータ構造，論理構造とその表現，リスト，リストの作成
８．基本的なデータ構造：リストの操作，双方向リスト
９．基本的なデータ構造：スタック，キュー
１０．基本的なデータ構造：木，木の用語，木の走査，２分木
１１．基本的なデータ構造：２分木の表現，一般の木の表現，木への操作，ヒープソート
１２．基本的なデータ構造：ハッシュ，ハッシュ値，ハッシュの利用，改ざん検出
１３．基本的なデータ構造：グラフ，グラフの用語，部分グラフ
１４．基本的なデータ構造：グラフの表現，隣接行列，接続行列，グラフの探索，最短路問題
１５．学習成果の評価(学期末試験)
余裕があれば，ハノイの塔，８クイーン問題，ナップザック問題などについても触れる．

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

原則として定期試験で評価し，60点以上のものに単位を認める．ただし，欠席が少なく試験の点数がわずかに60点に足りない場合はレポート提出を認め，レポート内容が単位認定相当と判断される場合には最終成績を60点とする．

＜オフィスアワー＞

水曜日15時から18時．必要があればいつでもteru＠cc.kogakuin.ac.jpに連絡してください．

＜学生へのメッセージ＞

講義内で，簡単なプログラミングの演習を行う予定です．

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