シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 開講年度 /Academic year |
2015年度 | 開講年次 /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/2015/matroid/ | ||
| 更新日 /Last update |
2015/03/05 06:47:34 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ． 今年度は「組合せ最適化におけるマトロイドの役割」を題材とする． マトロイドと呼ばれる組合せ構造がなぜ役に立つのか，どう役に立つのか，という観点を，その数理的側面と計算的側面の双方を意識して講義する． 基本的な概念の理解，および，解析手法を学び，例に対して応用が可能となることを目標とする． |
|---|---|
| 前もって履修 しておくべき科目（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 |
マトロイド，独立集合，基，サーキット，階数関数，マトロイドの交わり，マトロイドの直和，マトロイドの制限，マトロイドの打ち切り，マトロイドの縮約，貪欲アルゴリズム，交互道，増加道，全域木，マッチング，最大最小定理 |