一、課程說明 (Course Description)--modified from Chapter 0 of our text book



This course will focus on the traditionally central areas of the theory of 

computation: automata, computability, and complexity. 



 1. The automata theory studies the definitions and properties of models of 

    computation.  These models are used in several applied areas of computer 

    science.  E.g., the finite automaton model is used in text processing,

    compilers, and hardware design;  the context-free grammar model is used

    in programming languages.



 2. The computability theory studies how to classify problems that are

    solvable by computers and problems that are not solvable.  The theory   

    arises from the discovery that certain basic problems cannot be solved

    by computers.  (The discovery was made during the first half of the 20th

    century, by mathematicians such as Gödel, Turing, and Church.)



 3. The complexity theory tries to classify, among problems that are solvable

    by computers, which problems are hard to solve (e.g., time-table 

    scheduling) and which problems are easy (e.g., sorting a list of numbers).

    The question --- what makes a problem computationally hard and others 

    easy --- has been intensively research for the past 35 years.  Complexity

    theory affects directly the field of cryptography, for it pinpoints 

    problems that are hard to solve, which consequently leads to the design

    of new codes that are hard to break.



In this course, we will introduce some of the fundamental results in each

of the above areas.



二、指定用書 (Text Book)  

    Introduction to the Theory of Computation (2nd Edition), by Michael Sipser 



三、參考書籍 (References)   

    1. Computational Complexity, by Christos Papadimitiou

    2. Introduction to Automata Theory, Languages, and Computation, by

       John Hopcroft, Rajeev Motwani, and Jeff Ullman.



四、教學方式 (Teaching Method)  

    Lectures and Tutorials (Lectures in English)



五、教學進度 (Syllabus)



1. Automata Theory:

   Regular Languages, Context-Free Languages



2. Computability Theory:

   Turing Machines, Decidability, Reducibility 



3. Complexity Theory:

   Time Complexity, Space Complexity, Circuit Complexity 



4. Advanced Topics in Complexity Theory (if time permits)

   Approximation Algorithms, Probabilistic Algorithms, Alternation,

   Interactive Proof System, Parallel Computation, Cryptography



六、成績考核 (Evaluation) 



    5 Assignments:  Best four     * 37%

                    Remaining one *  3%



    Midterm Quiz:                   10%

    Final Exam:                     50%

    -----------------------------------

    Total                          100%



七、可連結之網頁位址 (Web links) 

    06年下學期之網頁 [連結]