| １． |
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, DP4C.
<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>
訂正無し
|
| ３． |
Grading Policy |
|
Grading policy:
Midterm report(50%), Examination(50%).
The way of feedback;
Answers for questions or feedback for the contents of class, worksheets, and examination will be given in a class, through LMS or in office hours.
<Comments>
Grading policy:
Midterm report(50%), Examination(50%).
The way of feedback;
Answers for questions or feedback for the contents of class, worksheets, and examination will be given in a class, through LMS or during office hours.
|
| ４． |
Textbook and Reference |
|
Textbook: 丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045
Teaching materials: Published through LMS.
<Comments>
訂正無し
|
| ５． |
Requirements (Assignments) |
|
Before a class, students are required to prepare the class by using materials, such as slides, handouts and
related materials which will be published on the LMS, which requires about 1.5 hours.
In a class, students should concentrate on, not to take notes, but to understand the contents of class,
to solve exercises in a class,
because most of the materials were published on the LMS before the class and students can bring them with
tablets or smart phones.
After a class, students are required to review the materials used in the class or quizzes on the LMS, which requires about 1.5 hours.
<Comments>
Before the class, students are required to prepare by using materials, such as slides, handouts and
related materials which will be published on the LMS, which requires about 1.5 hours.
In the class, students should not concentrate on taking notes, but on understanding the contents. And concentrate on solving exercises in the class.
Because most of the materials are published on the LMS before the class and students can bring them with
tablets or smart phones.
After the class, students are required to review the materials used in the class or quizzes on the LMS, which requires about 1.5 hours.ours.
|
| ６． |
Note |
|
Students can hardly earn credits not submitting the mid-term report. Thus, it is expected students to observe the deadline.
As for the self-learning support students are expected to utilize materials, such as slides, handouts and quizzes on the LMS
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits, Data Structure and Algorithms and Programming Language Theory
At the same semester with this course, students should take Graph Theory.
After taking this course, students should take computer architecture, information security.
If a student has a question on quizzes or mid-term report or examinations, ask the question in the class or in office hours or through LMS.
This course is a required course, and relates to the mid term 1-3 and 5-1 of the attaining targets for learning and educating, in the JABEE program.
<Comments>
Students can hardly earn credits not submitting the mid-term report. Thus, it is expected students to observe the deadline.
As for the self-learning support students are expected to utilize materials, such as slides, handouts and quizzes on the LMS.
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits, Data Structure and Algorithms and Programming Language Theory
At the same semester with this course, students should take Graph Theory.
After taking this course, students should take computer architecture, information security.
If a student has a question on quizzes or mid-term report or examinations, ask the question in the class or in office hours or through LMS.
This course is a required course, and relates to the mid term 4-1 of the attaining targets for learning and educating, in the JABEE program.
|
| ７． |
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
<Comments>
訂正無し
|
９. Pushdown automata2 The equivalency between pushdown automata and context-free grammars
<Comments>
訂正無し
|
10. Turing machines
<Comments>
訂正無し
|
11. Nondeterministic Turing machines
<Comments>
訂正無し
|
12. Computational universality of Turing machines, reduction, Post correspondence problem and its undecidability
<Comments>
訂正無し
|
13. Quantification of computational complexity based on Turing machines
<Comments>
訂正無し
|
14. Logic circuits and those complexities, complexity classes
<Comments>
訂正無し
|
15. Summary and examination
<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, DP4C.
<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>
訂正無し
|
| ３． |
Grading Policy |
|
Grading policy:
Midterm report(50%), Examination(50%).
The way of feedback;
Answers for questions or feedback for the contents of class, worksheets, and examination will be given in a class, through LMS or in office hours.
<Comments>
Grading policy:
Midterm report(50%), Examination(50%).
The way of feedback;
Answers for questions or feedback for the contents of class, worksheets, and examination will be given in a class, through LMS or during office hours.
|
| ４． |
Textbook and Reference |
|
Textbook: 丸岡 章著、"計算理論とオートマトン言語理論、" サイエンス社、ISBN-13: 978-4781911045
Teaching materials: Published through LMS.
<Comments>
訂正無し
|
| ５． |
Requirements (Assignments) |
|
Before a class, students are required to prepare the class by using materials, such as slides, handouts and
related materials which will be published on the LMS, which requires about 1.5 hours.
In a class, students should concentrate on, not to take notes, but to understand the contents of class,
to solve exercises in a class,
because most of the materials were published on the LMS before the class and students can bring them with
tablets or smart phones.
After a class, students are required to review the materials used in the class or quizzes on the LMS, which requires about 1.5 hours.
<Comments>
Before the class, students are required to prepare by using materials, such as slides, handouts and
related materials which will be published on the LMS, which requires about 1.5 hours.
In the class, students should not concentrate on taking notes, but on understanding the contents. And concentrate on solving exercises in the class.
Because most of the materials are published on the LMS before the class and students can bring them with
tablets or smart phones.
After the class, students are required to review the materials used in the class or quizzes on the LMS, which requires about 1.5 hours.ours.
|
| ６． |
Note |
|
Students can hardly earn credits not submitting the mid-term report. Thus, it is expected students to observe the deadline.
As for the self-learning support students are expected to utilize materials, such as slides, handouts and quizzes on the LMS
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits, Data Structure and Algorithms and Programming Language Theory
At the same semester with this course, students should take Graph Theory.
After taking this course, students should take computer architecture, information security.
If a student has a question on quizzes or mid-term report or examinations, ask the question in the class or in office hours or through LMS.
This course is a required course, and relates to the mid term 1-3 and 5-1 of the attaining targets for learning and educating, in the JABEE program.
<Comments>
Students can hardly earn credits not submitting the mid-term report. Thus, it is expected students to observe the deadline.
As for the self-learning support students are expected to utilize materials, such as slides, handouts and quizzes on the LMS.
Before taking this course, students should take the following courses;
Mathematical Logic, Logic Circuits, Data Structure and Algorithms and Programming Language Theory
At the same semester with this course, students should take Graph Theory.
After taking this course, students should take computer architecture, information security.
If a student has a question on quizzes or mid-term report or examinations, ask the question in the class or in office hours or through LMS.
This course is a required course, and relates to the mid term 4-1 of the attaining targets for learning and educating, in the JABEE program.
|
| ７． |
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
<Comments>
訂正無し
|
９. Pushdown automata2 The equivalency between pushdown automata and context-free grammars
<Comments>
訂正無し
|
10. Turing machines
<Comments>
訂正無し
|
11. Nondeterministic Turing machines
<Comments>
訂正無し
|
12. Computational universality of Turing machines, reduction, Post correspondence problem and its undecidability
<Comments>
訂正無し
|
13. Quantification of computational complexity based on Turing machines
<Comments>
訂正無し
|
14. Logic circuits and those complexities, complexity classes
<Comments>
訂正無し
|
15. Summary and examination
<Comments>
訂正無し
|
|
|