|
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室;
bottle1116(_at_)hotmail.com
(02) 33663700
ext 6606
Announcements:
-
期末考成績、期中考、作業1-5:
成績登錄。
-
1/25(一) 1:00 - 3:00 PM
可以來博理館525看期末考考卷。
-
期末考
(解答)
-
Final exam will be held at 9:10 - 12:00 on
January 11 (Monday) in BL-114.
-
Sample final exams (2014, 2013,
2012,
2011,
2010,
2009,
2008,
2007,
2006,
2005,
2004,
2001,
1996,
199? )
-
12/21 (一)上課時間改到9:30
AM 開始
-
Homework #5:
due Dec. 28 (Monday)
解答
-
Homework #4:
due Dec. 7 (Monday)
解答
-
期中考
(解答): 11月16日 (一) 9:10~12:00
AM (範圍: 課本pp. 31- 111 以及講義)
-
Homework #3:
due Nov. 16 (Monday)
解答
-
Sample midterm exams
2008;
2009;
2010;
2011;
2012;
2013;
2014
-
Homework #2:
due Oct. 26 (Monday)
解答
-
Homework #1:
due Oct. 12 (Monday)
解答
-
Oct. 12 (Monday)
改由10點開始上課 (10:00 ~ 12:00)
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, ...
|
|
|
