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.
- To understand the concept of Turing machines and to be able to discuss the theories of computation by using them.
- To understand the concept of computability (Turin decidability) and to be able to show the decidability/undecidability of a given elemental problem.
- To understand the classes of computational complexites.
| 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 |
| Final assignment | Weekly assignments | Total. | |
|---|---|---|---|
| 1. | 25% | 20% | 45% |
| 2. | 25% | 20% | 45% |
| 3. | 10% | 0% | 10% |
| Total. | 60% | 40% | - |
Final assignment (60%) and weekly 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.
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.
Handout will be available.
Reference: M. Sipser, "Introduction to the theory of computation 3rd editon," Cengage Learning, 2013.
Reference: M. Sipser, "Introduction to the theory of computation 3rd editon," Cengage Learning, 2013.
- Course that cultivates an ability for utilizing knowledge
| Work experience | Work experience and relevance to the course content if applicable |
|---|---|
| N/A | N/A |
Last modified : Sun Mar 21 16:45:38 JST 2021