Hsu-Chun Yen's Homepage

計算理論 Theory of Computation

(Spring 2024)

Instructor: 顏嗣鈞

E-mail:  hcyen(_at_)ntu.edu.tw

Time: 2:20-5:20 PM, Tuesday

Place: Room BL-112

Office phone: (02) 3366 3581

Office hours: by appointment

TA: 王璲博理館606室

(02) 33663700 ext 6606

Announcements:

Homework #3 due May 7, 2024. Should you have questions about the homework, please write to the TA.
Homework #2: (Solutions) due April 9, 2024. Should you have questions about the homework, please write to the TA.
Midterm exam (Solutions) will be held on April 9 (考試範圍: 講義Intro、Chap1、Chap2(不含DCFL))
Office hours for midterm
1. 王璲 4/5（五）下午 2:00 - 4:00 Google Meet
  https://meet.google.com/jxk-frwj-ssd (如登入有問題，請EMAIL通知助教)
2. 顏嗣鈞 4/8(-) 上午 10:00 - 11:30 Webex https://ntucc.webex.com/meet/hcyen
　
Sample midterm exams 2008; 2009; 2010; 2011; 2012; 2013; 2014; 2015; 2016; 2017; 2018; 2020; 2021; 2023
Homework #1: (Solutions) due March 26, 2024. Should you have questions about the homework, please write to the TA.

Class Notes:

This course provides a rigorous, graduate level introduction to Automata theory, Formal languages, and Complexity. Topics to be covered will include:

Topics
	Chapter 0	Introduction and mathematical notations		Intro.pdf (updated 2/18)
	Chapter 1	Regular Languages	deterministic vs. nondeterministic FA, minimization pumping lemma for regular sets, closure properties, decision properties, Myhill-Nerode theorem ...	Chap1.pdf (updated 3/4) Supplementary materials
	Chapter 2	Context-free Languages	deterministic vs. nondeterministic PDA, one-way vs. two-way PDA, reversal bounded PDA, linear grammars, counter machines, pumping lemma for CFLs, Chomsky normal form, Greibach normal form, closure properties, ...	Chap2.pdf (updated 3/25)
	Chapter 3	The Church-Turing Thesis Decidability	variants of Turing machines, halting problem, undecidability, valid and invalid computations of TMs	Chap3.pdf
	Chapter 4	Reducibility	Reductions Undecidability proof Post correspondence problem, Basic recursive function theory, ...	Chap4.pdf (updated 4/25) Supplementary materials
	Chapter 5	Complexity Theory	various resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE, EXPTIME, and many more, reducibility, completeness, ... time/space hierarchy theorems probabilistic complexity classes	Chap5.pdf

Reference textbook:

Introduction to the Theory of Computation, Michael Sipser, (3rd Ed. Thomson) 開發圖書

Grading: