|
システム最適化
|
|
| 担当教員 |
久野誉人、佐野良夫
|
| 電子メール | 久野誉人: takahito (at) cs.tsukuba.ac.jp, 佐野良夫: sano (at) cs.tsukuba.ac.jp |
| URL | http://www.cs.tsukuba.ac.jp/~takahito/gcourse.html |
| オフィスアワー | F932（久野） F834（佐野） 随時（メールでアポイントメントのこと） |
| 科目番号 | 01CH109, 01CJ211 |
| 分野 | 数理情報工学，専修プログラム |
| 基礎／専門の別 | |
| 授業形態 | 講義 |
| 開講学期 | 春A |
| 時限 | 火3,4 |
| 教室 | 3B311 |
| キーワード | 数理最適化，アルゴリズム，計算の複雑さ |
| Keyword | Mathematical optimization, algorithm, computational complexity |
| 前提条件 | 線形代数，解析 |
| 学習目標 | 数理最適化問題の基礎的事項に関する知識を身につけるとともに，計算の複雑さに関する基礎的理論を理解する． |
| 概要 | 数理最適化問題とそのシステム運用／設計への応用に係る幾つかのトピックスを中心に，求解に必要な最適化アルゴリズムの仕組みとその計算の複雑 さについて議論する． |
| 授業計画 |
第１回：システム設計／運用のための最適化問題I (定 義） （線形計画問題，組合せ最適化・整数計画問題， etc. ） 第２回：システム設計／運用のための最適化問題II (応 用例） （線形計画問題，組合せ最適化・整数計画問題， etc.） 第３回：計算の複雑さとアルゴリズム I （多項式時間アルゴリズム，指数時間アルゴリズム， etc. ） 第４回：計算の複雑さとアルゴリズム II （クラスP，NP，多項式時間還元，etc. ） 第５回：計算の複雑さとアルゴリズム III （NP完全，NP困難，etc.） |
| 教科書 | 特に指定しない．指定するWEBページから各自ダウンロ ード． |
| 参考書 |
・「数理最適化」（ 久野・繁野・後藤，オーム社， 2012） ・「最適化法」（ 田村・村松，共立出版，2002） ・「巡回セール スマン問題への招待」（ 山本・久保， 朝倉 書店，1997） ・「最適化ハンドブッ ク」（ Nemhauser他 (伊理他監 訳)，朝倉書店，1995） ・「線形計画法」 （ 今野 浩，日科技連，1987） |
| 成績評価 | レポートの提出・発表，小テストなどの結果を総合し て 評価する． |
| TF・TA | |
| その他の情報 | |