アルゴリズム工学

科目基礎情報

学校	熊本高等専門学校	開講年度	2017
授業科目	アルゴリズム工学
科目番号	AN214	科目区分	専門 / 選択
授業形態	授業	単位の種別と単位数	学修単位: 2
開設学科	電子情報システム工学専攻	対象学年	専2
開設期	前期	週時間数	2
教科書/教材	上野修一、高橋篤司　「情報とアルゴリズム」　森北出版
担当教員	山本 直樹

到達目標

①グラフとネットワークアルゴリズムの考え方と実現技法を応用できる。
②アルゴリズムの解析に関する基本的な概念を理解し説明できる。
③アルゴリズムの設計技法について応用できる。プログラミング演習などを通してアルゴリズムの設計および実装ができる。

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
グラフとその表現および木	グラフの基本的な定義と行列表現、全域木、２分木についてすべて説明でき、これらに関する問題を正しく解くことができる。	グラフの基本的な定義と行列表現、全域木、２分木について説明でき、これらに関する問題を解くことができる。	グラフの基本的な定義と行列表現、全域木、２分木について一部しか説明できず、これらに関する問題を解くことができない。
各種グラフの特徴と性質	２部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題をすべて説明でき、これらに関する問題を正しく解くことができる。	２部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題を説明でき、これらに関する問題を解くことができる。	２部グラフ、オイラーグラフ、ハミルトングラフ、巡回セールスマン問題を一部分しか説明できず、これらに関する問題を解くことができない。
アルゴリズムの解析	関数の漸近的評価手法をすべて説明でき、計算量の観点からアルゴリズムおよびプログラムを的確に評価できる。	関数の漸近的評価手法を説明でき、計算量の観点からアルゴリズムおよびプログラムを評価できる。	関数の漸近的評価手法を一部分しか説明できず、計算量の観点からアルゴリズムおよびプログラムを評価できない。
グラフのアルゴリズム	探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムをすべて説明でき、対象のネットワーク問題に対する実行効率を考慮したプログラムが実装できる。	探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを説明でき、対象のネットワーク問題に対するプログラムが実装できる。	探索アルゴリズム、最短路アルゴリズム、最大全域木アルゴリズムを一部分しか説明できず、対象のネットワーク問題に対するプログラムが実装できない。

教育方法等

概要:

本講義では、グラフとネットワークの概念、アルゴリズムの解析に関する基本的な概念、アルゴリズムの設計技法の概要について説明する。

授業の進め方・方法:

講義の形式で進める。グラフおよび木、各種グラフの特徴と性質、アルゴリズムの解析、グラフのアルゴリズムなどの内容について実施する。

注意点:

規定授業時数 15
1単位あたり30時間程度の自学自習が求められます。

授業計画

		週	授業内容	週ごとの到達目標
前期
	1stQ
		1週	ガイダンス、グラフ	グラフの定義、グラフの種類について説明できる。グラフの操作ができる。
		2週	ネットワーク、基本的な定義	ネットワークについて説明できる。グラフの同形を説明し、それを示すことができる。部分グラフを説明できる。ウォーク、トレイル、路、閉路について説明できる。
		3週	最短路と距離、連結、グラフの行列表現、次数と辺数の関係	端点間の距離、連結の定義、隣接行列等のグラフの行列表現、次数との関係について、説明できる。
		4週	木、全域木	木、全域木の基本的な性質を説明できる。
		5週	根付き木と２分木、２部グラフ	根付き木と２分木、２部グラフの特徴および性質を説明できる。
		6週	グラフの彩色、オイラーグラフ	グラフの彩色を説明できる。また、オイラーグラフの特徴および性質を説明できる。
		7週	完全グラフと完全２部グラフ、ハミルトングラフ	完全グラフおよび完全２部グラフの特徴および性質を説明できる。ハミルトングラフと関連する巡回セールスマン問題の解法を説明できる。
		8週	関数の漸近的評価	関数の漸近的評価について説明でき、関数を評価することができる。
	2ndQ
		9週	問題の定義	アルゴリズム理論における問題の定義を説明できる。
		10週	アルゴリズムの解析、多項式時間アルゴリズム、グラフの大きさ	時間計算量の定義を説明できる。多項式時間アルゴリズムについて説明できる。グラフの大きさの評価を説明できる。
		11週	オイラーグラフ判定問題、深さ優先探索アルゴリズム	連結オイラーグラフ判定問題を説明でき、時間計算量を評価できる。深さ優先探索アルゴリズムを説明でき、時間計算量を評価できる。
		12週	スタック利用深さ優先探索アルゴリズム、順序番号付けアルゴリズム	スタック利用した深さ優先探索アルゴリズムを説明でき、時間計算量を評価できる。順序番号付けアルゴリズムを説明でき、時間計算量を評価できる。
		13週	幅優先探索アルゴリズム、距離ラベル付けアルゴリズム	幅優先探索アルゴリズムを説明でき、時間計算量を評価できる。距離ラベル付けアルゴリズムを説明でき、時間計算量を評価できる。
		14週	最短路アルゴリズム、最長路問題	最短路アルゴリズムを説明でき、時間計算量を評価できる。また、そのアルゴリズムを実装できる。最長路問題について説明できる。
		15週
		16週	最大（最小）全域木アルゴリズム	最大（最小）全域木アルゴリズムを説明でき、時間計算量を評価できる。また、そのアルゴリズムを実装できる。

評価割合

	試験	レポート	合計
総合評価割合	70	30	100
基礎的能力	0	0	0
専門的能力	70	30	100
分野横断的能力	0	0	0