シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2019年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
| 開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 | ||
| 公開E-mail |
okamotoy followed by @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2019/npc/ | ||
| 更新日 /Last update |
2019/03/05 00:08:38 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（2,000文字以内） /Themes and goals（up to 2,000 letters） |
今年度は「離散最適化における計算困難性」を題材とする． 最適化やアルゴリズムの専門家が未知の問題に対して適切な解法を提供できるのは，計算困難性に対する理解があるからである． つまり，計算困難性を学ぶことで，アルゴリズム設計に対する理解が深まる． その視点の獲得を目指して，計算困難性，特に，NP完全性に関連する概念と手法の理解し，例に対して応用が可能となることを達成目標とする． The course provides intensive discussion on a single topic of discrete optimization. The topic of this academic year is "Computational Complexity in Discrete Optimization." You may wonder why experts on optimization and algortihms are able to select appropriate methods to solve new problems. This is because they have knowledge and understanding on computational complexity. Namely, by learning computational complexity, you will understand algorithm design better. The goal of this course is to understand the basic concepts and methods on computational complexity, in particular NP-completeness, and to be able to apply the methods to examples. |
|---|---|
| 前もって履修 しておくべき科目（1,000文字以内） /Prerequisites（up to 1,000 letters） |
離散数学 Discrete Mathematics |
| 前もって履修しておくこ とが望ましい科目（1,000文字以内） /Recommended prerequisites and preparation（up to 1,000 letters） |
アルゴリズム論第一，アルゴリズム論第二，計算理論，オートマトン理論 (形式言語理論)，グラフとネットワーク Algorithms I, Algorithms II, Theory of Computing, Theory of Automata (Formal Language Theory), Graphs and Networks |
| 教科書等（1,000文字以内） /Course textbooks and materials（up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書： M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979. B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018. その他，参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books: M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., 1979. B. Korte, J. Vygen, Combinatorial Optimization, 6th Edition, Springer, 2018. The related materials will be referred to in the class. |
| 授業内容と その進め方（2,000文字以内） /Course outline and weekly schedule（up to 2,000 letters） |
進め方：講義では基礎概念と考え方について学ぶ．より深い理解と具体例に対する応用は演習問題を通じて行う． 授業計画： 1. アルゴリズム的問題解決と計算複雑性 2. 速習 P vs NP問題 3. 充足可能性問題とその変種 4. グラフに関する問題 (1)：部分集合の選択 5. グラフに関する問題 (2)：経路の選択 6. 集合族に関する問題 (1)：グラフとの関連 7. 集合族に関する問題 (2)：発展 8. まとめ１ 9. 数値が関わる問題 (1)：2分割問題 10. 数値が関わる問題 (2)：3分割問題 11. 平面性が関わる問題 12. 計算幾何学に関する問題 13. 文字列に関する問題 14. アルゴリズム的問題解決：再考 15. まとめ２ Plan: Basic concepts will be discussed in the class. Deeper understanding and applications will be complemented with homework and exercises. Schedule: 1. Algorithmic Problem Solving and Computational Complexity 2. Crash Course on the P vs NP Problem 3. Satisfiability Problem and Its Variants 4. Problems on Graphs (1): Selecting a Subset 5. Problems on Graphs (2): Selecting a Route 6. Problems on Set Systems (1): Relationship with Graphs 7. Problems on Set Systems (2): Advanced 8. Summary 1 9. Problems Related to Numbers (1): Partition 10. Problems Related to Numbers (2): 3-Partition 11. Problems with Planarity 12. Problems on Computational Geometry 13. Problems on Strings 14. Algorithmic Problem Solving Revisited 15. Summary 2 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等）（1,000文字以内） /Preparation and review outside class（up to 1,000 letters） |
演習問題に取り組む． Solving exercises |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法： 数回のレポートによって評価を行う． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること．出題される演習問題の半分程度を解くことができる能力を最低達成基準とする． Evaluation: Report submissions Evaluation criteria: Understanding of basic concepts, 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） |
メールにて相談． Appointment by email |
| 学生へのメッセージ（1,000文字以内） /Message for students（up to 1,000 letters） |
これは計算複雑性理論の講義ではありません．これは，計算複雑性の視点がどのように役立つのか，ということを学ぶものです．困ることは，この視点に関する良書が存在しないか，あるいは絶版になっていることです．しかし，最適化やアルゴリズムの専門家は日常的にこの視点を用いています．それを学ぶことのできるよい機会だと捉えて下さい． |
| その他 /Others |
他専攻，他研究科の学生も歓迎します． Students from other departments are welcome to join. |
| キーワード /Keywords |
NP完全性，帰着 (還元)，ガジェット，充足可能性問題，グラフ，集合族 NP-completeness, reduction, gadget, satisfiability, graph, set system |