Course title
V05201002
Theory of Computation

 idogawa tomoyuki Click to show questionnaire result at 2019
Course description
This subject deals the computations as mathematical objects. At present we have powerful computers, but they are limited by finite memories and finite calculation times. From a practical point of view it is desirable to develop efficient algorithms, while from a theoretical point of view it is important to determine whether or not the objective problem can be solved by our computers (computability) at first. Next, it becomes a problem whether or not the problem can be solved in a realistic time (computational complexity). In this course, we will formulate computational models such as Turing machine or While programs and will discuss the computability theory and the computational complexity theory.
Purpose of class
To understand the fundamental theories of computation.
Goals and objectives
  1. To understand the concept of Turing machines and to be able to discuss the theories of computation by using them.
  2. To understand the concept of computability (Turin decidability) and to be able to show the decidability/undecidability of a given elemental problem.
  3. To understand the classes of computational complexites.
Language
Japanese
Class schedule

 Class schedule HW assignments (Including preparation and review of the class.) Amount of Time Required
1. Preliminaries (introduction, graphs, strings and languages) Review the fundamental concepts of theory of computation by using Web, etc. 190minutes
2. Automata (1)
Deterministic finite automaton (DFA) 		Review the last lecture/read handouts 190minutes
3. Automata (2)
Nondeterministic finite automaton (NFA) 		Review the last lecture/read handouts 190minutes
4. Automata (3)
Equivalence of DFA and NFA,
Regular languages 		Review the last lecture/read handouts 190minutes
5. Turing machines (1)
Definition and examples,
Recognizability and decidability of languages 		Review the last lecture/read handouts 190minutes
6. Turing machines (2)
Variants of Turing machines,
Nondeterministic Turing machines 		Review the last lecture/read handouts 190minutes
7. Turing machines (3)
Other computational models 		Review the last lecture/read handouts 190minutes
8. Decidability (1)
Algorithm and Church-Turing thesis 		Review the last lecture/read handouts 190minutes
9. Decidability (2)
Universal Turing machine 		Review the last lecture/read handouts 190minutes
10. Decidability (3)
Decidable languages 		Review the last lecture/read handouts 190minutes
11. Decidability (4)
Undecidability of the halting problem 		Review the last lecture/read handouts 190minutes
12. Decidability (5)
Turing unrecognizable languages 		Review the last lecture/read handouts 190minutes
13. Computational complexity:
Definition of computational complexity and order notations,
The class P and the class NP 		Review the last lecture/read handouts 190minutes
14. Final examination and review Review the total of lectures 190minutes
Total. - - 2660minutes
Relationship between 'Goals and Objectives' and 'Course Outcomes'

 Examination Report Total.
1. 30% 10% 40%
2. 30% 10% 40%
3. 10% 10% 20%
Total. 70% 30% -
Evaluation method and criteria
Examinations (70%) and reports (30%)
Textbooks and reference materials
Reference: M. Sipser, "Introduction to the theory of computation 3rd editon," Cengage Learning, 2013; handout will be available
Prerequisites
Already acquired the credit of the course "Automata"
Office hours and How to contact professors for questions
  • Tuesday 12:35 -- 13:05.
Regionally-oriented
Non-regionally-oriented course
Development of social and professional independence
  • Non-social and professional independence development course
Active-learning course
N/A
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicatable
N/A N/A
Education related SDGs:the Sustainable Development Goals
    Last modified : Sat Mar 21 13:04:02 JST 2020