Theory of Computation ｜ Syllabus data

Course Title

Theory of Computation

Course Title in English

Theory of Computation

Course Type

Major Courses

−

Eligible Students

School of Social Information Science

Target Grade

3Year

Course Numbering Code

KCJBS3MCA1

Credits

2.00Credits

The course numbering code represents the faculty managing the subject, the department of the target students, and the education category (liberal arts / specialized course). For detailed information, please download the separate manual from the upper right 'question mark'.

Type of Class

講義 (Lecture)

Eligible Year/Semester

Fall semester 2026

Instructor

玉置卓

Affiliation

社会情報科学部

Language of Instruction

Japanese

Related SDGs

9

Office Hours and Location

アポイントメントによる

Contact

tamak@sis.u-hyogo.ac.jp

Corresponding Diploma Policy

A double circle indicates the most relevant DP number and a circle indicates the associated DP.

Corresponding Undergraduate School DP

3◎／1〇

Corresponding Graduate School DP

ー

Corresponding University-Wide DP

N/a

Academic Goals of Teacher Training Course

ー

Course Objectives and Learning Outcome

講義目的

計算理論では「計算」を厳密に定義し、計算可能性や計算効率を調べる枠組みを提供する。
本講義では、計算理論の基本的な話題である「オートマトンと言語の理論」、「計算可能性の理論」、「計算複雑さの理論」に親しむ。
具体的には
1. 種々の計算モデル (有限オートマトン、チューリング機械)
2. 計算可能性
3. 効率の良い計算、P対NP問題
について基本的な知識を習得する。
これらの知識はアルゴリズムの設計と解析における重要な基礎である。

到達目標

・基礎概念を理解し練習問題を解くことができる
・理論的、数学的な話題を厳密に理解し説明ができる

Subtitle and Keywords of the Class

Course Overview and Schedule

講義内容

最初に、最も単純な計算モデルの1つである有限オートマトンを扱い、計算理論への導入を行う。
次に、最も強力な計算モデルであるTuring機械を扱い、計算可能性や計算複雑性における基本的な概念に触れる。
最後に、計算理論におけるいくつかの発展的な話題を紹介する。

授業計画

1. 計算理論への導入 (1)
2. 計算理論への導入 (2)
3. オートマトン (1)
4. オートマトン (2)
5. オートマトン (3)
6. Turing機械 (1)
7. Turing機械 (2)
8. 中間試験
9. 効率のよい計算
10. クラスNPとNP完全性 (1)
11. クラスNPとNP完全性 (2)
12. 発展的話題 (1) 乱択アルゴリズム
13. 発展的話題 (2) 計算理論に基づく暗号
14. 発展的話題 (3) 量子アルゴリズム
15. まとめ
16. 期末試験

In-person/Remote Classification

In-person

Implementation Method and Remote Credit Limit Application

・対面授業のみ
・遠隔授業単位上限の適用を受けない

Uses of Generative AI

Limited permission for use

Precautions for using Generative AI

生成AIの利用にあたっては『本学の教育における生成AIの取扱いについて(学生向け)』の記載内容について留意すること。生成AIの利用については担当教員の指示に従うこと。
教員が認める範囲を超えて生成AIを利用したことが判明した場合は、単位を認定しない、又は認定を取り消すことがある。生成AIの出力した内容について、事実関係の確認や出典・参考文献を確認・追記することが重要である。また、生成AIによる出力結果をそのまま課題・レポート・論文として提出してはならない。

Textbook

資料を配布する

References

Michael Sipser (著), 太田和夫, 田中圭介 (監訳)『計算理論の基礎 [原著第2版]』共立出版 (1〜3巻)

Contents and Estimated Time for Pre- and Post- Learning (Preparation and Review)

内容
宿題に取り組むとともに、理解不足、誤解があった箇所の復習を行う
時間の目安
4時間×15週

Contents of Active Learning

ミニッツペーパーにより理解度の把握を随時行う

Grading Criteria and Methods

基準
基礎概念を理解できていること
理論的、数学的な話題に対して厳密な理解や説明ができること
方法
中間試験と期末試験による。それぞれを60点満点とし
min｛100, 中間試験の素点+期末試験の素点｝
を成績とする

How to Disclose Assignments and Exam Results

講評や解説を行う

Precautions and Requirements for Course Registration

データ構造とアルゴリズム (もしくはそれらに相当する科目) を履修していること。

Practical Education

該当しない

Remarks

講義の進度により内容を変更することがある

In cases where any differences arise between the English version and the original Japanese version, the Japanese version shall prevail as the official authoritative version.