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

科目基礎情報

学校	米子工業高等専門学校	開講年度	令和06年度 (2024年度)
授業科目	アルゴリズムとデータ構造
科目番号	0089	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	履修単位: 2
開設学科	総合工学科（情報システムコース）	対象学年	4
開設期	通年	週時間数	2
教科書/教材	情報系のための離散数学、猪股俊光他、共立出版 例題と演習でわかる離散数学、加納幹雄、森北出版 情報工学レクチャーシリーズ　アルゴリズムとデータ構造、藤原 暁宏、森北出版 新・明解C言語で学ぶアルゴリズムとデータ構造第2版,柴田望洋、SBクリエイティブ
担当教員	徳光 政弘

到達目標

(1) 時間・領域の計算量によってアルゴリズムを比較・評価できることを説明できる。
(2) 同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。
(3) リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
時間・領域の計算量によってアルゴリズムを比較・評価できることを説明できる。	時間・領域の計算量によってアルゴリズムを比較・評価できることを説明できる。	時間・領域のどちらかの計算量によってアルゴリズムを比較・評価できることを説明できる。	時間・領域の計算量によってアルゴリズムを比較・評価できることを説明できない。
同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	同一の問題に対し、それを解決できるアルゴリズムが存在しうることを説明できる。	同一の問題に対し、それを解決できるアルゴリズムが存在しうることを説明できない。
リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。	リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装することができる。	リスト構造、スタック、キュー、木構造などの基本的なデータ構造の一部を実装できる。	リスト構造、スタック、キュー、木構造などの基本的なデータ構造を実装できない。

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

学習・教育到達度目標 A （技術者としての基礎力）

教育方法等

概要:

コンピュータを用いた計算処理・情報処理は、半導体技術の技術革新に伴うハードウェアの性能向上だけでなく、コンピュータ上で実行するプログラムの計算手順（アルゴリズム）およびデータ構造の進化が大きく貢献している。コンピュータグラフィックス、画像処理、音声処理、信号処理、データベース等、さまざまな分野で工夫されたアルゴリズムとデータ構造が開発され、適用されている。本講義では、基礎的なアルゴリズムとデータ構造を学習し、実際にプログラミングして実装することでそのアイデアや考え方を修得する。そして、同一の問題に対して複数のアルゴリズム・データ構造が適用できることを理解し、領域・時間の計算量を見積もることで、適切なアルゴリズムを選択・実装できることを目指す。

授業の進め方・方法:

(1) 座学による講義とプログラミング演習を中心に、必要に応じて小テストおよび課題（レポート）を実施する。講義中に課す課題は、講義で学んだ内容に関して理解を確認し、演習する機会であるため、必ず問題を解き、提出すること。
(2) 試験は、授業計画に記載のとおり、前期中間試験、前期期末試験、後期中間試験、学年末試験の４回実施する。積極的に授業に参加することが肝要である。
(3) 本科目の内容は、情報工学の基礎、オペレーティングシステム、金プーたネットワーク、人工知能・機械学習等を始めとするその他情報分野を学習するための基礎科目となっているため、単位の修得だけにとらわれることなく授業内容の理解を深めてもらいたい。
(4) 講義の内容に関して質問等がある場合は、徳光のところまで質問に来ること。疑問点はすぐに解消するように努める。
(5) 本科目の内容を身につけるためには、演習やプログラミングによる確認等を行い、実際に考えたり、手を動かすことが重要である。資料やプログラムをただ眺めるのではなく、実際に自ら思考し、手を動かして紙に考えを書き出したり、アウトプットすることを心がけることを強くお薦めする。
(6) 本科目に関する諸連絡、課題、補足資料等についてTeams・WebClassに掲載するので、必要に応じて参照すること。
(7) 授業では教科書、ノートを持参すること。

注意点:

授業の属性・履修上の区分

アクティブラーニング

ICT 利用

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		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週	振り返り	試験結果を振り返る。

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

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

評価割合

	試験	発表	相互評価	態度	ポートフォリオ	その他	合計
総合評価割合	50	10	0	0	0	40	100
基礎的能力	50	10	0	0	0	40	100
専門的能力	0	0	0	0	0	0	0
分野横断的能力	0	0	0	0	0	0	0