アルゴリズム理論

科目基礎情報

学校	明石工業高等専門学校	開講年度	令和02年度 (2020年度)
授業科目	アルゴリズム理論
科目番号	0041	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 2
開設学科	機械・電子システム工学専攻	対象学年	専2
開設期	後期	週時間数	2
教科書/教材	五十嵐善英、西谷泰昭:「アルゴリズムの基礎」、コロナ社
担当教員	濱田 幸弘

到達目標

　[1] アルゴリズムの基礎知識と基本的なデータ構造を説明できる(D)。
　[2] 現実の問題をグラフ上の問題として定式化することができる(F)。
　以下にあげるアルゴリズムとそれらの時間計算量を把握する(H)。
　[3] 最小全域木を構成するアルゴリズム
　[4] グラフを探索するアルゴリズム
　[5] 最短経路問題を解くアルゴリズム
　[6] 最大フロー問題を解くアルゴリズム
　[7] 文字列照合アルゴリズム

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目1	計算量、オーダ、リスト、スタック、キュー、ヒープ、グラフ、木を的確に説明できる。	計算量、オーダ、リスト、スタック、キュー、ヒープ、グラフ、木を説明できる。	計算量、オーダ、リスト、スタック、キュー、ヒープ、グラフ、木を説明できない。
評価項目2	各種委員会の開催日を決定する問題を的確に定式化することができる。	各種委員会の開催日を決定する問題を定式化することができる。	各種委員会の開催日を決定する問題を定式化することができない。
評価項目3	Kruskal、Primのアルゴリズムとそれらの時間計算量を的確に説明できる。	Kruskal、Primのアルゴリズムとそれらの時間計算量を説明できる。	Kruskal、Primのアルゴリズムとそれらの時間計算量を説明できない。
評価項目4	深さ優先探索アルゴリズム、幅優先探索アルゴリズムとそれらの時間計算量を的確に説明できる。	深さ優先探索アルゴリズム、幅優先探索アルゴリズムとそれらの時間計算量を説明できる。	深さ優先探索アルゴリズム、幅優先探索アルゴリズムとそれらの時間計算量を説明できない。
評価項目5	Dijkstra、Bellman-Ford、Floydのアルゴリズムとそれらの時間計算量を的確に説明できる。	Dijkstra、Bellman-Ford、Floydのアルゴリズムとそれらの時間計算量を説明できる。	Dijkstra、Bellman-Ford、Floydのアルゴリズムとそれらの時間計算量を説明できない。
評価項目6	ord-Fulkerson、Edmonds-Karp、Push-relabelアルゴリズムとそれらの時間計算量を的確に説明できる。	Ford-Fulkerson、Edmonds-Karp、Push-relabelアルゴリズムとそれらの時間計算量を説明できる。	ord-Fulkerson、Edmonds-Karp、Push-relabelアルゴリズムとそれらの時間計算量を説明できない。
評価項目7	Knuth-Morris-Pratt、Boyer-Mooreのアルゴリズムとそれらの時間計算量を的確に説明できる。	Knuth-Morris-Pratt、Boyer-Mooreのアルゴリズムとそれらの時間計算量を説明できる。	Knuth-Morris-Pratt、Boyer-Mooreのアルゴリズムとそれらの時間計算量を説明できない。

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

学習・教育目標 (D) （基礎学力と自主的・継続的学習能力）

学習・教育目標 (F) （柔軟かつ創造的な設計能力）

学習・教育目標 (H) （多次元的なシステム思考）

教育方法等

概要:

グラフアルゴリズムと文字列照合アルゴリズムについて学ぶ。グラフは頂点集合と辺集合の2項組で定義され、現実の問題における「もの」とそれらの間の「関係」または「接続」を表現するのによく用いられる。現実の問題をグラフ上の問題として定式化して、グラフ上で解くことにより現実の問題の解を得ることができる。文字列は計算機で扱われるデータの中で最も重要なもののひとつである。文書ファイルやソースファイルなどの文字列データの中から、指定された文字列を効率よく見つけるアルゴリズムについて学ぶ。

授業の進め方・方法:

講義形式

注意点:

本科目は、授業で保証する学習時間と、予習・復習及び課題レポート作成に必要な標準的な自己学習時間の総計が、90時間に相当する学習内容である。受講に当たっては、C言語によるプログラミングを習得しておくことが望ましい。
合格の対象としない欠席条件(割合) 1/3以上の欠課

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	アルゴリズムの基礎知識	アルゴリズム、計算量、オーダについて説明できる。
		2週	基本的なデータ構造	リスト、スタック、キュー、ヒープについて説明できる。
		3週	現実の問題をグラフ上の問題として定式化する方法	グラフと木について説明できる。各種委員会の開催日を決定する問題をグラフ上の問題として定式化することができる。
		4週	最小全域木を構成するアルゴリズム 1/2	Kruskalのアルゴリズム、集合操作のアルゴリズムとそれらの時間計算量を説明できる。
		5週	最小全域木を構成するアルゴリズム 2/2	Primのアルゴリズムとその時間計算量を説明できる。
		6週	グラフを探索するアルゴリズム	深さ優先探索アルゴリズム、幅優先探索アルゴリズムとそれらの時間計算量を説明できる。
		7週	最短経路問題を解くアルゴリズム 1/2	単一頂点からの最短経路を求めるDijkstraのアルゴリズムとその時間計算量を説明できる。
		8週	中間試験 第1週から第6週までの内容を試験範囲とする。
	4thQ
		9週	最短経路問題を解くアルゴリズム 2/2	単一頂点からの最短経路を求めるBellman-Fordのアルゴリズムとすべての頂点間の最短経路を求めるFloydのアルゴリズムについて説明できる。また、それらの時間計算量を説明できる。
		10週	最大フロー問題を解くアルゴリズム 1/2	Ford-Fulkersonのアルゴリズム、Edmonds-Karpのアルゴリズムとそれらの時間計算量を説明できる。
		11週	最大フロー問題を解くアルゴリズム 2/2	Push-relabelアルゴリズムとその時間計算量を説明できる。
		12週	文字列照合アルゴリズム 1/3	Knuth-Morris-Prattのアルゴリズムとその時間計算量を説明できる。
		13週	文字列照合アルゴリズム 2/3	Boyer-Mooreのアルゴリズム(高速化のアイデアその1)とその時間計算量を説明できる。
		14週	文字列照合アルゴリズム 3/3	Boyer-Mooreのアルゴリズム(高速化のアイデアその2)とその時間計算量を説明できる。
		15週	アルゴリズム理論からアルゴリズム工学へ	アルゴリズム理論と現実とのギャップを埋める「アルゴリズム工学」について説明できる。
		16週	期末試験

評価割合

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