前言FOREWORD
计算机科学与技术、软件工程、网络空间安全等计算机类学科，统称为计算学科。学科通过在计算机上建立模型和系统，模拟实际过程进行科学调查和研究；通过数据搜集、存储、传输与处理等进行问题求解，包括科学、工程、技术和应用4部分。其科学部分的核心在于通过抽象建立模型实现对计算规律的研究；其工程部分的核心在于根据规律低成本地构建从基本计算系统到大规模复杂计算应用系统的各类系统；其技术部分的核心在于研究和发明用计算进行科学调查和研究中使用的基本手段和方法；其应用部分在于构建、维护和使用计算系统实现特定问题的求解。其根本问题是什么能且如何被有效地自动计算，而计算的自动化，均以问题描述和处理的符号化为基础。从事计算机科学研究、工程设计、开发、运行、应用、维护的计算机人才都不例外。也正因为如此，才有人用问题抽象、系统抽象、数据抽象来表述对计算机类专业人才的基本要求。2016年6月2日，在吉隆坡召开的国际工程联盟大会上，中国获全票通过，正式加入《华盛顿协议》，成为第18个正式成员，这被认为是中国高等教育取得的具有里程碑意义的历史性突破。该协议虽然是针对本科教育的，但对我们按照工程教育的要求，不断提升研究生教育的水平与质量也是很重要的。根据《华盛顿协议》，工程被定义为包括数学、自然科学和工程知识、技术和技能整体的、有目的性的应用。可见，工程对基础的强调。另外，《华盛顿协议》还规定，两年制的专科教育旨在培养学生解决狭义工程问题的能力，三年制专科旨在培养学生解决广义工程问题的能力，本科教育则聚焦培养学生解决复杂工程问题的能力。所谓的复杂工程问题是满足如下条件的工程问题：1 必须运用深入的工程原理经过分析才可能解决；2 需求涉及多方面的技术、工程和其他因素，并可能相互有一定冲突；3 需要通过建立合适的抽象模型才能解决，在建模过程中需要体现出创造性；4 不是仅靠常用方法就可以完全解决的；5 问题中涉及的因素可能没有完全包含在专业标准和规范中；6 问题相关各方利益不完全一致；7 具有较高的综合性，包含多个相互关联的子问题。作为本科教育后继的研究生教育，显然应该在本科教育的基础上开展。但是目前存在的问题是，很多年来，由于各方面的限制，部分专业点的教育还很难说达到了这一基本定位的要求，表现出来的现象是，进入研究生阶段学习的学生在对深入原理的掌握、分析方法的掌握，从而具有分析能力以及建立合适的抽象模型并且在建模过程中需要体现出创造性等方面都存在一定的差距。建模能力是如此之重要，以至于《华盛顿协议》还明确要求包括机械、电子、化工、建筑等在内的所有工科专业的教育都要包括数学、数值分析、统计，以及计算机和信息科学关于形式化方面的基本内容，以支持学科问题的分析和建模（WK2： mathematics and computerconceptuallybased mathematics, numerical analysis, statistics and formal aspects of computer and information science to support analysis and modeling applicable to the discipline）。作为培养工程应用型人才为主的计算机类学科专业，更应如此。而形式语言与自动机理论则是培养学生这些方面能力的非常恰当的重要载体。希望通过这类课程的教育，支持这一要求的达成，同时促进学生在基础理论上更好地达到我国学位条例中 在本门学科上掌握坚实的基础理论和系统的专门知识的要求。另外，从复杂工程问题的定义不难看出，解决这类问题，需要有扎实的基础理论和深入的原理性知识，同时要强调对基本理论的应用。所以，包括研究生教育在内，需要追求理论指导下的、非简单的、高水平实践能力的培养，以追求高水平动脑指挥下的问题求解（实践、动手）。落实到本教材对应的课程教育，绝不仅仅是要让学生掌握其基本知识，而是要以这些知识为载体，使学生掌握其中的思想和典型方法，培养他们模型描述和模型计算的意识和能力。为此，要开展研究型的教与学： 教师在对问题的研究中教，学生在对未知的研究中学，努力体现基于产出（outcomebased education，OBE）的基本教育观点，纠正基于课程的教育观点（curricularbased education，CBE）。为了达到这一目的，在本书的写作中，我们除了以定义、定理、算法的形式叙述基本概念和结论外，还尽力进行相关的问题分析。希望读者不要限于简单地记忆定义、定理和相应的算法，要通过深入的分析，掌握相关的知识、思想和方法。多提问题，多想问题，这样才能有真正的收获。本书是基于国家精品教材《形式语言与自动机》编著的，重点考虑了研究生教育的需求，全书共分9章。第1章介绍语言和文法，包括相关的基本概念、文法的构造、Chomsky体系、左线性文法和右线性文法。第2章讨论有穷状态自动机，包括有穷状态自动机的定义、描述、构造方法，确定的、非确定的、带空移动的有穷状态自动机以及与正则文法的等价性。第3章研究正则表达式及其与有穷状态自动机的等价性。第4章讨论正则语言的性质，包括正则语言的泵引理、封闭性、MyhillNerode定理、极小化、判定算法。第5章为上下文无关语言，包括文法二义性、派生树、化简、Chomsky范式和Greibach范式。第6章讨论下推自动机，包括基本定义和构造方法以及下推自动机与上下文无关文法的等价性。第7章是上下文无关语言的性质，包括上下文无关语言的泵引理、Ogden引理、封闭性、判定算法。第8章介绍图灵机，包括基本定义、接受的语言、构造技术、通用图灵机、ChurchTuring论题、图灵机的变形、可计算语言、不可判定性、PNP问题。第9章介绍上下文有关语言，包括图灵机与短语结构文法的等价性，以及线性界限自动机的定义及与上下文有关语言的关系。书中难免存在不足，请读者不吝赐教。联系地址： jiangzl@bjut.edu.cn。
作者2017年1月
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
