【 2009 年度 授業概要】

科　　　目			アルゴリズムとデータ構造 ( Algorithms and Data Structures )
担当教員			若林 茂 教授
対象学年等			電気電子工学専攻・1年・後期・選択・2単位
学習・ 教育目標			A3(50%) A4-AE4(50%)
JABEE 基準1(1)			(c),(d)1,(d)2-a,(d)2-d,(g)
授業の概要 と方針			アルゴリズムに関する知識は問題ごとに個別的なものであり，何か統一的な原理があってそれですべてが解決するというものではない．しかし，代表的な優れたアルゴリズムを理解することにより，アルゴリズム設計のかんどころというものが習得できるはずである．この科目では，特定の応用分野に限定されない一般的なアルゴリズムについて，それを実現するためのデータ構造とともに解説する．授業は輪講形式で行う．
到 達 目 標		1	【A3】　 基本的なデータ構造（配列，線形リスト，2分木など）について理解できる．
		2	【A3】　 代表的な探索アルゴリズムについて理解できる．
		3	【A3】　 代表的な整列アルゴリズムについて理解できる．
		4	【A3】　 代表的なグラフアルゴリズムについて理解できる．
		5	【A3】　 代表的な文字列処理アルゴリズムについて理解できる．
		6	【A4-AE4】　 一つ以上のアルゴリズムについてプログラムを作成し，実験的に計算量などの考察ができる．
		7
		8
		9
		10
評 価 方 法 と 基 準	到 達 目 標 毎	1	定期試験，および，輪講（資料と質疑）により評価する．
		2	定期試験，および，輪講（資料と質疑）により評価する．
		3	定期試験，および，輪講（資料と質疑）により評価する．
		4	定期試験，および，輪講（資料と質疑）により評価する．
		5	定期試験，および，輪講（資料と質疑）により評価する．
		6	定期試験，および，課題レポートにより評価する．
		7
		8
		9
		10
	総 合 評 価		成績は，試験70%　輪講（資料と質疑応答）30%　として評価する．100点満点で60点以上を合格とする．なお，試験には課題レポートに関する設問を含む．
テキスト			「アルゴリズムとデータ構造」：石畑清（岩波書店）
参考書			「Pascalプログラミングの基礎」：真野芳久（サイエンス社） 「新訂新C言語入門シニア編」：林晴比古（ソフトバンク）
関連科目			プログラミングI，プログラミングII，ソフトウェア工学
履修上の 注意事項			学園都市単位互換講座の学内提供科目である．手続き型言語でのプログラミング経験のあること．配列，関数，ポインタ等の基礎は理解できていること．

【授業計画（ アルゴリズムとデータ構造 ）】

週	上段：テーマ／下段：内容（目標、準備など）
1	アルゴリズムと計算量
	授業の進め方を説明する．その後，基本的なデータ構造について解説する．また，次週以降の担当学生を決める．
2	探索1
	担当学生が作成した資料をもとに，「線形探索と2分探索」を解説し質疑を行う．
3	探索2
	担当学生が作成した資料をもとに，「2分探索木」を解説し質疑を行う．
4	探索3
	担当学生が作成した資料をもとに，「平衡木とB木」を解説し質疑を行う．
5	探索4
	担当学生が作成した資料をもとに，「ハッシュ法」を解説し質疑を行う．
6	整列1
	担当学生が作成した資料をもとに，「選択法・挿入法・シェルソート」を解説し質疑を行う．
7	整列2
	担当学生が作成した資料をもとに，「クイックソート」を解説し質疑を行う．
8	整列3
	担当学生が作成した資料をもとに，「ヒープソート」を解説し質疑を行う．
9	整列4
	担当学生が作成した資料をもとに，「マージソート」を解説し質疑を行う．
10	グラフのアルゴリズム1
	担当学生が作成した資料をもとに，「グラフの表現と探索」を解説し質疑を行う．
11	グラフのアルゴリズム2
	担当学生が作成した資料をもとに，「各種連結性の判定」を解説し質疑を行う．
12	グラフのアルゴリズム3
	担当学生が作成した資料をもとに，「最短路の問題」を解説し質疑を行う．
13	文字列のアルゴリズム
	担当学生が作成した資料をもとに，「文字列の照合」を解説し質疑を行う．
14	難しい問題
	担当学生が作成した資料をもとに，「バックトラック法・計算量の理論」を解説し質疑を行う．
15	レポート発表とまとめ
	学生がひとりずつレポートの内容をプレゼンテーションする．また，授業のまとめを行う．
備 考	後期定期試験を実施する．