筑波大学システム情報工学研究科コンピュータサイエンス専攻科目一覧
システム最適化
担当教員
久野誉人、佐野良夫
電子メール 久野誉人: 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
前提条件 線形代数,解析
学習目標 数理最適化問題の基礎的事項に関する知識を身につけるとともに,計算の複雑さに関する基礎的理論を理解する.
概要 数理最適化問題とそのシステム運用/設計への応用に係る幾つかのトピックスを中心に,求解に必要な最適化アルゴリズムの仕組みとその計算の複雑 さについて議論する.
授業計画 第1回:システム設計/運用のための最適化問題I (定 義)
(線形計画問題,組合せ最適化・整数計画問題, etc. )
第2回:システム設計/運用のための最適化問題II (応 用例)
(線形計画問題,組合せ最適化・整数計画問題, etc.)
第3回:計算の複雑さとアルゴリズム I
(多項式時間アルゴリズム,指数時間アルゴリズム, etc. )
第4回:計算の複雑さとアルゴリズム II
(クラスP,NP,多項式時間還元,etc. )
第5回:計算の複雑さとアルゴリズム III
(NP完全,NP困難,etc.)
教科書 特に指定しない.指定するWEBページから各自ダウンロ ード.
参考書 ・「数理最適化」( 久野・繁野・後藤,オーム社, 2012)
・「最適化法」( 田村・村松,共立出版,2002)
・「巡回セール スマン問題への招待」( 山本・久保, 朝倉 書店,1997)
・「最適化ハンドブッ ク」( Nemhauser他 (伊理他監 訳),朝倉書店,1995)
・「線形計画法」 ( 今野 浩,日科技連,1987)
成績評価 レポートの提出・発表,小テストなどの結果を総合し て 評価する.
TF・TA
その他の情報
ページ先頭へ