首頁 > 教務資訊 > 課程內容
  
課程資訊
課程大綱
學群課程
台大課程網
台大課程地圖
裝飾圖片 課程內容
計算理論
Theory of Computing
顏嗣鈞   109下

課程概述
1. finite automata, regular languages, regular grammars:
deterministic vs. nondeterministic, one-way vs. two-way finite automata, minimization,
pumping lemma for regular sets, closure properties.
2. pushdown automata, context-free languages, context-free grammars:
deterministic vs. nondeterministic, one-way vs. two-way pdas, reversal bounded pdas,
linear grammars, counter machines, pumping lemma for cfls, chomsky normal form,
greibach normal form, closure properties.
3. linear bounded automata, context-sensitive languages, context-sensitive grammars.
4. turing machines, recursively enumerable sets, type 0 grammars:
variants of turing machines, halting problem, undecidability, post correspondence
problem, valid and invalid computations of tms.
5. basic recursive function theory
6. basic complexity theory:
various resource bounded complexity classes, including nlogspace, p, np,
pspace, exptime, and many more. reducibility, completeness.
7. advanced topics in complexity theory:
approximation algorithms, probabilistic complexity, parallel complexity, alternation,
interactive proof systems, oracle computations.

課程目標

課程要求

指定閱讀

參考書目
教科書: 教科書: 上課後決定
參考書目:

更多資訊 臺大課程網