アルゴリズム特論

科目基礎情報

学校	釧路工業高等専門学校	開講年度	令和03年度 (2021年度)
授業科目	アルゴリズム特論
科目番号	0026	科目区分	専門 / 選択
授業形態	講義	単位の種別と単位数	学修単位: 2
開設学科	電子情報システム工学専攻	対象学年	専1
開設期	後期	週時間数	2
教科書/教材	教科書：アルゴリズムサイエンス 浅野 共立出版，参考書：アルゴリズムとデータ構造 平田 森北出版，参考書：アルゴリズムの基礎 岩野 朝倉出版
担当教員	本間 宏利

到達目標

・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・離散最適化問題クラスについて説明できる．
・スケージュリングアルゴリズム，最適化アルゴリズム，意思決定アルゴリズムなどの発展型アルゴリズムを用いての離散最適化問題を解くことができる．

ルーブリック

	理想的な到達レベルの目安	標準的な到達レベルの目安	未到達レベルの目安
	基本的なアルゴリズムや再帰アルゴリズムの動作や計算量解析の説明ができる．	基本的なアルゴリズムや再帰アルゴリズムの動作を説明できる．	基本的なアルゴリズムの動作を説明できない．
	離散最適化問題のクラスの差異や問題の帰着の原理について説明できる．	離散最適化問題のクラスの差異について説明できる．	離散最適化問題のクラスの差異について説明できない．
	各種離散最適化問題の定式化と最適解の導出ができる．	各種離散最適化問題の定式化ができる．	各種離散最適化問題の定式化ができない．

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

学習・教育到達度目標 Ｄ  （技術者として自己の基盤となる専門分野の知識（専門応用系，工学実験系，問題解決系，実務対応系）を修得し，それを応用する能力を身につけている。）

JABEE d-1

教育方法等

概要:

多様化，複雑化する問題に対して，効率的な計算手法である様々なアルゴリズムが考案されている．
本科目の目標を以下に示す．
・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・離散最適化問題クラスについて説明できる．
・スケージュリングアルゴリズム，最適化アルゴリズム，意思決定アルゴリズムなどの発展型アルゴリズムを用いての離散最適化問題を解くことができる．

授業の進め方・方法:

プレゼンスライドと黒板板書の両方を使った講義形式でおこなう．
小セクションごとに演習問題を与える．
定期試験直前には総合的な演習を行う．
暗記ではなく論理の積み重ねで問題を考える習慣をつける．

成績評価方法：
定期試験2回の成績で行う．
中間試験(50%)，期末試験(50%)
合否判定：最終評価（または再試験の素点）≧60％を合格とする．

注意点:

基本的な離散数学の知識が必要である．
手続き型プログラミング言語の知識があること．
講義は基本的にプロジェクタを利用して行う．

授業計画

		週	授業内容	週ごとの到達目標
後期
	3rdQ
		1週	計算理論 1	アルゴリズム・手続きの概念を説明できる．
		2週	計算理論 2	O記号の意味と，多項式時間，指数式時間の差異を説明できる．
		3週	計算理論 3	様々なアルゴリズムの計算量解析を行える．
		4週	グラフアルゴリズム 1	グラフの概念，問題のモデル化を説明できる．
		5週	グラフアルゴリズム 2	最短経路問題，最小全域木問題の解法を説明できる．
		6週	グラフアルゴリズム 3	最大流量問題，巡回セールスマン問題の解法を説明できる．
		7週	問題のクラス 1	可解，非可解，クラスP，クラスNPについて説明できる．
		8週	問題のクラス 2	NP完全問題の種類，問題の多項式帰着について説明できる．
	4thQ
		9週	スケジューリングアルゴリズム 1	ジョンソン法を用いた2機械最適化スケジュール問題の解法を説明できる．
		10週	スケジューリングアルゴリズム 2	ジョンソン法を用いた3機械最適化スケジュール問題の解法を説明できる．
		11週	資源最適化アルゴリズム 1	最大化問題・最小化問題の定式化とグラフを使った解法を説明できる．
		12週	資源最適化アルゴリズム 2	最大化問題をシンプレックス法を用いて解くことができる．
		13週	資源最適化アルゴリズム 3	最大化問題を双対シンプレックス法を用いて解くことができる．
		14週	意思決定アルゴリズム 1	様々な意思決定基準とゲーム理論の原理を説明できる．
		15週	意思決定アルゴリズム 2	最適混合戦略による最適解を導出することができる．
		16週	期末試験	この講義の理解度・目標達成度を確認するため，試験を実施する．

評価割合

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