| １． |
Outline |
|
This course aims at learning the theory of automata and formal languages, then also aims at learning the theory of computation, including the computation complexity theory and the computability theory.
In particular, this course aims at learning the following topics;
The equivalency between the deterministic, non-deterministic finite automata and the regular grammar/expression, and these properties;
The non-equivalency between the deterministic and non-deterministic pushdown automata;
The equivalency between the non-deterministic pushdown automaton and the comma-free grammar and these properties;
The equivalency between the deterministic and non-deterministic Turing machines, the universality and the bound of these automata;
The equivalency between the Turing machines and the family of sets of logical circuits;
The definition and the evaluation of computational complexity;
The relation of P vs. NP, NP complete-problems and NP hard problems;
This course relates to the diploma policy DP2.
|
| ２． |
Objectives |
|
Recently, computers get to win each world champion of Chess, Japanese Chess or the game of Go.
It has been common to use computers to solve problems which seem insolvable to human beings, by using huge data called the Big-data,
and it has been common to use the artificial intelligence(AI) in our daily life.
Then, can computers solve all the problems which we give computers ?
To use computers effectively, we should learn the ability and the bounds of computers.
Thus, this course deals with the meaning of computation, the bounds of computation theoretically.
|
| １． |
Outline |
|
This course aims at learning the theory of automata and formal languages, then also aims at learning the theory of computation, including the computation complexity theory and the computability theory.
In particular, this course aims at learning the following topics;
The equivalency between the deterministic, non-deterministic finite automata and the regular grammar/expression, and these properties;
The non-equivalency between the deterministic and non-deterministic pushdown automata;
The equivalency between the non-deterministic pushdown automaton and the comma-free grammar and these properties;
The equivalency between the deterministic and non-deterministic Turing machines, the universality and the bound of these automata;
The equivalency between the Turing machines and the family of sets of logical circuits;
The definition and the evaluation of computational complexity;
The relation of P vs. NP, NP complete-problems and NP hard problems;
This course relates to the diploma policy DP2.
|
| ２． |
Objectives |
|
Recently, computers get to win each world champion of Chess, Japanese Chess or the game of Go.
It has been common to use computers to solve problems which seem insolvable to human beings, by using huge data called the Big-data,
and it has been common to use the artificial intelligence(AI) in our daily life.
Then, can computers solve all the problems which we give computers ?
To use computers effectively, we should learn the ability and the bounds of computers.
Thus, this course deals with the meaning of computation, the bounds of computation theoretically.
|
| ３． |
Grading Policy |
|
2つのレポート課題の合格を前提に、科目修得試験において60%以上をの評価点を得たものを合格とします。レポート課題に関しては、返却時にフィードバックを記述します。レポート課題及び科目修得試験の学習について質問がある場合は原則的にLMSを通して対応します。
|
| ４． |
Textbook and Reference |
|
テキスト：丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045
使用教材：LMS
|
| ５． |
Requirements (Assignments) |
|
各講義前に昨年度または今年度の講義ノート及び関連する資料等をLMS上に掲載します。これらの資料を利用して予習をしてください。また、原則として各講義に対する演習問題をLMSのテストとして公開します。このテストは評価の対象ではありませんが、復習に利用してください。
予習と復習を合わせて、当該期間中に30時間以上の学習が必要です。
|
| ６． |
Note |
|
関連して履修すべき科目は、論理数学、グラフ理論、データ構造とアルゴリズム、計算理論1、計算理論2です。
|
| ７． |
Schedule |
|
１.
すべては計算から始まる |
２.
計算の理論のための概念や用語 |
３.
有限オートマトン
決定性有限オートマトン |
４.
非決定性有限オートマトン
決定性有限オートマトンと非決定性有限オートマトンの等価性 |
５.
正規表現 |
６.
正規言語/文脈自由言語 |
７.
文脈自由文法 |
８.
プッシュダウンオートマトン1 -プッシュダウンオートマトンの定義- |
９.
プッシュダウンオートマトン2 -プッシュダウンオートマトンと文脈自由文法の等価性- |
10.
Turingマシン1 -Turingマシンの定義とその拡張- |
11.
Turingマシン2 -非決定性Turingマシン- |
12.
Turingマシンの万能性とその限界 |
13.
Turingマシンに基づいた計算量限定の計算 |
14.
論理回路に基づいた計算量限定の計算 |
15.
まとめ |
|
|