アルゴリズム特論

Advanced Algorithm

996D601

63CSALC601

入山　聖史、田畑　耕治

Satoshi Iriyama

2024年度後期

水曜3限

3rd, Wednesday

創域理工学研究科　情報計算科学専攻

Department of Information Sciences, Graduate School of Science and Technology

2.0単位

講義

Lecture

-

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

計算の理論と，それにおける数理について深い理解を目指す．アルゴリズムの定義や言語クラスについての知識，定理の証明方法などを学ぶ．

Mathematical foundations and advanced lecture of computational theory are given for deep understanding. You will learn definition of algorithm, language classes and how to construct proof for problems in computational theory.

本学科のディプロマポリシー・カリキュラムポリシー「情報を数量化し科学的に分析する力を身につけることができる．情報科学科の学問分野における基礎的知識や原理を体系的に身に付けることができる．」に該当する科目である．

You will integrate the knowledge that you have learned so far, and conduct research on various problems related to information theory.
Discuss and make presentations and acquire the ability of presentation.
To acquire the ability to think, logically and critically think based on sophisticated expertise research ability and culture and find, set and resolve tasks themselves in the diploma policy of this department Subject.

1. アルゴリズムを数理的に深く理解し，問題を効果的に解くアルゴリズムを構成できるようになる．
2. 様々な言語クラスについてそれぞれの関係を理解し，問題を分類できるようになる．
3. アルゴリズムについての先進的な研究を理解し，具体例を上げて説明できるようになる．

1. You understand mathematical foundations of algorithm, and construct effective algorithm
2. You understand relations among several language classes, and classify problems
3. You study on advanced topics on algorithm, and show concrete examples for description

リンク先の [評価項目と科目の対応一覧]から確認できます（学部対象）。
履修登録の際に参照ください。
​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/​​​

計算の理論の基礎的な知識があることが望ましい．

Basic knowledge on computational theory is expected

-

-

授業準備と復習を合わせて週4時間を目安とする．
準備：授業内容について図書や論文を検索し，概要をまとめておく
復習：授業内容の行間を埋め，疑問点を解消する

Preparation and review are required total 4 hours per week.
Preparation: Study each seminar field and examining articles in advance.
Review: Write carefully topics and proofs and clarify questions

レポートで評価する．

Reports

・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/

M.Sipser, 計算理論の基礎, 共立出版
ISBN-10: 4320029488
ISBN-13: 978-4320029484

第１回：序論，アルゴリズムの歴史を解説し，数学的準備を行う．
第２回：オートマトン(1)，決定性有限オートマトンの定義と例を説明する．
第３回：オートマトン(2)，非決定性有限オートマトンの定義と例を説明する．
第４回：チューリング機械(1)，決定性チューリング機械の定義と例を説明する．
第５回：チューリング機械(2)，様々なチューリング機械について定義と例を説明する．
第６回：アルゴリズムの定義とChurch-Turingの提唱，アルゴリズムの定義を説明し，様々なモデルとの等価性について説明する．
第７回：判定可能性，判定可能性と，停止問題について説明する．
第８回：帰着可能性，計算理論における帰着可能性について説明する．
第９回：計算の複雑さ(1)，言語クラスの定義と用語を説明する．
第１０回：計算の複雑さ(2)，NP完全性の定義とNP完全問題について説明する．
第１１回：計算の複雑さ(3)，領域の複雑さについて説明する．
第１２回：アルゴリズムの先進的話題(1)，計算理論における先進的なテーマについて議論する．
第１３回：アルゴリズムの先進的話題(2)，計算理論における先進的なテーマについて議論する．
第１４回：アルゴリズムの先進的話題(3)，計算理論における先進的なテーマについて議論する．
第１５回：まとめ

1. Introduction
2. Automaton(1), definitions and examples
3. Automaton(2), Non-deterministic automaton
4. Turing Machine(1), Deterministic Turing Machine
5. Turing Machine(2), Several modifications
6. Algorithm and CT-Thesis, definitions of algorithm and equivalency
7. Decidable Problems, definition and halting problem
8. Recursibility, how to reduce problems into others
9. Computational Complexity(1), definition of language class
10. Computational; Complexity(2), NP problems and completeness
11. Computational; Complexity(3), space difficulty
12. Advanced topic(1)
13. Advanced topic(2)
14. Advanced topic(3)
15. Summary

-

-

-

N

N