|
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 3700 ext 123
Office hours:
by appointment
TA:
何宗諭 (明達631;
d98921029(_at_)ntu.edu.tw)
Announcements:
(老師) 1/5 (Thurs.) 3:00 - 4:30 PM (電機二館一樓系主任辦公室)
(助教) 1/6 (Friday) 2:00 - 4:00 PM (明達館631)
-
期末將於1/9 (一)舉行 (考試範圍 Chapters 5-9)
-
Sample
final exams (2010,
2009,
2008,
2007,
2006,
2005,
2004,
2001,
1996,
199? )
-
期中考的評分如有問題 請於星期三(12/28)
中午12:00~下午2:00 和下午5:00~下午7:00 到明達館 631 實驗室 找 何宗諭 助教
-
Homework #2:(Solution)
due Dec. 26, 2011
-
期中考(Solution)將於11/14 (一)舉行 (考試範圍 Chapters 1-4)
-
Office
Hours: 11/10 (四) 2:00 - 4:00; BL-525室
-
Sample midterm exams
1996,
2001,
2002,
2004,
2005 (2005 Solutions:
1,
2,
3),
2006;
2007;
2008;
2009,
2010
-
11/5
(六) 9:10 - 12:00 BL 114 補課
-
Homework #1 (Solution):
due Nov. 7, 2011
-
10/31 (一)的課暫停,以後再補課
-
10/3 (一)
的課調至10/1 (六) 9:10 - 12:00 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
9.pdf
|
|
Chapter 9 |
Undecidability |
|
Chapter 10 |
Intractable Problems |
- various
resource bounded complexity classes, including NLOGSPACE, P, NP, PSPACE,
EXPTIME, and many more,
-
reducibility,
-
completeness, ...
|
|
|
Chapter 11 |
Additional Classes of Problems |
|
|
|
Supplementary Materials |
- Weighted automata
- Tree automata,
- Omega automata,
- Probabilistic automata, ...
|
|
|
