|
システム最適化
|
|
| 担当教員 |
久野誉人、佐野良夫
|
| 電子メール | 久野誉人: takahito (at) cs.tsukuba.ac.jp, 佐野良夫: sano (at) cs.tsukuba.ac.jp |
| URL | https://manaba.tsukuba.ac.jp |
| オフィスアワー | F932（久野） F834（佐野） 随時（メールでアポイントメントのこと） |
| 科目番号 | 01CH109 |
| 分野 | 数理情報工学 |
| 基礎／専門の別 | |
| 授業形態 | 講義 |
| 開講学期 | 春A |
| 時限 | 火3,4 |
| 教室 | 3B311 |
| キーワード | 数理最適化、アルゴリズム、計算の複雑さ |
| Keyword | Mathematical Optimization, Algorithms, Computational Complexity |
| 前提条件 | 線形代数，解析 |
| 学位プログラム・コンピテンスとの関係 | 知の活用力、マネジメント能力、国際性、研究力、知識力 |
| 学習目標 | 数理最適化問題の基礎的事項に関する知識を身につけるとともに、計算の複雑さに関する基礎的理論を理解する。 |
| 概要 | 数理最適化問題とそのシステム運用／設計への応用に係る幾つかのトピックスを中心に、求解に必要な最適化アルゴリズムの仕組みとその計算の複雑さについて議論する。 |
| 授業計画 |
第１回：数理最適化入門 （最適化問題、線形計画問題、整数計画問題、組合せ最適化、巡回セールスマン問題、最短路問題、アルゴリズム、計算量） 第２回：アルゴリズムと計算量 （最短路問題、ベルマン-フォードアルゴリズム、ナップサック問題、動的計画法） 第３回：NP完全性と計算量クラス （判定問題、クラスP、クラスNP、NP完全、NP困難、多項式時間還元、Karpの21のNP完全問題、Cookの定理） 第４回：効率の良いアルゴリズムと数理構造 （最大全域木問題、マトロイド、独立集合、基、階数関数、サーキット、貪欲アルゴリズム、特徴づけ） 第５回：計算困難問題に対するアルゴリズム設計 （ナップサック問題、厳密解法、近似解法、ヒューリスティクス、近似アルゴリズム、全列挙、分枝限定法） |
| 教科書 | 特に指定しない。 |
| 参考書 |
・「組合せ最適化 第2版 理論とアルゴリズム」 B. コルテ・J. フィーゲン［著］浅野孝夫・浅野泰仁・小野孝男・平田富夫［翻訳］（丸善出版）2012年 ・「アルゴリズムデザイン」 J. Kleinberg・E. Tardos［著］浅野孝夫・浅野泰仁・小野孝男・平田富夫［翻訳］（共立出版）2008年 ・「数理最適化（IT Text）」 久野誉人・繁野麻衣子・後藤順哉［著］（オーム社）2012年 |
| 成績評価 | レポート課題を提出して満点の60％以上をとること。 A+～Cの評点は、このレポートの点数に基づいて行う。 |
| TF・TA | |
| その他の情報 | 授業後に配布資料および参考文献を基に授業内容の復習を行うとともに、次回の授業範囲を予習し、専門用語の意味などを理解しておくこと。 |