《形式语言与自动机理论》由会员分享，可在线阅读，更多相关《形式语言与自动机理论（10页珍藏版）》请在金锄头文库上搜索。
1、理论计算机科学基础,课程介绍,信息与计算科学专业,培养 解决信息技术中所涉及的数学问题的高级人才。 信息技术：信息的获取、传输和处理。 信息获取：统计、遥感。 信息传输：通信、Internet主要的问题：可靠性、有效性与安全性。数学理论：信息论、编码理论、密码学。 信息处理：计算技术，包括数值计算、符号计算、数据挖掘、计算模拟等技术。应用广泛，如：银行金融风险的控制、产品设计、天气预报、密码破译。,计算理论与技术,本专业的主要目标：掌握计算理论与技术；能够为各种实际问题设计算法，并用计算机求解。 主要工作：（1）建模，（2）算法设计与分析。 课程体系：1. 数学基础，离散数学，概论与统计，数值
2、计算，运筹与优化，数学建模。2. 计算理论，数据结构，算法设计与分析。3. 程序语言。4. 数学建模，算法设计与编程训练。,理论计算机科学,研究计算理论与技术，是关于计算技术的数学理论。 核心理论：（1）形式语言与自动机理论，（2）可计算性理论，（3）计算复杂性理论。 其中，形式语言与自动机理论是基础，是本课程的学习内容，包括如下3部分：（1）正规语言与有限自动机，（2）上下文无关语言与下推自动机，（3）图灵机与可判定性理论。,理论渊源,形式语言理论是美国语言学家乔姆斯基开创的。上个世纪50年代，乔姆斯基研究如何根据语法规则生成一个语言的所有语句，提出了形式化的文法概念与文法推导方法。他提出的
3、方法类似于逻辑推导。 同一时期，数学家克林研究如何自动地识别一个语言的所有语句。克林根据神经细胞的启发提出了识别语言的自动机模型。 1959年，乔姆斯基证明了两者是等价的，即文法所生成的语言都是自动机可识别的，反之亦然。这一结果宣告了形式语言与自动机理论的诞生。 此后，该理论在计算机科学技术中得到迅速而广泛的应用。例如，用形式化的文法描述高级编程语言的词法和语法；根据自动机设计编译器。,课程特点,本课程属于专业理论课，主要特点就是形式化，比较抽象，既有严格的理论证明，又有很强的构造性，难度较大。,学习目的,掌握形式语言与自动机理论的基本知识，为进一步的学习和应用打基础。 训练形式化思维。用规范的语言，严谨地描述事物；考虑事物的形式而非内涵。 训练计算思维。“建模 问题分析 算法设计 算法分析。” 考虑：问题的可计算性与计算复杂性，追求高效率的算法。,习题与实验,每一讲都布置适量的习题作为课后作业，用于理解、消化所学的知识。不安排实验。理论学习必须做习题。,考试与成绩评定,开卷笔试成绩评定总评成绩=平时20%+期末考试80%。平时成绩=考勤10分+作业10分。全班成绩分布：20% : 30% : 30% : 20%,教学参考书,蒋宗礼、姜守旭编著形式语言与自动机理论（第2版）清华大学出版社，2007。 王柏 杨娟编著 形式语言与自动机北京邮电大学出版社，2008。,
