【授業の目的】
各種のデータ構造とそれらに関連する基本的なアルゴリズムについて学習する．
【授業の到達目標】
(a)各種のデータ構造（線形構造、木構造、グラフ構造）を理解する
(b)基本的な探索法（縦型探索法、横型探索法）を理解する
(c)文字列照合の代表的なアルゴリズム（ＫＭＰ法）を理解する
(d)グラフの最短路問題の代表的なアルゴリズム（ダイクストラ法）を理解する
(e)解探索の代表的なアルゴリズム（Ａアルゴリズム）を理解する
(f)データ整列の代表的なアルゴリズム（ヒープソート法，クイックソート法）を理解する
(g)データ探索の代表的なアルゴリズム（ハッシュ法、ニ分探索木法）を理解する
【授業概要（キーワード）】
データ構造とアルゴリズムは，プログラムを作る上で必ず学ばなければならない基礎の一つであり，少しでも本格的な良いプログラムを作ろうと思えば，データ構造とアルゴリズムに関する知識が欠かせない．このようなプログラミングの基礎となる，基本的な種々のデータ構造とそれらに関連する基本的なアルゴリズムを解説する．
（線形構造，木構造，グラフ構造，スタックと待ち行列，文字列照合，グラフの最短路問題，解の探索，データ整列，データ探索）
【科目の位置付け】
本授業の基礎となる科目：計算機基礎
本授業と関連が深い科目：プログラミング言語，データベース論，プログラミング演習Ⅰ～Ⅲ
【授業計画】
・授業の方法
講義形式で行う．毎回15分～20分間でその時間内に学んだ内容の演習問題を解いてもらう．
・日程
第１回 ガイダンス，データ構造とアルゴリズムの基礎
第２回 線形構造
第３回 スタックと待ち行列，基本的な探索法
第４回 文字列照合（単純照合法、KMP法）
第５回 文字列照合（KMP法）
第６回 木構造
第７回 グラフ構造
第８回 中間試験と解説
第９回 グラフの最短路問題（ダイクストラ法など）
第１０回 解の探索（Aアルゴリズムなど）
第１１回データ整列（ヒープソート法など）
第１２回 データ整列（クイックソート法など）
第１３回 データ探索（ハッシュ法など）
第１４回 データ探索（ニ分探索木法など）
第１５回 期末試験と解説
【学習の方法】
・受講のあり方
欠席や遅刻をすると授業内容が分からなくなるので必ず遅刻せずに出席すること．
私語など他の受講生の迷惑となる行為は行わないこと．受け身にならず積極的な受講を期待する．
・授業時間外学習へのアドバイス
予習として，講義資料をホームページで公開するので，事前に読んでくるとともに疑問点をノートに書きだしてくる．
復習として，演習問題をもう一度解いてみるとともに講義で出てきたアルゴリズムを実際にC言語を用いてプログラミングするのが望ましい．
【成績の評価】
・基準
総合点で６０点以上を合格とする．
・方法
中間試験（５０点），期末試験（５０点）の配点で評価する．
【テキスト・参考書】
テキストとして，自作の講義資料を用いる．
参考書
1. データ構造とアルゴリズム、斎藤信男・西原清一 著、コロナ社、2800円(1998）
2. Cで学ぶデータ構造とアルゴリズム、西原清一 著、オーム社、2600円(2008)
3. アルゴリズムとデータ構造、原 隆浩 他著、共立出版、2400円(2012)
|