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

科目基礎情報

学校	沖縄工業高等専門学校	開講年度	令和03年度 (2021年度)
授業科目	アルゴリズムとデータ構造
科目番号	3215	科目区分	専門 / 必修
授業形態	授業	単位の種別と単位数	履修単位: 2
開設学科	情報通信システム工学科	対象学年	3
開設期	通年	週時間数	2
教科書/教材	教員自作のプリント、パワーポイントのプレゼン資料。 「Javaプログラマのためのアルゴリズムとデータ構造」（ソフトバンクパブリッシング） 「アルゴリズムとデータ構造」（SoftBank Creative） （他にも参考図書を探す場合のキーワード：アルゴリズム、データ構造）
担当教員	金城 伊智子

到達目標

基本的なデータ構造の概念および整列、探索などの代表的なアルゴリズムとその設計方法を理解する。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
正しく説明できるか定期試験および講義での演習課題で評価する。	授業で学習した内容と関連付けながら基本的なデータ構造の概念および整列、探索などの代表的なアルゴリズムとその設計方法について説明ができる。	教科書や資料に従って基本的なデータ構造の概念および整列、探索などの代表的なアルゴリズムとその設計方法について説明ができる。	教科書や資料を見ながら基本的なデータ構造の概念および整列、探索などの代表的なアルゴリズムとその設計方法について説明ができる。

学科の到達目標項目との関係

学科ごとの教育目標 ２ （コンピュータのハードウェアとソフトウェアの基礎知識を備え、通信を含む社会の様々な問題をシステムとして解決できる基本技術力）

教育目標 本科－１ （技術者に必要な基礎知識を備え、実践力のある人材を育成する）

教育目標 本科－３ （専門的基礎知識を理解し、自ら学ぶことのできる人材を育成する）

教育方法等

概要:

基本的なデータ構造の概念および整列、探索などの代表的なアルゴリズムとその設計方法を理解する。
・　基本的なデータ構造である（配列、リスト、スタック、キューなど）の概念に関して理解する。
・　基本的なデータ構造の実現方法に関して理解を深める。
・　整列、探索などの代表的なアルゴリズムとその設計を理解する。
・　アルゴリズムの性能を比較するオーダー記法の基礎知識を理解する。
【V-D】ソフトウェアの分野では、アルゴリズムとデータ構造に関する基礎的な概念や、ソフトウェアを実際に作成する標準的なプロセスについて理解している。

授業の進め方・方法:

前期・後期評価：小テストの平均の80％＋課題演習20％
学年末評価は前期評価と後期評価の平均で行い、60％以上を合格とする。

注意点:

定期試験の他に、プログラムの演習課題で各自達成度を確認すること。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス、アルゴリズムとデータ構造の概念	1年間の授業の進め方や課題の提出の方法を説明する。アルゴリズムとデータ構造の概念と学習する意義を理解する。
		2週	配列	配列のデータ構造について学習し、プログラミングの演習により理解を深める。
		3週	構造体	構造体のデータ構造について学習し、プログラミングの演習により理解を深める。
		4週	直接探索と計算量	直接探索のアルゴリズムに関して学習し、計算量（オーダー記法）に関する概念を理解する。
		5週	線形探索	探索するアルゴリズムの基本である線形探索の概念について理解する。
		6週	二分探索	効率よく探索するための手法である二分探索の概念について理解する。
		7週	配列、構造体、直接探索、計算量、線形探索、二分探索の演習及び小テスト	配列、構造体、直接探索法、計算量、線形探索、二分探索の演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		8週	スタック、キュー	データ構造のスタックとキューに関する概念を理解する。
	2ndQ
		9週	木	データ構造の木の概念を理解する。
		10週	グラフ、集合	データ構造のグラフと集合の概念を理解する。
		11週	スタック、キュー、木、グラフ、集合の演習及び小テスト	データ構造のスタック、キュー、木、グラフ、集合の演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		12週	リスト	リスト構造に関して概念を理解する。
		13週	双方向連結リスト	双方向連結リスト構造に関して概念を理解する。
		14週	木構造、木の走査	木構造に関して概念と行きがけ順、通りがけ順、帰りがけ順などの走査方法の概念を理解する。
		15週	リスト、双方向リスト、木構造、木の走査の演習及び小テスト	リストと双方向連結リスト、木構造と木の走査に関する演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		16週
後期
	3rdQ
		1週	ニ分木と二分探索	二分木と二分探索方法の概念を理解する。
		2週	二分探索木のノードの挿入と削除、二分木探索の演習	二分探索木におけるノードの挿入方法と削除方法を子を持たない場合などの概念を理解する。
		3週	ハッシュ法	ハッシュテーブルのデータ構造、ハッシュ法の計算量や欠点などの概念を理解する。
		4週	二分木、二分探索、ハッシュ法の演習及び小テスト	二分木、二分探索、ハッシュ法に関する演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		5週	バブルソート	バブルソートの概念に関して理解する。
		6週	選択ソート	選択ソートの概念に関して理解する。
		7週	バブルソート、選択ソートの演習及び小テスト	バブルソート、選択ソートに関する演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		8週	挿入ソート	挿入ソートの概念に関して理解する。
	4thQ
		9週	シェルソート	シェルソートの概念に関して理解する。
		10週	挿入ソート、シェルソートの演習及び小テスト	挿入ソート、シェルソートに関する演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		11週	クイックソート	クイックソートの概念に関して理解する。
		12週	マージソート	マージソートの概念に関して理解する。
		13週	クイックソート、マージソートの演習及び小テスト	クイックソート、マージソートに関する演習問題に取り組むことによって理解を深める。また、小テストにより理解度を確認する。
		14週	ヒープソート	ヒープソートの概念に関して理解する。
		15週	ソートの小テスト	これまで学習してきたソート全般に関する小テストを実施する。
		16週

モデルコアカリキュラムの学習内容と到達目標

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
基礎的能力	工学基礎	情報リテラシー	情報リテラシー	同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを知っている。	3	前1,前2,前3,前4,前5,前6,前7,前9,前10,前11,前12,前13,前14,前15,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				与えられた基本的な問題を解くための適切なアルゴリズムを構築することができる。	3	前3,前5,前6,前9,前11,前13,前14,後1,後2,後4,後5,後6,後7,後9,後11,後12,後13,後14
				任意のプログラミング言語を用いて、構築したアルゴリズムを実装できる。	3	前2,前4,前7,前10,前12,前15,後3,後10,後15
専門的能力	分野別の専門工学	情報系分野	ソフトウェア	アルゴリズムの概念を説明できる。	3	前1,前2,前3,前4,前5,前6,前7,前9,前10,前11,前12,前13,前14,前15,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	3	前3,前4,前5,前6,前7,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	3	前3,前4,前5,前6,前7,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				時間計算量によってアルゴリズムを比較・評価できることを説明できる。	3	前3,前5,前6,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				領域計算量などによってアルゴリズムを比較・評価できることを説明できる。	3	前3,前5,前6,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				整列、探索など、基本的なアルゴリズムについて説明できる。	3	前3,前4,前5,前6,前7,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。	3	前1,前2,前3,前4,前5,前6,前7,前9,前10,前11,前12,前13,前14,前15,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。	3	前1,前2,前3,前4,前5,前6,前7,前9,前10,前11,前12,前13,前14,前15,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。	3	前2,前3,前5,前6,前9,前10,前11,前12,前13,前14,前15,後1,後3
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。	3	前2,前4,前7,前9,前10,前11,前12,前13,前14,前15,後1,後3,後10,後15
				ソフトウェアを中心としたシステム開発のプロセスを説明できる。	3	前1,前4,前7,前10,前12,前15,後10,後15
				ソースプログラムを解析することにより、計算量等のさまざまな観点から評価できる。	3	前3,前4,前5,前6,前7,後9,後10,後11,後12,後13,後14,後15
				同じ問題を解決する複数のプログラムを計算量等の観点から比較できる。	3	前3,前5,前6,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
			情報数学・情報理論	離散数学に関する知識をアルゴリズムの設計、解析に利用することができる。	2	前2,前3,前4,前5,前6,前7,前9,前10,前11,前12,前13,前14,前15,後1,後2,後3,後4,後5,後6,後7
				コンピュータ向けの主要な数値計算アルゴリズムの概要や特徴を説明できる。	2	前3,前5,前6,後1,後2,後3,後4,後5,後6,後7,後9,後10,後11,後12,後13,後14,後15
				情報量の概念・定義を理解し、実際に計算することができる。	3	前3,前5,前6,後6,後7,後9,後10,後11,後12,後13,後14,後15

評価割合

	小テスト	発表	相互評価	態度	ポートフォリオ	その他（課題）	合計
総合評価割合	80	0	0	0	0	20	100
基礎的能力	80	0	0	0	0	20	100
専門的能力	0	0	0	0	0	0	0
分野横断的能力	0	0	0	0	0	0	0