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室;
bottle1116(_at_)hotmail.com
(02) 33663700
ext 6606
Announcements:
-
期中考、期末考、作業1-4成績登錄，如要看期末考考卷，請於1/21
(Monday) 11:00 - 12:00 AM 間到計算機中心220室。
-
Final Exam Solutions
-
Final exam will be held on
January 8 (Tuesday), 9:10 - 12:00.
-
期中考、作業1-4成績登錄
-
Office Hours for Final Exam:
助教: 1/5 (五)
下午 2:00 - 5:00 地點:
博理館606室
老師: 1/7 (一) 上午
10:30 - 12:30
地點: 計算機中心二樓220。
-
期末考範圍: 講義 3、4、5、5a、5b、6、7
-
12/18 停課一次
-
Homework #4
(Solutions):
due December 25, 2018
-
Midterm Solutions
-
Sample final exams (2017,
2016,2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2001, 1996, 199? )
-
Homework #3
(Solutions):
due December 11, 2018
-
Office Hours for Midterm Exam:
助教: 11/9 (五)
下午 2:00 - 5:00 地點:
博理館606室
老師: 11/12 (一) 上午10:30-12:30
地點: 計算機中心二樓220。
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,
- minimization
- pumping lemma for regular
sets,
- closure properties,
- decision 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,
- valid and invalid
computations of TMs
|
3.pdf
4.pdf |
|
Chapter 4 |
Decidability |
|
Chapter 5 |
Reducibility |
- Reductions
- Undecidability proof
- Post correspondence
problem,
- Basic recursive function
theory, ...
|
5.pdf
5a.pdf
5b.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
8.pdf |
|
Supplementary Materials |
- Weighted automata
- Tree automata,
- Omega automata,
- Probabilistic automata, ...
|
LBA & CSG
PTIME-hierarchy
Relativization
|
|
