Instructor: 顏嗣鈞
E-mail: hcyen(_at_)ntu.edu.tw
Time:
9:10-12:00 AM,
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:
-
成績統計 (Homeworks #1, #2, #3;
Midterm Exam) 作業評分如有問題請連絡助教。期末考成績。可於6/21
3:00-4:30 PM來看考卷， 或另與老師連絡。
-
Final exam (solutions)
-
Final exam will be held on
June 6, 2023 (考試範圍: 講義 Chap2(p.15 開始)、Chap2a、Chap3、Chap4、Chap5 (至 p.32))
-
Office hours for final
exam
-
王璲 6/1（四）下午 2:00
- 4:30 Google Meet
https://meet.google.com/tkt-dnhx-pgg
(如登入有問題， 請EMAIL通知助教)
-
顏嗣鈞 6/2(五) 下午 2:00 - 4:00
Webex https://ntucc.webex.com/meet/hcyen
-
王璲 4/13（四）下午 2:00
- 4:30 Google Meet
https://meet.google.com/tkt-dnhx-pgg
(如登入有問題， 請EMAIL通知助教)
-
顏嗣鈞 4/14(五) 下午 2:00 - 3:30
Webex https://ntucc.webex.com/meet/hcyen
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 |
|
|
Chapter 1 |
Regular
Languages |
- deterministic vs.
nondeterministic FA,
- minimization
- pumping lemma for regular
sets,
- closure properties,
- decision properties,
- Myhill-Nerode theorem ...
|
Chap1.pdf
Chap1a.pdf
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
Chap2a.pdf
|
|
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 |
|
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
Chap6.pdf
Chap7.pdf
|
|
|
|
|
|
