|
Instructor: 顏嗣鈞
E-mail: yen(_at_)cc.ee.ntu.edu.tw
Time:
9:10-12:00 AM,
Monday
Place: Room
BL-114
Office phone:
(02) 3366 3581
Office hours:
by appointment
TA:
張以潤
b98901012@ntu.edu.tw
Announcements:
-
一月十四日(星期二)下午3:00 - 5:00 間，可以來博理館525室看期末考考卷。
-
Final exam solutions
-
Final exam
will be held
on January 6 (Monday) 9:10 - 12:00 AM.
-
Final Exam covers Chap. 6 (pushdown automata),
Chap. 7 (properties of CFLs), Chap. 8 (Intro. to Turing machines), Chap.
9 (undecidability), and materials discussed in class including basic
recursive function theory, basic complexity theory (time/space
hierarchies, P vs. NP) ... etc.
-
Sample
final exams (2012,
2011,
2010,
2009,
2008,
2007,
2006,
2005,
2004,
2001,
1996,
199? )
-
Homework #4: (Solutions)
due Dec 23, 2013.
-
Midterm solutions
-
Homework #3:
(Solutions) due Dec 9, 2013.
-
補課:
11/25 (一) 6:10-8:30 PM 於
BL 103
-
Homework #2:
(Solutions)
due Nov 11, 2013.
-
Midterm exam will be held at 9:10 - 12:00 on Nov.
4 (Monday) in BL-114.
-
期中考範圍: Chapter 1 (pp. 28-33), Chapter 2 (pp.
37-84), Chapter 3 (pp. 85-108), Chapter 4 (pp. 127-170), Chapter 5 (pp.
171-183), Chapter 7 (pp. 261-279) + class notes
-
Sample midterm exams
2008;
2009,
2010,
2011,
2012
-
Homework #1:
(Solutions)
due October 28, 2013.
-
因老師出國開會，9/23 及 9/30 停課。 第一次補課訂於 10/5 (六) 9:10
-- 12:10 於 BL 114。
Class Notes:
(Access restricted)
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 |
0.pdf |
|
|
Chapter 1 |
The Methods and the Machines |
-
deterministic vs.
nondeterministic FA,
-
one-way vs. two-way FA,
-
minimization,
-
pumping lemma for regular sets,
-
closure properties,
-
Myhill-Nerode Theorem,
...
|
1.pdf
2.pdf |
|
Chapter 2 |
Finite Automata |
|
Chapter 3 |
Regular Expressions and
Languages |
|
Chapter 4 |
Properties of Regular
Languages |
|
Chapter 5 |
Context-free Grammars and
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,
...
|
3.pdf
4.pdf
5.pdf
|
|
Chapter 6 |
Pushdown Automata |
|
Chapter 7 |
Properties of Context-free
Languages |
|
Chapter 8 |
Introduction to Turing
Machines |
- variants of Turing
machines,
- halting problem,
- undecidability,
- Post correspondence
problem,
- valid and invalid
computations of TMs,
- Basic recursive function
theory, ...
|
6.pdf
7.pdf
8.pdf
|
|
Chapter 9 |
Undecidability |
|
Chapter 10 |
Intractable Problems |
- various
resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE,
EXPTIME, and many more,
-
reducibility,
-
completeness, ...
|
9.pdf
10.pdf
Polynomial-time hierarchy |
|
Chapter 11 |
Additional Classes of Problems |
|
|
|
Supplementary Materials |
- Weighted automata
- Tree automata,
- Omega automata,
- Probabilistic automata, ...
|
|
|
