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

科目基礎情報

学校	岐阜工業高等専門学校	開講年度	2017
授業科目	データ構造とアルゴリズム
科目番号	0227	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 1
開設学科	電気情報工学科	対象学年	5
開設期	前期	週時間数	1
教科書/教材	C によるアルゴリズムとデータ構造(茨木俊秀・オーム社)
担当教員	出口 利憲

到達目標

以下の各項目を到達目標とする
(1) 基本的なデータ構造について理解する
(2) 基本的なデータ構造の実現方法について理解する
(3) 基本的なアルゴリズムを理解する
(4) 基本的なアルゴリズム設計技法を理解する
(5) 効率の評価法を理解し,データ構造・アルゴリズムの違いにより効率が異なる ことを理解する

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	基本的なデータ構造に関する問題 を正確(80%)に解くことができ る	基本的なデータ構造に関する問題 をほぼ正確(60%)に解くことが できる	基本的なデータ構造に関する問題 を解くことができない
評価項目2	基本的なデータ構造の実現に関す る問題を正確(80%)に解くこと ができる	基本的なデータ構造の実現に関す る問題をほぼ正確(60%)に解く ことができる	基本的なデータ構造の実現に関す る問題を解くことができない
評価項目3	整列,探索などに関する問題を正 確(80%)に解くことができる	整列,探索などに関する問題をほ ぼ正確(60%)に解くことができ る	整列,探索などに関する問題を解 くことができない
	分割統治法,動的計画法などに関 する問題を正確(80%)に解くこ とができる	分割統治法,動的計画法などに関 する問題をほぼ正確(60%)に解 くことができる	分割統治法,動的計画法などに関 する問題を解くことができない
	オーダーに関する問題を正確 (80%)に解くことができる	オーダーに関する問題をほぼ正確 (60%)に解くことができる	オーダーに関する問題を解くこと ができない

教育方法等

概要:

様々なデータ構造とそれを取り扱うアルゴリズムを理解する

授業の進め方・方法:

教科書に沿って授業をすすめるが,教科書の内容から離れることもあるので講義に集中すること。

注意点:

第2学年・第3学年のプログラミングの知識が必要なので,十分復習しておくこと。
演習には積極的に取り組み,指定された課題を提出すること。
なお,教室外学修の内容は演習課題および試験問題を通じて成績評価に含まれる。
学習教育・目標：(D-2 設計・システム系)１００％，
JABEE 基準1(1)：(d)

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	計算量(オーダー記法)（AL のレベル C）	オーダー記法を理解する （教室外学修）計算量に関する演習
		2週	基本的なデータ構造(リスト,スタック,待ち行列)（AL のレベル C）	スタック・待ち行列を理解する （教室外学修）基本的なデータ構造に関する演習
		3週	基本的なデータ構造(グラフ,木のデータ構造,木のなぞり,2分木,集合)（AL のレベル C）	木を理解する （教室外学修）基本的なデータ構造に関する演習
		4週	基本的なデータ構造(辞書,ハッシュ,互いに素な集合族)（AL のレベル C）	ハッシュを理解する 互いに素な集合族の実現法を理解する （教室外学修）基本的なデータ構造に関する演習
		5週	基本的なデータ構造(順序付集合,優先度付き待ち行列,ヒープ)（AL のレベル C）	ヒープを理解する （教室外学修）基本的なデータ構造に関する演習
		6週	2分探索木（AL のレベル C）	２分探索木を理解する （教室外学修）探索木に関する演習
		7週	並行探索木(AVL 木)（AL のレベル C）	AVL木を理解する （教室外学修）探索木に関する演習
		8週	中間試験	（教室外学修）探索木に関する演習
	2ndQ
		9週	整列アルゴリズム(バブルソート,バケットソート)（AL のレベル C）	バブルソート等およびバケットソート等を理解する （教室外学修）整列アルゴリズムに関する演習
		10週	整列アルゴリズム(ヒープソート,クイックソート)（AL のレベル B）	ヒープソート・クイックソートを理解する 決定木を理解する （教室外学修）整列アルゴリズムに関する演習
		11週	整列データの処理,分割統治法(マージソート)（AL のレベル C）	分割統治法を理解する （教室外学修）ソフトウェア設計技法に関する演習
		12週	動的計画法(SUBSET-SUM)（AL のレベル C）	動的計画法を理解する （教室外学修）ソフトウェア設計技法に関する演習
		13週	資源配分問題,欲張り法(Greedy Method)（AL のレベル C）	資源配分問題を理解する 欲張り法を理解する （教室外学修）ソフトウェア設計技法に関する演習
		14週	グラフ(プリム,クラスカル,ダイクストラ)（AL のレベル C）	グラフの実現を理解する 最小木を求める手法を理解する （教室外学修）グラフアルゴリズムに関する演習
		15週	文字列照合(BM 法)	BM法を理解する
		16週

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

分類		分野	学習内容	学習内容の到達目標	到達レベル	授業週
専門的能力	分野別の専門工学	情報系分野	ソフトウェア	アルゴリズムの概念を説明できる。	2
				与えられたアルゴリズムが問題を解決していく過程を説明できる。	2
				同一の問題に対し、それを解決できる複数のアルゴリズムが存在しうることを説明できる。	2
				時間計算量や領域計算量などによってアルゴリズムを比較・評価できることを理解している。	2
				整列、探索など、基本的なアルゴリズムについて説明できる。	2
				コンピュータ内部でデータを表現する方法(データ構造)にはバリエーションがあることを説明できる。	2
				同一の問題に対し、選択したデータ構造によってアルゴリズムが変化しうることを説明できる。	2
				リスト構造、スタック、キュー、木構造などの基本的なデータ構造の概念と操作を説明できる。	2

評価割合

	試験	演習	合計
総合評価割合	80	20	100
得点	80	20	100