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

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

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

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

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

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

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

＜参考書＞

湯田幸八・伊原充博著「アルゴリズムとデータ構造」（コロナ社、２００２年）
エイホ・ホップクロフト・ウルマン著、大野義夫訳「データ構造とアルゴリズム」（培風館、１９８７)

＜オフィスアワー＞

水曜日３時から６時。必要があればいつでもoyanagi＠cc.kogakuin.ac.jpに連絡してください。

＜学生へのメッセージ＞

プログラミングの演習と連動させる予定です。

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