アルゴリズム特論

科目基礎情報

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

到達目標

・基本的なアルゴリズムや再帰アルゴリズムの計算量解析ができる．
・離散最適化問題のクラスについて説明できる．
・並列分散アルゴリズムのPRAMモデルについてアルゴリズムの理解と実装ができる．

ルーブリック

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

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

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

JABEE d-1

教育方法等

概要:

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

授業の進め方・方法:

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

成績評価方法：
定期試験の成績で行う．
合否判定：最終評価（または再試験の素点）≧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	遺伝的アルゴリズムによるの問題解法を説明できる．
		10週	遺伝的アルゴリズム 2	初期解や交差手法を選定し遺伝的アルゴリズムのコーディングを行うことができる．
		11週	並列分散アルゴリズム 1	並列計算機モデルの種類や特徴について説明できる．
		12週	並列分散アルゴリズム 2	PRAMのメモリアクセス手法について説明できる．
		13週	並列分散アルゴリズム 3	PRAMアルゴリズムの性能評価方法について説明できる．
		14週	並列分散アルゴリズム 4	基本的なCREW PRAMアルゴリズムにつて説明できる．
		15週	並列分散アルゴリズム 5	基本的なEREW PRAMアルゴリズムにつて説明できる．
		16週	期末試験	この講義の理解度・目標達成度を確認するため，試験を実施する．

評価割合

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