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
English
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
Review the last lecture/read handouts 190minutes
5. Automata (4)
Regular languages
Review the last lecture/read handouts 190minutes
6. Turing machines (1)
Definition and examples,
Recognizability and decidability of languages
Review the last lecture/read handouts 190minutes
7. Turing machines (2)
Variants of Turing machines,
Nondeterministic Turing machines
Review the last lecture/read handouts 190minutes
8. Turing machines (3)
Other computational models
Review the last lecture/read handouts 190minutes
9. Decidability (1)
Algorithm and Church-Turing thesis
Review the last lecture/read handouts 190minutes
10. Decidability (2)
Universal Turing machine
Review the last lecture/read handouts 190minutes
11. Decidability (3)
Decidable languages
Review the last lecture/read handouts 190minutes
12. Decidability (4)
Undecidability of the halting problem
Review the last lecture/read handouts 190minutes
13. Decidability (5)
Turing unrecognizable languages
Review the last lecture/read handouts 190minutes
14. Computational complexity:
Definition of computational complexity and order notations,
The class P and the class NP
Review the total of lectures 190minutes
Total. - - 2660minutes
Relationship between 'Goals and Objectives' and 'Course Outcomes'

Term-end examination Weekly assignments Total.
1. 25% 20% 45%
2. 25% 20% 45%
3. 10% 0% 10%
Total. 60% 40% -
Evaluation method and criteria
Term-end examination (60%) and two or three regular assignments (40%).
Submit each report in the specified format on time. Complete the assigned tasks without fail (correct results for calculations, and correct deductions for proofs). When a discussion is required, write a discussion, not an impression. The report should be written with the reader in mind (in principle, the process should be written as well as the answer). You will get 100 points if you have done these things perfectly. You will be given a halfway point for each report, so if you achieve 60% of the above, you will pass.
As described above, the term-end examination (written test) will be 60% and the regular assignments (reports) 40% in the evaluation. But, if it becomes difficult to give the term-end examination in the classroom, the final assignment (report; it may be divided into two or three assignments) will be substituted for the term-end examination (to be announced at the beginning of the class or when the situation suddenly changes).
Textbooks and reference materials
Handout will be available.
Reference: M. Sipser, "Introduction to the theory of computation 3rd editon," Cengage Learning, 2013.
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
  • Course that cultivates an ability for utilizing knowledge
Active-learning course
N/A
Course by professor with work experience
Work experience Work experience and relevance to the course content if applicable
N/A N/A
Education related SDGs:the Sustainable Development Goals
  • 9.INDUSTRY, INNOVATION AND INFRASTRUCTURE
Last modified : Sat Mar 19 00:04:29 JST 2022