COMP4141

计算理论

课程定位 COMP4141/9415 是 UNSW 计算机专业最具‘哲学高度’与‘数学纯度’的顶级理论课。它解决了计算科学最本质的命题：什么是可计算的？什么又是永远无法被计算机解决的？它探讨了自动机、形式语言与计算复杂性的极限。它是通往高级编译器理论、密码学研究、及理论计算机科学 (TCS) 领域的必经圣殿。它将编程彻底抽象为符号动力学，是区分‘应用开发者’与‘计算机科学家’的终极红线。 技术栈与学习内容 课程基于严密的数学证明。核心内容包括：形式语言与自动机理论（DFA, NFA, 正则表达式的等价性）、上下文无关文法 (CFG) 与下推自动机、最具杀伤力的‘图灵机 (Turing Machines)’及其通用性证明。此外，课程深入探讨了可判定性 (Decidability) 与停机问题 (Halting Problem) 的不可解性证明、以及 P, NP, PSPACE 等复杂性类的层级关系。课程强调利用归约 (Reductions) 证明问题的计算下界。 课程结构 10 周极高强度的脑力风暴。前三周夯实正则语言与有限自动机，中期转向图灵机与不可判定性（这是全课的逻辑巅峰），后期聚焦复杂性理论。评估由每周的‘智力脱发级’证明习题 (Problem Sets)、两个要求极高逻辑构造能力的个人项目（Assignment，涉及构造特定属性的自动机或形式化证明）、以及一场极其考验逻辑严密性与智力上限的期末综合大考组成。该课极其看重‘证明的无瑕疵性’。 适合人群 计算机专业大四、荣誉学位或数学系学生。必须具备极其扎实的离散数学 (MATH1081) 功底。如果你痴迷于‘思维的极限’、或者想搞清楚‘为什么 P vs NP 价值百万美元’，这门课会为你揭示真理。建议每周投入 25 小时以上进行逻辑构建。