Electrical Engineering
 
Welcome Biography Research Teaching Publications Awards
Lab Professional Activities Research Projects Links

 計算理論 Theory of Computation (Fall 2018)

Instructor: 顏嗣鈞
E-mail:  hcyen(_at_)ntu.edu.tw

Time:  9:10-12:00 AM, Tuesday

Place: Room BL-112

Office phone: (02) 3366 3581

Office hours: by appointment

TA:  顏玓德  博理館606室;

     bottle1116(_at_)hotmail.com

     (02) 33663700 ext 6606     


Announcements:

        助教: 1/5  (五)  下午 2:00 - 5:00  地點: 博理館606室

        老師: 1/7  (一)  上 10:30 - 12:30  地點: 計算機中心二樓220。

        助教: 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

 

 

 

 

Textbook:

  • Introduction to the Theory of Computation,  Michael Sipser, (3rd Ed. Thomson)


Grading:  

  • Homework/Project: 20%

  • Midterm exam: 40%

  • Final exam:  40% 

 

 

.