计算理论是关于计算知识的有系统的整体,本是数学的一个研究领域,诞生于数理逻辑学家对计算本质的探索。这里的计算 (Computation) 并不是指纯粹的算术 (Calculation),而是指一种以 “机械而有效的” 方式获取问题答案的过程。随着计算理论的发展最终促使了计算机的发明,计算理论的重心也从数学转到了计算机科学,而计算理论关心的核心问题是:
计算(机)的基本能力和限制究竟是什么?
这个问题中包含了两个内容,分别对应计算理论的两个研究方向:可计算性理论和计算复杂性理论, 而形式语言与自动机理论正是这两个重要的研究方向的理论基础。
为了能够严谨的研究这种机械而有效的计算过程,我们需要严格定义的概念去描述它,需要严谨的计算模型去分析它。这个概念,其实就是已经被我们大家所熟知的“算法”(Algorithm);而这些模型呢,就是我们将要在课程中主要学习的自动机理论,包括有穷自动机、下推自动机和图灵机等几种自动机装置,还包括一些与自动机形式上不相似但能力上却完全相同的模型,如正则表达式和文法等。
形式语言与自动机理论是计算机科学与技术领域基本的思想和方法,它不仅是编译技术的基础,在诸如计算机网络协议、文件搜索、数字电路设计和验证等诸多领域也发挥着重要作用。本课程旨在培养学生形式化描述和抽象思维能力,掌握“问题——形式化描述——自动化(计算机求解)”的思想和方法,并用于解决实际问题。
课程目标1:掌握正则语言与上下文无关语言等语言的形式化描述方法和识别方法,能够设计与之相应的文法和自动机,培养学生的抽象思维能力和逻辑思维能力。
课程目标2:分类研究语言的性质,培养针对不同语言的模型描述能力和模型计算能力(包括模型的等价变换、推理等),能够在更高的抽象层面处理复杂工程问题,进而尝试探讨问题的可计算性及其计算的复杂性。
课程目标3:掌握由问题到形式化描述、再到计算机化的问题求解方法,能够对实际问题进行抽象、形式化,构建计算模型,进而用计算机予以解决。
集合论与图论
为积极响应国家低碳环保政策, 2021年秋季学期开始,中国大学MOOC平台将取消纸质版的认证证书,仅提供电子版的认证证书服务,证书申请方式和流程不变。
电子版认证证书支持查询验证,可通过扫描证书上的二维码进行有效性查询,或者访问 https://www.icourse163.org/verify,通过证书编号进行查询。学生可在“个人中心-证书-查看证书”页面自行下载、打印电子版认证证书。
完成课程教学内容学习和考核,成绩达到课程考核标准的学生(每门课程的考核标准不同,详见课程内的评分标准),具备申请认证证书资格,可在证书申请开放期间(以申请页面显示的时间为准),完成在线付费申请。
认证证书申请注意事项:
1. 根据国家相关法律法规要求,认证证书申请时要求进行实名认证,请保证所提交的实名认证信息真实完整有效。
2. 完成实名认证并支付后,系统将自动生成并发送电子版认证证书。电子版认证证书生成后不支持退费。
Introduction to Automata Theory, Languages, and Computation - 3rd Edition
作者 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
国内影印版
《自动机理论、语言和计算导论》(英文版·第3版)
机械工业出版社,ISBN: 9787111223924
Introduction to the Theory of Computation
作者 Michael Sipser
中文译版《计算理论导引》机械工业出版社
An Introduction to Formal Languages and Automata
作者 Peter Linz & Susan H. Rodger