| １． |
Outline |
|
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.
In this course, students learn the meaning of computations by computers, and whether computations by computers have any bounds or not.
To deal with computations by computer mathematically, we model a computer itself in simple forms, which are computational models or automata. Given input data and a program, it become possible for a computer to compute the program, thus, we also model input data and programs in simple forms, which are called languages in this field. A language is a set of a series of symbols which obey a rule. The rule is called a grammar. It is known that an automaton corresponds to a grammar and the pair of a automaton and a grammar makes a hierarchical structure.
For each pair of an automata and a grammar, we will show its equivalency or non-equivalency by showing that a grammar can generate a language or not, where the language is accepted by an automata. In addition, as for an automaton called Turing machine which belongs to the hight class of the hierarchy, we will show that there are problems which cannot be solved essentially by computer by showing its universality and bound.
Moreover, by using the concept of complexity and Turing machines, we learn that problems dealt in the computer science can be classified into computational ones and non-computational ones. We also deals the relationship between computational ones and non-computational ones and these structures.
Students acquire skills related to the diplomatic policy 2 of Department of Information Science Correspondence Course.
<Comments>
Recently, computers get to win each world champion in 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.
In this course, students learn the meaning of computations by computers, and whether computations by computers have any bounds or not. To deal with computations by computer mathematically, we model a computer itself in simple forms, which are computational models or automata. Given input data and a program, it becomes possible for a computer to compute the program, thus, we also model input data and programs in simple forms, which are called languages in this field. A language is a set of a series of symbols which obey a rule. The rule is called a grammar. It is known that an automaton corresponds to a grammar and the pair of a automaton and a grammar makes a hierarchical structure.
For each pair of an automata and a grammar, we will show its equivalency or non-equivalency by showing whether a grammar can generate a language, where the language is accepted by an automata. In addition, as for an automaton called Turing machine, which belongs to the highest class of the hierarchy, we will show that there are problems which cannot be solved essentially by computer by showing its universality and bound.
Moreover, by using the concept of complexity and Turing machines, we learn that problems dealt in the computer science can be classified into computational ones and non-computational ones. We also deals the relationship between computational ones and non-computational ones and these structures.
Students acquire skills related to the diplomatic policy 2 of Department of Information Science Correspondence Course.
|
| ２． |
Objectives |
|
The goal of this class is that students master the following abilities;
Students can trace actions of a simple automata giving an input series of symbols and state transition functions of the automata.
Students understand the equivalency between deterministic and (generalized) nondeterministic finite automaton and regular expressions or regular grammar, and can utilize transform algorithm for each of them.
Students can express the features of regular languages as algebraic systems.
Students understand the meaning of the Chomsky normal form and given an arbitral context-free grammar, students can transform it to the corresponding Chomsky normal form.
Students can explain the Chomsky Hierarchy.
Students can explain the non-equivalency between deterministic pushdown automata and nondeterministic pushdown automata.
Students can explain the equivalency between pushdown automaton and context-free grammar and can utilize algorithms which translate one to another.
Students can explain the equivalency of deterministic Turing machines, nondeterministic Turing machines, other variations of Turing machines and logical circuits, the universality and the bound of Turing machines.
Students understand the concept of computational complexity and can express the complexity of each problem, algorithm with Big-O notation.
Students can explain the computational complexity and the relation of P, NP, NP complete and NP hard as classes of complexity, and can express the definition of NP.
<Comments>
The goal of this class is that students master the following abilities;
Students can trace actions of a simple automata giving an input series of symbols and state transition functions of the automata.
Students understand the equivalency between deterministic and (generalized) nondeterministic finite automaton and regular expressions or regular grammar, and can utilize transform algorithm for each of them.
Students can express the features of regular languages as algebraic systems.
Students understand the meaning of the Chomsky normal form and given an arbitral context-free grammar, students can transform it to the corresponding Chomsky normal form.
Students can explain the Chomsky Hierarchy.
Students can explain the non-equivalency between deterministic pushdown automata and nondeterministic pushdown automata.
Students can explain the equivalency between pushdown automaton and context-free grammar and can utilize algorithms which translate one to another.
Students can explain the equivalence of deterministic Turing machines, nondeterministic Turing machines, other variations of Turing machines and logical circuits, the universality and the bound of Turing machines.
Students understand the concept of computational complexity and can express the complexity of each problem, algorithm with Big-O notation.
Students can explain the computational complexity and the relation of P, NP, NP complete and NP hard as classes of complexity, and can express the definition of NP.
|
| ３． |
Grading Policy |
|
Grading policy:
Examination(100%).
The way of feedback;
Answers for questions or feedback for the contents of classes and examination will be given in a class, through LMS.
2つのレポート課題の合格を前提に、科目修得試験において60%以上をの評価点を得たものを合格とします。レポート課題に関しては、返却時にフィードバックを記述します。レポート課題及び科目修得試験の学習について質問がある場合は原則的にLMSを通して対応します。
<Comments>
Grading policy:
Examination(100%).
The way of feedback;
Answers for questions or feedback for the contents of classes and examination will be given in a class, through LMS.
|
| ４． |
Textbook and Reference |
|
Textbook: 丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045
Teaching materials: Published through LMS.
<Comments>
訂正無し
|
| ５． |
Requirements (Assignments) |
|
Teaching materials of this or last years will be published through LMS. In addition, small quizzes for each class will be published through LMS. Though quizzes are not used for grading. students should utilize to review each class. Students will be required to learn over 30 hours, which includes preparation and revision.
<Comments>
Teaching materials of this or last years will be published through LMS. In addition, small quizzes for each class will be published through LMS. Although, quizzes are not used for grading, students should utilize to review each class. Students will be required to learn over 30 hours, which includes preparation and revision.
|
| ６． |
Note |
|
In order to earn credits of this course, students must submit two reports and get 60% points for each report before taking an examination.
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits and Graph Theory.
At the same semester with this course, students should take Data Structure and Algorithms.
After taking this source, students should take Information Security.
関連して履修すべき科目は、論理数学、グラフ理論、データ構造とアルゴリズム、計算理論1、計算理論2です。
<Comments>
In order to earn credits of this course, students must submit two reports and get 60% points for each report before taking an examination.
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits and Graph Theory.
At the same semester with this course, students should take Data Structure and Algorithms.
After taking this source, students should take Information Security.
|
| ７． |
Schedule |
|
１. Introduction Everything begins from compuatations
すべては計算から始まる
<Comments>
Introduction Everything begins from computations
|
２. Concepts and technical words on the theory of automata and computatio
計算の理論のための概念や用語
<Comments>
Concepts and technical words on the theory of automata and computation
|
３. Deterministic finite automata
有限オートマトン
決定性有限オートマトン
<Comments>
訂正無し
|
４. Nondeterministic finite automata, the equivalency between deterministic finite automata and nondeterministic finite automata
非決定性有限オートマトン
決定性有限オートマトンと非決定性有限オートマトンの等価性
<Comments>
訂正無し
|
５. Regular expressions
正規表現
<Comments>
訂正無し |
６. Regular languages/Context-free languages, Pumping lemma for regular languages
正規言語/文脈自由言語
<Comments>
訂正無し |
７. Context-free grammars, generation and acceptance, Chomsky normal form
文脈自由文法
<Comments>
訂正無し |
８. Pushdown automata1 A decision problem for context-free grammars, CYK algorithm, pushdown automata
プッシュダウンオートマトン1 -プッシュダウンオートマトンの定義-
<Comments>
訂正無し |
９. Pushdown automata2 The equivalency between pushdown automata and context-free grammars
プッシュダウンオートマトン2 -プッシュダウンオートマトンと文脈自由文法の等価性-
<Comments>
訂正無し |
10. Turing machines
Turingマシン1 -Turingマシンの定義とその拡張-
<Comments>
訂正無し |
11. Nondeterministic Turing machines
Turingマシン2 -非決定性Turingマシン-
<Comments>
訂正無し |
12. Computational universality of Turing machines, reduction, Post correspondence problem and its undecidability
Turingマシンの万能性とその限界
<Comments>
訂正無し |
13. Quantification of computational complexity based on Turing machines
Turingマシンに基づいた計算量限定の計算
<Comments>
訂正無し |
14. Logic circuits and those complexities, complexity classes
論理回路に基づいた計算量限定の計算
<Comments>
訂正無し |
15. Summary
まとめ
<Comments>
訂正無し |
|
| １． |
Outline |
|
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.
In this course, students learn the meaning of computations by computers, and whether computations by computers have any bounds or not.
To deal with computations by computer mathematically, we model a computer itself in simple forms, which are computational models or automata. Given input data and a program, it become possible for a computer to compute the program, thus, we also model input data and programs in simple forms, which are called languages in this field. A language is a set of a series of symbols which obey a rule. The rule is called a grammar. It is known that an automaton corresponds to a grammar and the pair of a automaton and a grammar makes a hierarchical structure.
For each pair of an automata and a grammar, we will show its equivalency or non-equivalency by showing that a grammar can generate a language or not, where the language is accepted by an automata. In addition, as for an automaton called Turing machine which belongs to the hight class of the hierarchy, we will show that there are problems which cannot be solved essentially by computer by showing its universality and bound.
Moreover, by using the concept of complexity and Turing machines, we learn that problems dealt in the computer science can be classified into computational ones and non-computational ones. We also deals the relationship between computational ones and non-computational ones and these structures.
Students acquire skills related to the diplomatic policy 2 of Department of Information Science Correspondence Course.
<Comments>
Recently, computers get to win each world champion in 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.
In this course, students learn the meaning of computations by computers, and whether computations by computers have any bounds or not. To deal with computations by computer mathematically, we model a computer itself in simple forms, which are computational models or automata. Given input data and a program, it becomes possible for a computer to compute the program, thus, we also model input data and programs in simple forms, which are called languages in this field. A language is a set of a series of symbols which obey a rule. The rule is called a grammar. It is known that an automaton corresponds to a grammar and the pair of a automaton and a grammar makes a hierarchical structure.
For each pair of an automata and a grammar, we will show its equivalency or non-equivalency by showing whether a grammar can generate a language, where the language is accepted by an automata. In addition, as for an automaton called Turing machine, which belongs to the highest class of the hierarchy, we will show that there are problems which cannot be solved essentially by computer by showing its universality and bound.
Moreover, by using the concept of complexity and Turing machines, we learn that problems dealt in the computer science can be classified into computational ones and non-computational ones. We also deals the relationship between computational ones and non-computational ones and these structures.
Students acquire skills related to the diplomatic policy 2 of Department of Information Science Correspondence Course.
|
| ２． |
Objectives |
|
The goal of this class is that students master the following abilities;
Students can trace actions of a simple automata giving an input series of symbols and state transition functions of the automata.
Students understand the equivalency between deterministic and (generalized) nondeterministic finite automaton and regular expressions or regular grammar, and can utilize transform algorithm for each of them.
Students can express the features of regular languages as algebraic systems.
Students understand the meaning of the Chomsky normal form and given an arbitral context-free grammar, students can transform it to the corresponding Chomsky normal form.
Students can explain the Chomsky Hierarchy.
Students can explain the non-equivalency between deterministic pushdown automata and nondeterministic pushdown automata.
Students can explain the equivalency between pushdown automaton and context-free grammar and can utilize algorithms which translate one to another.
Students can explain the equivalency of deterministic Turing machines, nondeterministic Turing machines, other variations of Turing machines and logical circuits, the universality and the bound of Turing machines.
Students understand the concept of computational complexity and can express the complexity of each problem, algorithm with Big-O notation.
Students can explain the computational complexity and the relation of P, NP, NP complete and NP hard as classes of complexity, and can express the definition of NP.
<Comments>
The goal of this class is that students master the following abilities;
Students can trace actions of a simple automata giving an input series of symbols and state transition functions of the automata.
Students understand the equivalency between deterministic and (generalized) nondeterministic finite automaton and regular expressions or regular grammar, and can utilize transform algorithm for each of them.
Students can express the features of regular languages as algebraic systems.
Students understand the meaning of the Chomsky normal form and given an arbitral context-free grammar, students can transform it to the corresponding Chomsky normal form.
Students can explain the Chomsky Hierarchy.
Students can explain the non-equivalency between deterministic pushdown automata and nondeterministic pushdown automata.
Students can explain the equivalency between pushdown automaton and context-free grammar and can utilize algorithms which translate one to another.
Students can explain the equivalence of deterministic Turing machines, nondeterministic Turing machines, other variations of Turing machines and logical circuits, the universality and the bound of Turing machines.
Students understand the concept of computational complexity and can express the complexity of each problem, algorithm with Big-O notation.
Students can explain the computational complexity and the relation of P, NP, NP complete and NP hard as classes of complexity, and can express the definition of NP.
|
| ３． |
Grading Policy |
|
Grading policy:
Examination(100%).
The way of feedback;
Answers for questions or feedback for the contents of classes and examination will be given in a class, through LMS.
2つのレポート課題の合格を前提に、科目修得試験において60%以上をの評価点を得たものを合格とします。レポート課題に関しては、返却時にフィードバックを記述します。レポート課題及び科目修得試験の学習について質問がある場合は原則的にLMSを通して対応します。
<Comments>
Grading policy:
Examination(100%).
The way of feedback;
Answers for questions or feedback for the contents of classes and examination will be given in a class, through LMS.
|
| ４． |
Textbook and Reference |
|
Textbook: 丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045
Teaching materials: Published through LMS.
<Comments>
訂正無し
|
| ５． |
Requirements (Assignments) |
|
Teaching materials of this or last years will be published through LMS. In addition, small quizzes for each class will be published through LMS. Though quizzes are not used for grading. students should utilize to review each class. Students will be required to learn over 30 hours, which includes preparation and revision.
<Comments>
Teaching materials of this or last years will be published through LMS. In addition, small quizzes for each class will be published through LMS. Although, quizzes are not used for grading, students should utilize to review each class. Students will be required to learn over 30 hours, which includes preparation and revision.
|
| ６． |
Note |
|
In order to earn credits of this course, students must submit two reports and get 60% points for each report before taking an examination.
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits and Graph Theory.
At the same semester with this course, students should take Data Structure and Algorithms.
After taking this source, students should take Information Security.
関連して履修すべき科目は、論理数学、グラフ理論、データ構造とアルゴリズム、計算理論1、計算理論2です。
<Comments>
In order to earn credits of this course, students must submit two reports and get 60% points for each report before taking an examination.
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits and Graph Theory.
At the same semester with this course, students should take Data Structure and Algorithms.
After taking this source, students should take Information Security.
|
| ７． |
Schedule |
|
１. Introduction Everything begins from compuatations
すべては計算から始まる
<Comments>
Introduction Everything begins from computations
|
２. Concepts and technical words on the theory of automata and computatio
計算の理論のための概念や用語
<Comments>
Concepts and technical words on the theory of automata and computation
|
３. Deterministic finite automata
有限オートマトン
決定性有限オートマトン
<Comments>
訂正無し
|
４. Nondeterministic finite automata, the equivalency between deterministic finite automata and nondeterministic finite automata
非決定性有限オートマトン
決定性有限オートマトンと非決定性有限オートマトンの等価性
<Comments>
訂正無し
|
５. Regular expressions
正規表現
<Comments>
訂正無し |
６. Regular languages/Context-free languages, Pumping lemma for regular languages
正規言語/文脈自由言語
<Comments>
訂正無し |
７. Context-free grammars, generation and acceptance, Chomsky normal form
文脈自由文法
<Comments>
訂正無し |
８. Pushdown automata1 A decision problem for context-free grammars, CYK algorithm, pushdown automata
プッシュダウンオートマトン1 -プッシュダウンオートマトンの定義-
<Comments>
訂正無し |
９. Pushdown automata2 The equivalency between pushdown automata and context-free grammars
プッシュダウンオートマトン2 -プッシュダウンオートマトンと文脈自由文法の等価性-
<Comments>
訂正無し |
10. Turing machines
Turingマシン1 -Turingマシンの定義とその拡張-
<Comments>
訂正無し |
11. Nondeterministic Turing machines
Turingマシン2 -非決定性Turingマシン-
<Comments>
訂正無し |
12. Computational universality of Turing machines, reduction, Post correspondence problem and its undecidability
Turingマシンの万能性とその限界
<Comments>
訂正無し |
13. Quantification of computational complexity based on Turing machines
Turingマシンに基づいた計算量限定の計算
<Comments>
訂正無し |
14. Logic circuits and those complexities, complexity classes
論理回路に基づいた計算量限定の計算
<Comments>
訂正無し |
15. Summary
まとめ
<Comments>
訂正無し |
|
|