一、課程說明 (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年下學期之網頁 [連結]