計算理論（社会情報・専門科目）

授業科目名

計算理論（社会情報・専門科目）

(英語名)

Theory of Computation （社会情報・専門科目）

科目区分

専門教育科目

−

対象学生

社会情報科学部

学年

3年

ﾅﾝﾊﾞﾘﾝｸﾞｺｰﾄﾞ

KCJBS3MCA1

単位数

2単位

ナンバリングコードは授業科目を管理する部局、学科、教養専門の別を表します。詳細は右上の？から別途マニュアルをダウンロードしてご確認ください。

授業の形態

講義 (Lecture)

開講時期

2024年度後期

担当教員

玉置卓

所属

社会情報科学部

授業での使用言語

日本語

講義目的

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

到達目標

・基礎概念を理解し説明できる
・理論的、数学的な話題に対して厳密な理解や説明ができる

授業のサブタイトル・キーワード

講義内容・授業計画

講義内容

最初に、最も単純な計算モデルの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. 期末試験

※生成系AI の取扱いについて
レポート，小論文，学位論文等については、学生本人が作成することを前提としているため、生成系AIのみを用いて作成することはできません。

教科書

資料を配布する

参考文献

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

事前・事後学習（予習・復習）の内容・時間の目安

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

アクティブ・ラーニングの内容

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

成績評価の基準・方法

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

課題・試験結果の開示方法

講評や解説を行う

履修上の注意・履修要件

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

実践的教育

該当しない

備考

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

英語版と日本語版との間に内容の相違が生じた場合は、日本語版を優先するものとします。

シラバス情報

講義目的

到達目標

講義内容

授業計画