シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 開講年度 /Academic year |
2014年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 連携専門科目 | ||
| 開講類・専攻 /Cluster/Department |
情報・通信工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 | ||
| 公開E-mail |
okamotoy の後に @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/fdopt/ | ||
| 更新日 /Last update |
2014/03/10 03:01:45 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ． 今年度は「組合せ最適化における線形計画法の利用」を題材とする． 線形計画法の基礎概念を復習した後で，特に「緩和」，「双対性」，「整数性」の3つをキーワードとして，組合せ最適化問題に対して線形計画法を用いてどのようにアプローチするのか講義する． 基本的な概念の理解，および，解析手法を学び，例に対して応用が可能となることを目標とする． |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学，線形代数学第一 |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
数理計画法，数理解析 (グラフとネットワーク)，アルゴリズム論第一，アルゴリズム論第二，線形代数学第二 (あるいは，それに準じる内容) |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書：なし．資料を毎回用意する． |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
進め方：講義では基礎概念と考え方について学ぶ．また，演習問題を解く時間を講義中にも設けて，その中で講義に現れた概念の理解を深める． 授業計画： 第１回： 線形計画問題と整数計画問題 第２回： 組合せ最適化問題と整数計画問題 第３回： 凸多面体の基礎 第４回： 凸多面体の整数性 第５回： 双対性の幾何学 第６回： 完全双対整数性 第７回： 完全双対整数性の幾何学 第８回： 完全双対整数性：ネットワークフロー 第９回： 完全双対整数性：全域木 第１０回： 完全双対整数性：マッチング 第１１回： 切除平面法 第１２回： 切除平面法：巡回セールスマン問題 第１３回： 整数性ギャップ：下界 第１４回： 整数性ギャップ：上界 第１５回： まとめ |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： 期末試験によって評価を行う． 評価基準： 線形計画法，整数計画法，組合せ最適化における基本的な概念を理解し，解析手法と例に対する応用ができること． |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
金曜5限．時間が不都合な場合はメールにて相談してください． |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
組合せ最適化の真髄を味わいます．組合せ最適化問題を理解しようとするとき，高次元凸多面体が手に取るように見えてくるかどうかということが，大きな違いを生み出します．なぜ凸多面体が役に立つのか (数学)，それが高速アルゴリズムにどうつながっていくのか (計算)，といった，様々な側面を大学院の講義らしく紹介します． |
| その他 /Others |
情報数理工学コース以外の学生も歓迎します．他コースだけではなく，他専攻，他研究科の学生も歓迎します． |
| キーワード /Keywords |
線形計画法，整数計画法，組合せ最適化，双対定理，相補性定理，凸多面体，ファセット，凸錐，法錐，法扇，線形計画緩和，整数多面体，完全双対整数性，ヒルベルト基底，切除平面法，整数性ギャップ，ネットワークフロー，全域木，マッチング，巡回セールスマン問題，安定集合，頂点被覆 |