Instructor: 顏嗣鈞
E-mail: hcyen(_at_)ntu.edu.tw
Time:
2:20-5:20 PM,
Tuesday
Place: Room
BL-11 2
Office phone:
(02) 3366 3581
Office hours:
by appointment
TA:
王璲 博理館606室
(02) 33663700
ext 6606
D07921012@ntu.edu.tw
Announcements:
-
Final Exam Grades (如需看考卷，請和老師聯絡)
-
Fianl exam (Solutions)
-
Office hours for final
exam
-
王璲 5/30（四）下午 6:30
- 8:30 Google Meet
https://meet.google.com/jxk-frwj-ssd
(如登入有問題， 請EMAIL通知助教)
-
Homework #4
(Solutions) due June 4, 2024. Should you have questions about the homework, please
write to the TA.
-
Final exam will be held on
June 4, 2024. (考試範圍: 講義I Chap3、Chap4, Chap5, Prob.
Cmputation)
-
Sample final exams
2006;
2007;
2009;
2011;
2012;
2013;
2014;
2015;
2016;
2017;
2018;
2020;
2021,
2023
-
Homework #3
(Solutions) 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
-
王璲 4/5（五）下午 2:00
- 4:00 Google Meet
https://meet.google.com/jxk-frwj-ssd
(如登入有問題， 請EMAIL通知助教)
-
顏嗣鈞 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
(updated 5/13)
Probabilistic Computation
(updated 5/19)
Oracle Computation and Polynomial-Time Hierarchy
Decision vs. Search
|
|
|
|
|
|
