| 授業の目的 【日本語】 | | | 数理的にモデル化された様々な問題を計算機で解くために必要な計算資源（計算時間やメモリ）の量を基準にして，問題の持つ複雑さ（計算複雑さ）を測るための理論（計算量理論）を学習する。問題の数学的定式化や計算機の数理モデル（計算モデル）を学んだ後，計算機における計算複雑さの測り方を具体例とともに理解する。そして，計算複雑さの尺度で考えたときに効率的に解ける問題がどういったものかを学び，そのような問題が持つ特徴や基本的性質を修得する。 |
|
|
| 授業の目的 【英語】 | | | In this course, students will learn computational complexity -- theory for measuring the complexity of a problem based on the amount of computational resources (time and memory) required to solve various mathematically modeled problems with a computer. After studying the mathematical formulation of the problem and the mathematical model of a computer (computation model), they will understand how to measure the computational complexity of a computer with concrete examples. Then, they will learn what kind of problems can be solved efficiently when they are considered in terms of computational complexity, and learn the characteristics and basic properties of such problems. |
|
|
| 到達目標 【日本語】 | | | 今日のコンピュータ科学を支える基礎理論である計算量理論について理解するために，最低限必要な事項について講義を実施する。この講義により計算量理論の基本事項を習得するとともに，計算量理論とその応用について学んでいくためのきっかけとする。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | 計算問題をコンピュータで解くための複雑さ（計算複雑さ）を測るための理論（計算量理論）を理解するための基礎事項を詳細に解説する。計算問題，計算モデル，計算量など計算とは何か，計算複雑さとは何かについての数学的定式化を行い，具体例を紹介する。さらに様々な（計算）問題の計算量を評価する方法や多項式時間計算可能性など計算量理論を展開するうえで必要不可欠な事項について説明を行う。
1. ガイダンス
2. 計算問題
3. 計算モデル
4. チャーチの提唱
5. 計算モデルの万能性
6. 計算量
7. 計算量の評価方法
8. 多項式時間計算可能性 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に与える課題の評価40％，期末試験60％，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | | 必要に応じて講義プリントを配布する。参考文献等は講義中に紹介する。履修条件は特にない。 | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|