シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2016年度 | 開講年次 /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/2016/treewidth/ | ||
| 更新日 /Last update |
2016/03/01 15:44:26 | 更新状況 /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） |
教科書：なし．講義資料を毎回用意するので，講義webページより各自入手すること． その他，参考文献は講義中に挙げる． |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
進め方：講義では基礎概念と考え方について学ぶ．また，演習問題を解く時間を講義中にも設けて，その中で講義に現れた概念の理解を深める． 授業計画： 第１回： 離散最適化における木分解の役割 第２回： 木に対するアルゴリズム設計 第３回： 道分解と道幅 第４回： 道分解を用いたアルゴリズム設計 第５回： 木分解と木幅 第６回： 木幅の性質 第７回： 木分解を用いたアルゴリズム設計：頂点集合の選択 第８回： 木分解を用いたアルゴリズム設計：頂点集合の分割 第９回： 木分解を用いたアルゴリズム設計：その他の問題 第１０回： 木幅と論理：単項二階論理 第１１回： 木幅と論理：オートマトン 第１２回： 木幅と論理：アルゴリズム設計 第１３回： 木分解構成アルゴリズム：準備 第１４回： 木分解構成アルゴリズム 第１５回： まとめ |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
演習問題を解き，レポートとして提出することを推奨する．(なお，レポートは成績評価に勘案されない．) |
| 成績評価方法 および評価基準 （最低達成基準を含む） （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 |
道，木，道分解，道幅，木分解，木幅，動的計画法，単項二階論理，Courcelleの定理 |