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

科目基礎情報

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

到達目標

様々なデータ構造とそれを取り扱うアルゴリズムを理解する
(1) 基本的なデータ構造について理解する
(2) 基本的なデータ構造の実現方法について理解する
(3) 基本的なアルゴリズムを理解する
(4) 基本的なアルゴリズム設計技法を理解する
(5) 効率の評価法を理解し,データ構造・アルゴリズムの違いにより効率が異なる ことを理解する

ルーブリック

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

教育方法等

概要:

授業の進め方・方法:

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

注意点:

第2学年・第3学年のプログラミングの知識が必要なので,十分復習しておくこと。
演習には積極的に取り組み,指定された課題を提出すること。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	計算量(オーダー記法)
		2週	基本的なデータ構造(リスト,スタック,待ち行列)
		3週	基本的なデータ構造(グラフ,木のデータ構造,木のなぞり,2分木,集合)
		4週	基本的なデータ構造(辞書,ハッシュ,互いに素な集合族)
		5週	基本的なデータ構造(順序付集合,優先度付き待ち行列,ヒープ)
		6週	2分探索木
		7週	並行探索木(AVL 木)
		8週	中間試験
	2ndQ
		9週	整列アルゴリズム(バブルソート,バケットソート)
		10週	整列アルゴリズム(ヒープソート,クイックソート)
		11週	整列データの処理,分割統治法(マージソート)
		12週	動的計画法(SUBSET-SUM)
		13週	資源配分問題,欲張り法(Greedy Method)
		14週	グラフ(プリム,クラスカル,ダイクストラ)
		15週	文字列照合(BM 法)
		16週

評価割合

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