新南威尔士大学Theory of Computation课程怎么学？

最佳答案

• 

  课程顾问-小管家 2023-04-27 16:24:58

  立即咨询

  　　同学在学习新南威尔士大学Theory of Computation这门课的时候，要时常思考三个问题：一次计算能解决什么问题?计算解决方案有多难?如何表达计算?课程内容始终是基于这三个问题展开讨论的。因为课程本身难度比较大，所以同学有不理解的内容一定要及时问老师，不然可能会对后续课程学习有影响。

  

  　　我们可以把Theory of Computation这门课涵盖的知识分为三个部分，这样学习起来更有条理：

  　　1、语言和自动机：正则表达式和语言、有限自动机、确定性、环境无关语法和语言、乔姆斯基范式、字符问题、泵作用引理、下推自动机、CFLs的可判定性问题。

  　　2、可计算性：形式语言与问题、图灵机(TMs)、可计算性、可判定性、通用TMs、图灵论题、停机问题、约简和不可判定性证明。

  　　3、计算复杂性：运行时间，空间，复杂性类别，非确定性和NP，多项式约简和NP完备性，空间复杂度，NLogspace，交替，层次定理，优化问题和逼近。

  　　我们的澳洲课程辅导老师可以随时为同学答疑解惑，同学有补习需求的话直接和老师沟通即可。

其他答案