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

 計算理論 Theory of Computation (Spring 2020)

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室      

     (02) 33663700 ext 6606 

        D07921012@ntu.edu.tw    


Announcements:

  • Office Hours for Final  Exam:

        助教: 6/22 (一) 下午 1:00 - 3:30  地點: 博理館217室                    

       老師: 6/19 (五) 2:30 - 5:00  地點: 計算機中心二樓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

1b.pdf

1c.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

3a.pdf

 

Chapter 4 Decidability
Chapter 5 Reducibility
  • Reductions
  • Undecidability proof
  • Post correspondence problem,
  • Basic recursive function theory, ...

*4.pdf

5.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, ...

 

 

 

Textbook:

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


Grading:  

  • Homework/Project: 20%

  • Midterm exam: 40%

  • Final exam:  40% 

 

 

.