シラバス参照
シラバス参照
| 授業科目名 /Course title (Japanese) |
離散最適化基礎論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Foundation of Discrete Optimization | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2026年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 曜限 /Day, Period |
火／Tue 2 | ||
| 科目区分 /Category |
大学院専門教育科目 - 専門科目Ⅰ | ||
| 開講類・専攻 /Cluster/Department |
情報・ネットワーク工学専攻 | ||
| 担当教員名 /Lecturer(s) |
岡本 吉央 | ||
| 居室 /Office |
西4-206 (West-4 Bldg, Room 206) | ||
| 公開E-mail |
okamotoy followed by @uec.ac.jp | ||
| 授業関連Webページ /Course website |
http://dopal.cs.uec.ac.jp/okamotoy/lect/2026/expander/ | ||
| 更新日 /Last update |
2026/03/30 12:06:02 | 更新状況 /Update status |
公開中 /now open to public |
| 主題および達成目標 （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 academic year is "Expanders." Expanders are important combinatorial objects in discrete mathematics and theoretical computer science, but their existence and construction are not fully understood. The learning objective is to understand the concepts and methods, and to apply them to examples. |
|---|---|
| 前もって履修 しておくべき科目 （1,000文字以内） /Prerequisites （up to 1,000 letters） |
離散数学，線形代数学，アルゴリズム論第一 (特に，オーダー記法) Discrete Mathematics，Linear Algebra, Algorithms I (the Big-O notation) |
| 前もって履修しておくこ とが望ましい科目 （1,000文字以内） /Recommended prerequisites and preparation （up to 1,000 letters） |
アルゴリズム論第二，グラフとネットワーク，確率論 (特に，離散確率) Algorithms II, Graphs and Networks, Probability (Discrete probability) |
| 教科書等 （1,000文字以内） /Course textbooks and materials （up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書： M. Krebs, A. Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide. Oxford University Press, 2011. F.R.K. Chung, Spectral Graph Theory, AMS, 1997. C. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001. B. Nica, A Brief Introduction to Spectral Graph Theory, 2018. T. Checherini-Silberstein, F. Scarabotti, F. Tolli, Discerete Harmonic Analysis, Cambridge University Press, 2018. その他の参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books: M. Krebs, A. Shaheen, Expander Families and Cayley Graphs: A Beginner's Guide. Oxford University Press, 2011. F.R.K. Chung, Spectral Graph Theory, AMS, 1997. C. Godsil, G. Royle, Algebraic Graph Theory, Springer, 2001. B. Nica, A Brief Introduction to Spectral Graph Theory, 2018. T. Checherini-Silberstein, F. Scarabotti, F. Tolli, Discerete Harmonic Analysis, Cambridge University Press, 2018. G. Davidoff, P. Sarnak, A. Valette, Elementary Number Theory, Group Theory, and Ramanujan Graphs. Cambridge University Press, 2003. The related materials will be referred to in the class. |
| 授業内容とその進め方 （2,000文字以内） /Course outline and weekly schedule （up to 2,000 letters） |
英語タイプ：Cc (日本語で説明し，日本語の教材・資料を使う) 授業計画： 1. グラフ理論速習 2. グラフのスペクトル 3. グラフの等周定数とエクスパンダ 4. グラフの等周定数と直径 5. グラフの等周定数とランダムウォーク 6. Cheegerの不等式 7. 前半のまとめ 8. Alon-Boppanaの定理：第1の証明 9. Alon-Boppanaの定理：第2の証明 10. ジグザグ積：定義 11. ジグザグ積：証明 12. エクスパンダの構成 13. リフト：定義 14. リフト：性質の紹介 15. 後半のまとめ 進め方： 教室で講義を行うが，リアルタイムでZoom中継も行う．録画した講義を後で見直せるようにする．「LMSコース情報」に記載されているGoogle Classroomに参加すること． English Type: Cc (delivered in Japanese, materials prepared in Japanese) Plan: 1. Recap of basic graph theory 2. Graph spectra 3. Isoperimetric constants and expanders 4. Isoperimetric constants and diameters 5. Isoperimetric constants and random walks 6. Cheeger's inequality 7. Summary of the first half 8. Alon-Boppana's theorem: the first proof 9. Alon-Boppana's theorem: the second proof 10. Zig-zag products: definition 11. Zig-zag products: proofs 12. Construction of expanders 13. Lifts: definition 14. Lifts: properties 15. Summary of the second half Format: Lectures will be delivered at a lecture room, but at the same time broadcast via Zoom. Lecture videos will be made public. Students are supposed to join Google Classroom described in the ”LMS course info" section. |
| 対面授業・遠隔授業の別 /Face-to-face or online lecture |
対面授業 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） （1,000文字以内） /Preparation and review outside class （up to 1,000 letters） |
講義動画を用いて復習を行う Recap by lecture videos |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
成績評価方法：毎回のクイズと2回のレポートによって評価を行う． 評価基準： 基本的な概念を理解し，解析手法と例に対する応用ができること． Evaluation: Quizzes at lectures and two reports Evaluation criteria: Understanding of basic concepts, and ability of application of methods to examples |
| オフィスアワー：授業相談 （1,000文字以内） /Office hours （up to 1,000 letters） |
メールにて相談． Appointment by email |
| 学生へのメッセージ （1,000文字以内） /Message for students （up to 1,000 letters） |
毎年異なる内容の授業を行っていますが，今年度はかなりグラフ理論に寄った内容になり，あまり離散最適化っぽくはないかもしれません．そうであっても，エクスパンダは重要な概念であり，これを通して離散数学の様々な方法論を学ぶこともできる題材です．その味わいを楽しんでください． The content of this course changes every year. For this academic year, the focus will be mostly on graph theory, so it might not feel like a typical discrete optimization class. Even so, expanders are a very important concept. By studying them, you can learn many different methods used in discrete mathematics. I hope you enjoy discovering the unique "flavor" of this subject. |
| その他 /Others |
他専攻，他研究科の学生も歓迎する． Students from other departments are welcome to join. |
| キーワード /Keywords |
グラフ，固有値，固有ベクトル，エクスパンダ，等周定数，直径，ランダムウォーク，混交，レイリー商，ジグザグ積，リフト，ラマヌジャン・グラフ Graphs, eigenvalues, eigenvectors, expanders, isoperimetric constants, diameters, random walks, mixing, Rayleigh quotient, zig-zag products, lifts, Ramanujan graphs |