计算是计算机科学的核心，而《计算理论》正是研究计算的本质、极限与效率的基础学科。作为计算机科学的理论基础，本课程探讨计算机能解决什么、不能解决什么，以及如何高效解决问题。课程涵盖自动机与语言、可计算性理论和计算复杂性理论三大支柱，帮助学生理解计算能力的基本数学特性。学习本课程不仅能培养严谨的抽象思维和数学建模能力，还能为算法设计、编译器优化、密码学乃至人工智能等领域奠定理论基础。通过探索图灵机的可判定性与可识别性、P问题与NP问题关系等经典问题，学生将掌握计算机科学的基础认知，不拘泥于具体的编程语言，而是真正理解计算的边界与可能。

本课程贯彻“厚基础、精理论、重实践、强能力”的网络空间安全人才培养理念，将思政教育有机融入教学全过程，综合采用研教融合、启发式教学、研讨式教学、案例教学、翻转课堂等教学方法，践行网络安全特色的PRIDE教学模式，注重理论与应用的结合，详略得当，重点突出，既锻炼逻辑推理能力，又启发创新思维，是未来从事科研或高端技术开发的信息安全专业学生必备基础。

本课程内容主要包括有穷自动机与正则语言、上下文无关文法与下推自动机、丘奇-图灵论题、可判定性、可规约性、时间复杂性。授课目标如下：

①掌握计算理论的基本概念、知识体系和知识点

②从形式化、逻辑和数学的角度了解计算机的能力与局限性

③理解计算理论与方法的核心思想，培养针对现实问题建立计算模型进行分析的能力

④培养对理论进行叙述及证明的基本技能

工科高等代数、离散数学

《计算理论导引》，段磊 唐常杰等译, 迈克尔·西普塞主编，机械工业出版社，2015年6月

Q1：《计算理论》MOOC学习成绩由哪几部分组成？

A1：《计算理论》MOOC的学习成绩组成为：域外出勤成绩10%+单元测验和作业20%+期中考试30%+期末考试40%。对于单次测验，测试题型有单选（2分）、多选（3分）、判断（2分）、填空（2分）、问答题（5分）。完成全部课程的学习，60分≤成绩＜85分者可申获得合格证书，成绩≥85分者可获得优秀证书。

Q2：北京航空航天大学《计算理论》课程教学、考核过程与本MOOC平台的教学、考核过程一样吗？

A2：北京航空航天大学网络空间安全学院研究生《计算理论》课程的学习成绩由出勤成绩10%、平时作业20%、期中成绩30%和期末成绩40%四部分组成。本MOOC平台开课的教学、考核内容主要是理论教学与测验，与线下课程基本一致，但题目类型略有不同。

Q3：本课程的教学视频每周什么时间更新？

A3：教学视频和章节测试、作业均每周更新，更新信息详见功能栏中的教学日历。

Q4：感觉MOOC中的视频清晰度不够怎么办？

A4：MOOC视频的清晰度选择有三种：标清、高清和超高清，如果学习时感觉教学视频不够清晰，建议重新选择清晰度（选项在视频的右下角），同时还可选择全屏浏览（选项在视频的右下角）。