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/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. | Term-end examination and its review | Review the total of lectures | 190minutes |
| Total. | - | - | 2660minutes |
| Term-end examination | Weekly assignments | Total. | |
|---|---|---|---|
| 1. | 25% | 20% | 45% |
| 2. | 25% | 20% | 45% |
| 3. | 10% | 0% | 10% |
| Total. | 60% | 40% | - |
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).
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).
| 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 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 : Sat Sep 09 07:28:16 JST 2023