Algorithms

Course Information

College	Akashi College	Year	2020
Course Title	Algorithms
Course Code	0041	Course Category	Specialized / Elective
Class Format	Lecture	Credits	Academic Credit: 2
Department	Mechanical and Electronic System Engineering	Student Grade	Adv. 2nd
Term	Second Semester	Classes per Week	2
Textbook and/or Teaching Materials	五十嵐善英、西谷泰昭:「アルゴリズムの基礎」、コロナ社
Instructor	HAMADA Yukihiro

Course Objectives

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

Rubric

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
評価項目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のアルゴリズムとそれらの時間計算量を説明できない。

Assigned Department Objectives

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

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

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

Teaching Method

Outline:

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

Style:

講義形式

Notice:

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

Course Plan

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

Evaluation Method and Weight (%)

	試験	発表	相互評価	態度	ポートフォリオ	その他	Total
Subtotal	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