Meysam Madani

Courses

ToC Links

مبانی نظریه محاسبه، زبان‌ها و ماشین‌ها- میثم مدنی

Theory of Computation

Spring 2017, Shahid Beheshti University
 

References

main:

- Michael Sipser (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.

Complementaries:

- John Martin, Introduction to Languages and the Theory of Computation, 4th Ed. Feb 2, 2010.
- Hopcroft, John E. and Jeffrey D. Ullman (2006). Introduction to Automata Theory, Languages, and Computation. 3rd ed. Reading, MA: Addison-Wesley.
- Alan Turing (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. IEEE. 2 (42): 230–265.
- Martin Davis (2004). The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions (Dover Ed). Dover Publications.

Course Materials


Grading

- 35% - Midterm Exam (9 May 2017), chapters 3,4
- 65% - Final Exam
- (up to) 10% - Projects (Web Development, Contents, Design, Problem Solving)

Course outline:

 The Church–Turing Thesis (Chp. 3)
-Turing Machines
-Variants of Turing Machines
-The Definition of Algorithm
Decidability (Chp. 4)
-Decidable Languages
-Undecidability
Reducibility (Chp. 5)
-Undecidable Problems from Language Theory
-A Simple Undecidable Problem
-Mapping Reducibility
Time Complexity (Chp. 7)
- The Class P
- The Class NP
- NP-completeness.
- Additional NP-complete Problems
Space Complexity (Chp. 8)
- Savitch’s Theorem
- The Class PSPACE