|
Instructor: 顏嗣鈞
E-mail: hcyen(_at_)ntu.edu.tw
Time:
9:10-12:00 AM,
Monday
Place: Room
BL-114
Office phone:
(02) 3366 3581
Office hours:
by appointment
TA:
張以潤 (博理館 606; Email:
au3bjp4(_at_)gmail.com
)
Announcements:
-
期末考成績將於1/25
(日)
10 PM
前在此公佈(作業及考試成績)，同學可於星期一(1/26)下午2:00
– 3:30 至博理館525
看考卷
-
Final exam (Solutions)
-
Final exam will be held at 9:10 - 12:00 on
January 12 (Monday) in BL-114.
-
Sample final exams (2013,
2012,
2011,
2010,
2009,
2008,
2007,
2006,
2005,
2004,
2001,
1996,
199? )
-
12/22因老師出國停課。補課訂於12/27
(六) 9:10 - 12:00 於博理館103教室。
-
Homework #3:
due Dec. 29 (Monday)
-
Homework #2:
due Nov. 24 (Monday)
-
Midterm exam (Solutions) will be held at 9:10 - 12:00 on
Nov. 17 (Monday) in BL-114.
-
11/8(六) 9:10 - 12:00 於博理館114教室第二次補課。
-
Sample midterm exams
2008;
2009;
2010;
2011;
2012;
2013
-
10/27 上課延至9:40 AM 開始
-
Homework #1:
due Oct. 27 (Monday)
-
9/29
與 10/6 因老師出國停課。第一次補課訂於9/27
(六) 9:10 - 12:00 於博理館114教室。
Class Notes:
(Courtesy of Prof. Bow-Yaw Wang of
Academia Sinica)
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
0.pdf |
|
|
Chapter 1 |
Regular
Languages |
-
deterministic vs.
nondeterministic FA,
-
one-way vs. two-way FA,
-
minimization,
-
pumping lemma for regular sets,
-
closure properties,
-
Myhill-Nerode Theorem,
...
|
1.pdf
1a.pdf
|
|
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,
...
|
2.pdf
2a.pdf |
|
Chapter 3 |
The Church-Turing Thesis |
- variants of Turing
machines,
- halting problem,
- undecidability,
- Post correspondence
problem,
- valid and invalid
computations of TMs
|
3.pdf
4.pdf
|
|
Chapter 4 |
Decidability |
|
Chapter 5 |
Reducibility |
- Reductions
- Undecidability proof
- Basic recursive function
theory, ...
|
5.pdf
5a.pdf |
|
Chapters 7-8 |
Complexity Theory |
- various
resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE,
EXPTIME, and many more,
-
reducibility,
-
completeness, ...
|
6.pdf
7.pdf
|
|
Supplementary Materials |
- Weighted automata
- Tree automata,
- Omega automata,
- Probabilistic automata, ...
|
8.ppt
|
|
