データ構造とアルゴリズム

科目基礎情報

学校	鈴鹿工業高等専門学校	開講年度	平成29年度 (2017年度)
授業科目	データ構造とアルゴリズム
科目番号	0035	科目区分	専門 / 必修
授業形態	授業	単位の種別と単位数	履修単位: 2
開設学科	電子情報工学科	対象学年	3
開設期	通年	週時間数	2
教科書/教材	教科書：「プログラミングの宝箱　アルゴリズムとデータ構造　第2版」紀平拓男・春日伸弥著（ソフトバンク）参考書：「アルゴリズムとデータ構造」湯田ほか著（コロナ社），「データ構造とアルゴリズム」斎藤ほか著（コロナ社）　など
担当教員	田添 丈博

到達目標

基本的なデータ構造とアルゴリズムを理解し，プログラミングにおいて利用することができる．

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	基本的なアルゴリズムについて実装できる．	基本的なアルゴリズムについて説明できる．	基本的なアルゴリズムについて説明できない．
評価項目2	基本的なデータ構造について実装できる．	基本的なデータ構造について説明できる．	基本的なデータ構造について説明できない．
評価項目3	プログラムを計算量の観点から比較・評価できる．	プログラムを計算量の観点で解析できる．	プログラムを計算量の観点で解析できない．

教育方法等

概要:

これまでに開発されている，問題解決のための各種のアルゴリズムと，関連するデータ構造について理解すること．そして，プログラミング上の応用問題において，それらを活用できる能力を養うこと．理論だけでなくコーディングも重視していく．

授業の進め方・方法:

・各週の内容は，電子情報工学科学習・教育到達目標(B)＜専門＞の項目に相当する．
・授業は講義・輪講形式で行う．講義中は集中して聴講する．
・「授業計画」における各週の「到達目標」はこの授業で習得する「知識・能力」に相当するものとする．

注意点:

＜到達目標の評価方法と基準＞下記授業計画の「到達目標」を網羅した問題を2回の中間試験，2回の定期試験で出題し，目標の達成度を評価する．各到達目標に関する重みは同じである．合計点の60％の得点で，目標の達成を確認できるレベルの試験を課す．
＜学業成績の評価方法および評価基準＞前期中間・前期末・後期中間・学年末の4回の試験の平均点による評価を80％，プログラミング課題等に対するレポートの評価を20％として学業成績を評価する．再試験は実施しない．
＜単位修得要件＞学業成績で60点以上を取得すること．
＜あらかじめ要求される基礎知識の範囲＞本教科はプログラミング基礎，マイクロコンピュータ基礎，プログラム設計，オペレーティングシステムの学習が基礎となる教科である．また，数学の基本事項について理解していることも必要である．
＜レポート等＞授業中に演習（C++プログラミング）を適宜行う．また，プログラミング課題に対するレポート提出を求める．さらに，それ以外に，計算問題等に対するレポート提出を求めることがある．
＜備考＞データ構造とアルゴリズムに関する理解は，情報工学分野における最も重要な基盤の一つである．具体例で確認・理解すると同時に，数学的な表現を理解できることも必要である．論理的・数学的な思考力を，さらに培っていくことが大切である．本教科は後に学習するソフトウェア工学，人工知能，数値解析の基礎となる教科である．

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	アルゴリズムとは	1. アルゴリズムの評価 ・アルゴリズムと計算量
		2週	ソート	4. 整列アルゴリズム ・バブルソート，クイックソート ・マージソート
		3週	サーチ	3. 探索アルゴリズム ・線形探索 ・2分探索
		4週	データ構造とは	2. 基本的なデータ構造 ・配列，構造体，ポインタ
		5週	リスト	2. 基本的なデータ構造 ・連結リスト，木
		6週	スタック	2. 基本的なデータ構造 ・スタック
		7週	キュー	2. 基本的なデータ構造 ・キュー（待ち行列）
		8週	中間試験	これまでに学習した内容を説明し，諸量を求めることができる．
	2ndQ
		9週	再帰	6. アルゴリズムの設計 ・再帰
		10週	最大公約数を求める	6. アルゴリズムの設計 ・再帰
		11週	木構造	2. 基本的なデータ構造 ・連結リスト，木
		12週	2分木	3. 探索アルゴリズム ・2分探索木
		13週	多分木	3. 探索アルゴリズム ・平衡木，AVL木 ・多分木，B木
		14週	マップ	3. 探索アルゴリズム ・ハッシュ法
		15週	ハッシュ	3. 探索アルゴリズム ・ハッシュ法
		16週
後期
	3rdQ
		1週	誤差	6. アルゴリズムの設計 ・近似解法（数値計算）
		2週	数値計算	6. アルゴリズムの設計 ・近似解法（数値計算）
		3週	文字列検索	3. 探索アルゴリズム ・文字列の探索
		4週	KMP法	3. 探索アルゴリズム ・文字列の探索
		5週	BM法	3. 探索アルゴリズム ・文字列の探索
		6週	深さ優先探索	5. グラフとアルゴリズム ・グラフ上の探索（深さ優先，幅優先）
		7週	幅優先探索	5. グラフとアルゴリズム ・グラフ上の探索（深さ優先，幅優先）
		8週	中間試験	これまでに学習した内容を説明し，諸量を求めることができる．
	4thQ
		9週	動的計画法	6. アルゴリズムの設計 ・分割統治法 ・動的計画法
		10週	ナップザック問題	6. アルゴリズムの設計 ・分割統治法 ・動的計画法
		11週	最短経路問題	6. アルゴリズムの設計 ・分割統治法 ・動的計画法
		12週	逆ポーランド記法	3. 探索アルゴリズム ・2分探索木
		13週	グラフ構造	5. グラフとアルゴリズム ・グラフとその表現
		14週	重み付きグラフ	5. グラフとアルゴリズム ・グラフとその表現
		15週	ダイクストラ法	5. グラフとアルゴリズム ・グラフに関する応用（ダイクストラ，フロイド）
		16週

評価割合

	試験	課題	相互評価	態度	発表	その他	合計
総合評価割合	80	20	0	0	0	0	100
配点	80	20	0	0	0	0	100