Mathematical Foundation for Computer Sciences (SE2324)

to undergraduates, School of Software

Textbook

[Sip12] Introduction to the Theory of Computation}, Michael Sipser, 2012.

Lectures

Lecture 1. Regular Languages and Finite Automata.

Lecture 2. Context-Free Languages and Pushdown Automata.

Lecture 3. Turing Machine.

Lecture 4. Decidability and Undecidability.

Lecture 5. Reducibility.

Lecture 6. Time Complexity.

Lecture 7. Space Complexity.

Lecture 8. PCP Theorem.

Lecture 9.

Lecture 10. Conclusion.

Materials

Guoqiang Li
Last modified: Friday, Jan. 30, 2026.