シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2017年度 | 開講年次 /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/2017/geomcover/ | ||
| 更新日 /Last update |
2017/03/13 15:40:47 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
離散最適化における1つのトピックを集中的に学ぶ． 今年度は「幾何的被覆問題」を題材とする． 離散最適化問題に対して幾何的性質をどのように用いるのか，その数理的側面と計算的側面の双方を意識して講義する． 基本的な概念の理解，および，解析手法を学び，例に対して応用が可能となることを目標とする． The course provides intensive discussion on a single topic of discrete optimization. The topic of this fiscal year is "Geometric Covering Problems," with which we learn how to use geometric properties to solve discrete optimization problems from both mathematical and computational viewpoints. The goal is to understand the basic concepts, to learn methods for desining and analyzing algorithms, and to be able to apply the methods to examples. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学，アルゴリズム論第一，確率統計 (あるいは，それらに準じる内容) Discrete Mathematics, Algorithms I, Probability and Statistics (or similar courses) |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
グラフとネットワーク，アルゴリズム論第二，離散数理工学 (あるいは，それらに準じる内容) Graphs and Networks, Algorithms II, Discrete Mathematical Engineering (or similar courses) |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書：なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書：以下の書籍を参考にする． M. de Berg, O. Cheong, M. Overmars, and M. van Kreveld, Computational Geometry: Algorithms and Applications, Springer, 2008. J. Matousek, Lectures on Discrete Geometry, Springer, 2002. S. Har-Peled, Geometric Approximation Algorithms, AMS, 2011. その他，参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books: M. de Berg, O. Cheong, M. Overmars, and M. van Kreveld, Computational Geometry: Algorithms and Applications, Springer, 2008. J. Matousek, Lectures on Discrete Geometry, Springer, 2002. S. Har-Peled, Geometric Approximation Algorithms, AMS, 2011. The related materials will be referred to in the class. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
進め方：講義では基礎概念と考え方について学ぶ．また，演習問題を解く時間を講義中にも設けて，その中で講義に現れた概念の理解を深める． 授業計画： 第１回： 幾何的被覆問題とは？ 第２回： 最小包囲円問題(1)：基本的な性質 第３回： 最小包囲円問題(2)：乱択アルゴリズム 第４回： クラスタリング(1)：k-センター 第５回： クラスタリング(2)：k-メディアン 第６回： 幾何ハイパーグラフ(1)：VC次元 第７回： 幾何ハイパーグラフ(2)：εネット 第８回： 幾何的被覆問題(1)：線形計画法の利用 第９回： 幾何的被覆問題(2)：シフト法 第１０回： 幾何的被覆問題(3)：局所探索法 第１１回： 幾何的被覆問題(4)：局所探索法の解析 第１２回： 幾何ハイパーグラフ(3)：εネット定理の証明 第１３回： 幾何アレンジメント(1)：合併複雑度とεネット 第１４回： 幾何アレンジメント(2)：合併複雑度の例 第１５回： 最近のトピック Plan: Basic concepts will be discussed in the class. Deeper understanding and applications will be complemented with homework and exercises. Schedule: 1) What are geometric covering problems? 2) Minimum enclosing disk problem (1): Basic properties 3) Minimum enclosing disk problem (2): Randomized algorithms 4) Clustering (1): k-Center 5) Clustering (2): k-Median 6) Geometric hypergraphs (1): VC-dimensions 7) Geometric hypergraphs (2): Epsilon-nets 8) Geometric covering problems (1): Use of linear programming 9) Geometric covering problems (2): Shifting strategy 10) Geometric covering problems (3): Local search 11) Geometric covering problems (4): Analysis of local search 12) Geometric hypergraphs (3): Proof of the epsilon-net theorem 13) Geometric arrangements (1): Union complexity 14) Geometric arrangements (2): Examples of union complexity 15) Recent topics |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
演習問題を解き，レポートとして提出することを推奨する．(なお，レポートは成績評価に勘案されない．) Solving exercises, and submitting as a report |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： 期末試験によって評価を行う． 評価基準： 幾何的被覆問題に関する基本的な概念を理解し，解析手法と例に対する応用ができること．出題される演習問題の半分程度を解くことができる能力を最低達成基準とする． Evaluation: Final exam Evaluation criteria: Understanding of basic concepts on geometric covering problems, and ability of application of methods to examples Minimum requirement: Being able to solve half of the exercises |
| オフィスアワー： 授業相談（1,000文字以内） /Office hours（up to 1,000 letters） |
金曜5限．時間が不都合な場合はメールにて相談． Appointment by email |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
計算幾何学のフレーバーを持つ最適化問題の中でも，幾何的被覆問題は重要な役割を演じ，ワイヤレスネットワークや地理情報システムの応用にも数多く現れてきます．その理論は完全に理解されたという状況から遠い位置にありますが，それでも既に深遠な結果がいくつも存在します．この講義では，その理論の一端を垣間見れるようにしていきます． Geometric covering problems play an important role among optimization problems with geometric flavor, and appear in a lot of applications such as wireless networks and geographic information systems. Their theory has not been well understood, but still several deep results already exist. In this course, we will glance at aspects of those results. |
| その他 /Others |
情報数理工学プログラム以外の学生も歓迎します．他プログラムだけではなく，他専攻の学生も歓迎します． |
| キーワード /Keywords |
計算幾何，乱択アルゴリズム，集合被覆問題，集合横断問題，幾何ハイパーグラフ，領域空間，VC次元，粉砕関数，Radonの定理，Hellyの定理，εネット，貪欲法，線形計画法，局所探索法，シフト法，平面グラフ，アレンジメント，合併複雑度，Clarkson-Shorの技法 computational geometry, randomized algorithm, set cover problem, transversal problem, geometric hypergraph, range space, VC-dimension, shattering function, Radon's theorem, Helly's theorem, epsilon-net, greedy algorithm, linear programming, local search, shifting strategy, planar graph, arrangement, union complexity, Clarkson-Shor's technique |