筑波大学教育課程編成支援システム

GB22031 システム数理III

1.0 単位, 3・4 年次, 春C 月5,6
佐野良夫, 久野誉人

授業概要

離散最適化・組合せ最適化の分野における基本的な数理モデル、最適化問題、およびアルゴリズムについて講義する。

備考

GC54301と同一。

授業形態

講義

学位プログラム・コンピテンスとの関係

批判的・創造的思考力、データ・情報リテラシー、広い視野と国際性
ネットワークサイエンス、コンピューティングとシステム、数理的基盤

授業の到達目標(学修成果)

グラフ・ネットワークなどの離散システムにおける基本的な最適化問題,それらの数学的構造,最適化問題を解決するアルゴリズムのメカニズムについて理解する.

キーワード

離散最適化, 組合せ最適化, グラフ, ネットワーク, アルゴリズム

授業計画

離散最適化・組合せ最適化の分野における基本的な数理モデル,最適化問題,およびアルゴリズムについて講義する.

第1回	最小木問題
第2回	最短路問題
第3回	最大流問題
第4回	最小費用流問題
第5回	マッチング問題

履修条件

「情報数学I」または「離散構造」の知識(集合、論理、グラフ理論の基礎)があることを前提とする. また,「システム数理II」を受講していることが望ましい.

成績評価方法

レポートにより成績評価を行う.レポートにおいて満点の60%以上をとること. A+〜Cの評点はこの期末試験の点数に基づく.

学修時間の割り当て及び授業外における学修方法

授業後に授業内容の復習を行うとともに、参考文献等をもとに次回の授業範囲を予習し、専門用語の定義や意味などを理解しておくこと。

教材・参考文献・配付資料等

1. B. Korte and J. Vygen,"Combinatorial Optimization: Theory and Algorithms, Sixth Edition" (Algorithms and Combinatorics 21), Springer (2018)
2. B. コルテ・J. フィーゲン [著] 浅野孝夫・浅野泰仁・小野孝男・平田富夫 [翻訳],「組合せ最適化第2版理論とアルゴリズム」 (丸善出版) 2012年
3. A. Schrijver,"Combinatorial Optimization: Polyhedra and Efficiency" (Algorithms and Combinatorics 24), Springer (2003)

オフィスアワー等(連絡先含む)

特に指定しないが、不在中の訪問を避けるためにメールで事前に連絡を取ることが望ましい.

シラバス参照