科目名	最適化技法
単位数	2.0
担当者	准教授　上土井　陽子
履修時期	後期（第４ターム）
履修対象	２年
講義形態	講義
講義の目的	情報工学，計算機科学のさまざまな分野において利用されている各種の最適化技法・アルゴリズムについて，広く概観することを目的とする．特に，組合せ最適化問題に対する各種の解法，また，発見的解法，近似解法，NP-完全，NP-困難の概念の解説により，それらの概念の重要性を理解する．計算機科学に関する多くの最適化問題はグラフ上で定義されることが多く，よって，グラフに関する代表的な最適化問題を中心とした題材に触れる．この講義を通じ，回路設計やネットワーク接続などの応用分野から発生した対象問題に対するアルゴリズムの本質，問題を解くための基礎となる理論を理解し，自らが今後取り組む分野での諸問題を効率的に解くアルゴリズムを設計するための基礎を身につけることを目標とする． （授業形態：講義）
到達目標	最適化問題とそれら問題を解くための基礎となる理論を理解することを目標とする．具体的には １．最適化問題の難しさの表現法 ２．代表的な最適化問題の厳密解法 ３．多くの組合せ最適化問題に適用できる発見的解法の動作 ４．解の精度を保証する近似解法 を理解し，問題を解くための基礎を身につける．【知識２，技能１】 さらに，上記で身につけた知識・技能を用いて，自らがアルゴリズムを設計できるようになる．【思考力・判断力，主体性】
受講要件	「データ構造とアルゴリズムI」を修得していること，「離散数学」，「データ構造とアルゴリズムII」を履修していることが望ましい．
履修取消の可否	可
履修取消不可の理由
事前・事後学修	必要に応じて事前事後学習のための課題を課す．授業時間以外の自主的な学修時間として，合計30時間程度を想定する．
講義内容	１．イントロダクションー組合せ最適化問題とはー ２．PとNP，判定問題，問題の帰着（充足可能性問題，巡回セールスマン問題） ３．線形計画問題 ４．シンプレックス法 ５．ネットワーク理論（１）（最大流問題） ６．ネットワーク理論（２）（最小カット問題） ７．ネットワーク理論（３）（最大マッチング問題） ８．中間まとめ ９．組合せ最適化，近似解法，発見的手法（ナップサック問題） １０．分枝限定法 １１．切除平面法 １２．動的計画法（最短路問題） １３．焼きなまし法 １４．解の精度を保証する近似解法（巡回セールスマン問題） １５．グラフの最適化問題（最小木問題・最小点被覆問題） ※授業の順序は変更することがある． ※上記とは別に期末試験を実施する．
期末試験実施の有無	実施する
評価方法・基準	試験および演習，レポート等を課し，1. 前半の成績（50％），2. 後半の成績（50％）の割合で成績を総合的に評価する． また，各成績は試験が90％，レポート課題が10％の割合で評価する．評価基準は次のとおり． ・最適化問題とその定式化およびその複雑度を理解している． ・基本的・代表的な最適化問題の厳密解法を理解している． ・組合せ最適化問題に対するヒューリスティックの動作を理解している． ・解の精度を保証する近似解法を理解している．
教科書等	教科書：穴井宏和,斉藤努共著「今日から使える！組合せ最適化-離散問題ガイドブック-」（講談社） 参考書：久保幹雄著「組合せ最適化とアルゴリズム」（共立出版） 　　　　長尾智晴著「最適化アルゴリズム」（昭晃堂） 　　　　柳浦睦憲,茨木俊秀共著「組合せ最適化ーメタ戦略を中心としてー」（朝倉書店） 　　　　R.セジウィック著，野下浩平,星守,佐藤創,田口東共訳 　　　　　　　　　「アルゴリズムC++」（近代科学社）
担当者プロフィール	上土井陽子：主に、データマイニング、分散コンピューティングに関する研究に従事．情報工学専攻　所属．問合せ先は情報科学部棟4階414号室．
講義に関連する実務経験
課題や試験に対するフィードバック	WebClass，対面もしくは対面授業によりレポート課題の採点結果，および，再考すべき点などを連絡します．試験の総評を対面授業時またはWebClassより通知します．
アクティブ・ラーニング	振り返り，その他：レポートライティング，その他：演習
キーワード	最適化，組合せ最適化，線形計画問題，動的計画法，アルゴリズム，グラフ，近似解法，発見的手法
備考	【教職】高一種（数学）