シラバス参照
シラバス参照
| 授業科目名 /Course title (Japanese) |
理論計算機科学特論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Advanced Study for Theoretical Computer Science | ||
| 科目番号 /Code |
|||
| 開講年度 /Academic year |
2026年度 | 開講年次 /Year offered |
全学年 |
| 開講学期 /Semester(s) offered |
前学期 | 開講コース・課程 /Faculty offering the course |
博士前期課程、博士後期課程 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 曜限 /Day, Period |
火／Tue 1 | ||
| 科目区分 /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/tcs/ | ||
| 更新日 /Last update |
2026/04/08 14:58:08 | 更新状況 /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 theoretical computer science. The topic of this academic year is "Basic Computational Complexity Theory." Emphasis is placed on the fundamental facts and methods essential for specialists in informatics, computation, communication, and networks. The learning goal is for students to master the application of complexity-theoretic perspectives within their research and daily lives. |
|---|---|
| 前もって履修 しておくべき科目 （1,000文字以内） /Prerequisites （up to 1,000 letters） |
離散数学，アルゴリズム論第一 (特に，オーダー記法)，確率論（特に，離散確率） Discrete Mathematics, Algorithms I (the Big-O notation), Probability Theory (Discrete Probability) |
| 前もって履修しておくこ とが望ましい科目 （1,000文字以内） /Recommended prerequisites and preparation （up to 1,000 letters） |
計算理論，形式言語理論，アルゴリズム論第二 Theory of Computation, Formal Language Theory, Algorithms II |
| 教科書等 （1,000文字以内） /Course textbooks and materials （up to 1,000 letters） |
教科書： なし．講義資料を毎回用意するので，講義webページより各自入手すること． 参考書： M. Sipser, Introduction to the Theory of Computation, 3rd Edition. Course Technology Ptr., 2012. (邦訳あり) S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009. 荻原光徳，複雑さの階層，共立出版，2006． その他の参考文献は講義中に挙げる． Textbook: None. The course materials will be provided through the course webpage. Supplementary Books: M. Sipser, Introduction to the Theory of Computation, 3rd Edition. Course Technology Ptr., 2012. S. Arora, B. Barak, Computational Complexity: A Modern Approach. Cambridge University Press, 2009. 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. 時間計算量：P, NP, coNP 3. 帰着と完全性：NP完全 4. 領域計算量：L，NL，PSPACE, NPSPACE 5. 時間と領域の関係：P⊆PSPACE⊆EXPTIME 6. 階層定理：P≠EXPTIME 7. Ladnerの定理：P≠NP => NP-P≠NPC 8. Savitchの定理：PSPACE=NPSPACE 9. Immerman-Szelepcsényiの定理：NL=coNL 10. 多項式階層：P=NP => P=PH 11. 交代性計算：AP=PSPACE 12. 確率的計算：BPP⊆PP, NP⊆PP 13. 対話証明系 (1)：MA，AM，NP⊆MA⊆AM 14. 対話証明系 (2)：IP⊆PSPACE 15. 対話証明系 (3)：PSPACE⊆IP 進め方： 教室で講義を行うが，リアルタイムでZoom中継も行う．録画した講義を後で見直せるようにする．「LMSコース情報」に記載されているGoogle Classroomに参加すること． English Type: Cc (delivered in Japanese, materials prepared in Japanese) Plan: 1. Recap of theory of computation 2. Time complexity: P, NP, coNP 3. Reductions and completeness: NP-complete 4. Space complexity: L, NL, PSPACE, NPSPACE 5. Relation between time and space: PSPACE⊆EXPTIME 6. Hierarchy theorem: P≠EXPTIME 7. Ladner's theorem: P≠NP => NP-P≠NPC 8. Savitch's theorem: PSPACE=NPSPACE 9. Immerman-Szelepcsényi theorem: NL=coNL 10. Polynomial hierarchy: P=NP => P=PH 11. Alternation: AP=PSPACE 12. Probabilistic complexity classes: BPP⊆PP, NP⊆PP 13. Interactive proofs (1)：MA，AM，NP⊆MA⊆AM 14. Interactive proofs (2)：IP⊆PSPACE 15. Interactive proofs (3)：PSPACE⊆IP 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: In-class quizzes 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） |
情報系の専門家と呼ばれる人が，計算複雑性の理論をほとんど理解していないのに，それに関することを論文などに間違ったまま書き，その誤解が流布される，という悪循環が発生しています．電気通信大学の卒業生にはそのような人材になってほしくありません．この授業を通して，計算複雑性について，少なくとも基礎的な事項は正しく理解できるようになってほしいと思っています． There is a cycle where some people write about computational complexity in their papers without quite getting the basics right, and these mistakes then spread to others. I don't want graduates from the University of Electro-Communications to be in that position. Through this class, I want to help you learn the basic points accurately. My hope is that you will finish this course with a good foundation, so you can use these ideas correctly in your own research and work. |
| その他 /Others |
他専攻，他研究科の学生も歓迎する． Students from other departments are welcome to join. |
| キーワード /Keywords |
計算複雑性，アルゴリズム，時間計算量，領域計算量，計算複雑性クラス，帰着，完全性，困難性，充足可能性問題，証拠，対角線論法，階層定理，決定性計算，非決定性計算，交代性計算，確率的計算，対話証明，算術化 Computational complexity, algorithms, time complexity, space complexity, complexity classes, reductions, completeness, hardness, satisfiability problem, certificate, diagonalization, hierarchy theorem, deterministic computation, non-deterministic computation, alternating computation, probabilistic computation, interactive proofs, arithmetization |