前期 火曜日 ５講時 川北キャンパスＡ１０４. 単位数/Credit(s): 2. 担当教員(所属)/Instructor (Position): 静谷 啓樹 所属：教養教育院. 対象学部/Object: 全. 開講期/Term: 1/3/5/7セメスター. 科目群/Categories: 全学教育科目先進科目-カレント・トピックス科目. 履修年度: 2024. 科目ナンバリング/Course Numbering: ZAE-OAR803J. 使用言語/Language Used in Course: 日本語.
各学部の履修内規または学生便覧を参照。
入門：計算量理論
An Introduction to Computational Complexity Theory
情報技術が社会に広く深く織り込まれた現在、その基盤となる科学を理解した上で技術と向き合うことこそが、文系理系を問わず技術に流されない自分を確立する第一歩になる。この講義では、情報の基礎理論の一つである計算量理論について、一貫して数学的な議論により、その入門的事項を学ぶ。特に、問題の難しさの分類と、帰着により難しさを順序付ける方法の理解を目指す。
The first step not to lose ourselves in today's advanced information society is to understand
the science underling the technology. In this introductory class, we will learn basics of
Computational Complexity Theory which is a part of the mathematical and fundamental theory of information.
Specifically we will understand that each problem belongs to some class of
difficulty and that difficulty can be ordered by some reducibility.
・問題間の関係性を帰着可能性という概念を使って説明できるようになること。
・問題を解く難しさを、計算量のクラスという概念を使って説明できるようになること。
Students will be able to explain i) the relationship among problems by
the notion of reducibility, and ii) the difficulty to solve a problem by
the notion of computational complexity classes.
1.オリエンテーション
講義の内容と意義に関する概要説明
2.問題の難しさと社会
難しくて困る例、難しくないと困る例
3.問題の難しさの標準化(1)
抽象概念としての計算機の導入
4.問題の難しさの標準化(2)
難易の境界としての多項式の重要性
5.問題の難しさのクラス(1)
解くのが易しい問題、正解の確認が易しい問題
6.問題の難しさのクラス(2)
できる人に助けてもらうと解ける問題
7.問題の難しさのクラス(3)
限られた計算用紙を使って解ける問題
8.問題の難しさのクラス(4)
乱数を使うとだいたい解決する問題
9.帰着可能性(1)
問題の難しさの順序付けと問題間の関係性
10.帰着可能性(2)
できる人からの助言の威力は会話か書面かで違う
11.具体例(1)
簡単に計算できるけど、もとに戻し難い写像
12.具体例(2)
同じものか、部分的に同じものかの違い
13.具体例(3)
対話によってだいたい解決する問題
14.具体例(4)
計算量のクラスは生活の一部
15.まとめ、授業評価
最終質疑、期末レポートの説明
1.Orientation
Class overview.
2.Society and computational difficulty
If it's hard, it's hard. If it's not hard,it's not good.
3.Standardizing the computational difficulty I
Introducing an abstract computing machine.
4.Standardizing the computational difficulty II
Significance of polynomials as the boundary of difficulty.
5.Class of difficulty I
Problem easy to solve and problem easy to verify a solution.
6.Class of difficulty II
Problems that can be solved if some person of specific capability helps.
7.Class of difficulty III
Problems that can be solved even if memo pad is restricted.
8.Class of difficulty IV
Problems that can be almost solved if randomization is used.
9.Reducibility I
Ordering the difficulty of problems and the relationship among problems.
10.Reducibility II
Power of help by interactive communication is different from non-interactive one.
11.Example I
Maps easy to compute but hard to invert.
12.Example II
Difference between equivalence and partial equivalence.
13.Example III
Problems that can be almost resolved via conversation.
14.Example IV
Complexity classes are part of our life.
15.Concluding remarks and class evaluation
Last minute discussion. Explanation of the term paper.
課題レポート(30%)と期末レポート(70%)により評価される。
出欠情報は取られない(成績評価に使われない)。
Homework 30%. Term paper 70%.
Attendance in class is not considered in grading.
LMSとして Google Classroom を使用する.
We use Google Classroom as our LMS.
各授業のスライドのファイルをダウンロードできるので、それを復習することが奨励される。
Students are encouraged to review class slides which are available for download after class.
必要
Yes
・教科書や参考書は指定されないが、講義の資料は Google Classroomを通して入手することができる.
・オフィスアワーは設けられていない. 質問はメールで受け付けられる.
- Textbooks and reference books are not specified. Relevant materials can be downloaded at Google Classroom.
- No office hour is specified. Queries are accepted via email.