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.
| Term-end examination | Regular assignments | Total. | |
|---|---|---|---|
| 1. | 25% | 20% | 45% |
| 2. | 25% | 20% | 45% |
| 3. | 10% | 0% | 10% |
| Total. | 60% | 40% | - |
| Class schedule | HW assignments (Including preparation and review of the class.) | Amount of Time Required | |
|---|---|---|---|
| 1. | Preliminaries (introduction, graphs, strings and languages, automata) | Review the subject "Fundamentals of Theory of Computation" | 190minutes |
| 2. | Turing machines (1) Definition and examples | Review the last lecture/read handouts | 190minutes |
| 3. | Turing machines (2) Recognizability and decidability of languages | Review the last lecture/read handouts | 190minutes |
| 4. | Turing machines (3) Variants of Turing machines, Nondeterministic Turing machines | Review the last lecture/read handouts | 190minutes |
| 5. | Turing machines (4) Other computational models | Review the last lecture/read handouts | 190minutes |
| 6. | Decidability (1) Algorithm and Church-Turing thesis | Review the last lecture/read handouts | 190minutes |
| 7. | Decidability (2) Universal Turing machine | Review the last lecture/read handouts | 190minutes |
| 8. | Decidability (3) Decidable languages | Review the last lecture/read handouts | 190minutes |
| 9. | Decidability (4) Undecidability | Review the last lecture/read handouts | 190minutes |
| 10. | Decidability (5) Turing unrecognizable languages | Review the last lecture/read handouts | 190minutes |
| 11. | Computational complexity (1) Definition and order notations | Review the last lecture/read handouts | 190minutes |
| 12. | Computational complexity (2) The class P and the class NP | Review the last lecture/read handouts | 190minutes |
| 13. | Computational complexity (3) NP completeness | Review the last lecture/read handouts | 190minutes |
| 14. | Term-end examination and its review | Review the total of lectures | 190minutes |
| Total. | - | - | 2660minutes |
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.
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.
| ways of feedback | specific contents about "Other" |
|---|---|
| Feedback in the class |
Handout will be available.
Reference: M. Sipser, "Introduction to the theory of computation 3rd edition," Cengage Learning, 2013.
Reference: M. Sipser, "Introduction to the theory of computation 3rd edition," Cengage Learning, 2013.
It is assumed that the student understands the content of the course "Fundamentals of Theory of Computation".
- 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 02 04:06:38 JST 2025