計算の理論１

Theory of Computation １

9961171

63INALC303

入山　聖史

Satoshi Iriyama

2024年度後期

Semester

月曜4限

Monday 4th

創域理工学部　数理科学科、情報計算科学科

Department of Mathematics, Faculty of Science and Technology
Department of Information Sciences, Faculty of Science and Technology

2.0単位

講義

Lecture

-

① [対面]対面授業/ [On-site] On-site class

計算の数学的定義、計算の複雑さ、Turing機械、言語クラス、Hilbertの第10問題など、計算の理論の基礎について学ぶ。

本学科のディプロマポリシー「情報科学科の学問分野における幅広い基礎的知識をもとに、情報科学に関わる分野における原理と応用を体系的に身に付けている」を実現するために、計算の理論における数学的基礎、計算量の求め方、効果的なアルゴリズムの構成法、言語の取り扱いの基礎を身につける。

１　計算モデルの定義を説明できるようになる。
２　Church-Turingの提唱について説明できるようになる。
３　帰納的関数について説明できるようになる。
４　様々な言語クラスの定義を説明できるようになる。
５　効果的なアルゴリズムとは何かを理解する

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​You can check this from “Correspondence table between grading items and subjects” by following the link(for departments).
https://www.tus.ac.jp/fd/ict_tusrubric/​​​

情報数学１Ａ及び演習，情報数学１Ｂ及び演習の内容を理解していることが望ましい．

-

-

授業準備と復習を合わせて週4時間を目安とします
準備学習：毎回，講義の参考書を事前に調べて講義の学習の準備をして下さい．
1. ソートのアルゴリズムについて調べる
2. 有限オートマトンの定義を調べる
3. ディオファントス方程式について調べる
4. Church-Turingの提唱について調べる
5. 正規言語の再帰的定義を調べる
6. Cantorの対角線論法について調べる
7. アルゴリズムの計算時間での評価法について調べる
8. Karatsuba法について調べる
9. SAT問題とBoole代数について調べる
10. クイックソートについて調べる
11. RSA暗号の秘密鍵生成法について調べる
12. Carmichael数について調べる
13. クラスIPについて調べる
14. 秘密鍵分配について調べる
15. 定義の復習

復習：講義の内容が理解できているか，毎回復習して下さい．
1. Eucridアルゴリズムについて具体例を用いて復習する
2. 和算，積算を行う有限オートマトンを構成する
3. チューリング機械の定義を復習する
4. 多テープチューリング機械，万能チューリング機械のシミュレート方法を復習する
5. 正規言語，文脈自由言語，判定可能言語の包含関係を示す
6. 停止問題の証明を復習する
7. 定義を復習し，時間計算量の表記について具体例を示す
8. 有向グラフ問題のアルゴリズムについて，計算時間の異なるものを構成する
9. NP問題とNP完全問題の定義を復習し，多項式時間帰着可能性について整理する
10. 確率的チューリング機械の認識，受理について復習する
11. Fermatの小定理を復習し，具体例を示す
12. Miller-Rabinのアルゴリズムを復習し，素数判定がクラスBPPに属することを示す
13. 対話型証明のもつ2つの性質，アルゴリズムとメッセージ系列を復習する
14. メッセージ系列の偽造可能性とゼロ知識証明の関係を整理して復習する
15. これまでの復習

試験(中間および期末)によって評価する．

・S：到達目標を十分に達成し、極めて優秀な成果を収めている
・A：到達目標を十分に達成している
・B：到達目標を達成している
・C：到達目標を最低限達成している
・D：到達目標を達成していない
・-：学修成果の評価を判断する要件を欠格している

・S：Achieved outcomes, excellent result
・A：Achieved outcomes, good result
・B：Achieved outcomes
・C：Minimally achieved outcomes
・D：Did not achieve outcomes
・-：Failed to meet even the minimal requirements for evaluation

N

-

教科書および一部の参考書は、MyKiTS (教科書販売サイト) から検索・購入可能です。
​https://mirai.kinokuniya.co.jp/tokyorika/​​​

It is possible to search for and purchase textbooks and certain reference materials at MyKiTS (online textbook store).
​​https://mirai.kinokuniya.co.jp/tokyorika/

1. 予備概念
アルゴリズムの歴史的背景，記法，形式的体系について
2. 計算のモデル(1)
有限オートマトン，プッシュダウンオートマトンの形式的定義と実例
3. 計算のモデル(2)
Hilbertの第10問題とチューリング機械の定式化
4. 計算のモデル(3)
チューリング機械の類型と万能チューリング機械
5. 判定可能性
アルゴリズムにより判定可能な言語と諸定理
6. 停止問題
判定不可能な言語と対角線論法を用いた証明
7. 計算の複雑さ(1)
時間計算量のクラスと計算時間の表現方法
8. 計算の複雑さ(2)
多項式時間アルゴリズムとクラスP
9. 計算の複雑さ(3)
非決定性多項式時間アルゴリズムと検証装置，クラスNPと完全性
10. 確率的アルゴリズム(1)
確率的チューリング機械，受理条件，クラスBPP
11. 確率的アルゴリズム(2)
素数判定問題，Fermatの小定理
12. 確率的アルゴリズム(3)
Miller-Rabinのアルゴリズムと中国人剰余定理
13. 対話型証明(1)
対話型証明とグラフ非同型問題
14. 対話型証明(2)
グラフ同型問題とゼロ知識証明
15. まとめ

-

-

-

なし．

N

N