当前课程知识点：软件理论基础 > 第一章 基础知识 > 1.1 概要 > 第一节
同学们好
欢迎来到《软件理论基础》Mooc课堂
我是清华大学的教师 罗贵明
由我讲授《软件理论基础》这门课
今天讲第一章 基础知识
内容包括：概要、数学基础、图
证明方法、语言基础
最后介绍语言运算
首先介绍这门课的概要
大家对计算机软件非常熟悉
这是一门新型的学科
然而它的发展可以追溯到
200年前英国的数学家--阿达
阿达建立了循环子程序的概念
为计算机拟定了“算法”
她写了第一份“程序设计流程图”
被视为“第一位给计算机写程序的人”
另外一位科学家图灵
早在上个世纪30年代
他已经建立了计算机及软件的架构
软件现在发展十分迅速
在很多领域，像航天、火车
核电、汽车、手机、银行、照相机，等等
众多领域都要用到软件
所以软件无处不在
软件可以定义世界
可见软件现在
发展多么广泛、多么普及
软件的发展如此的迅速
特别近些年来
作为一门学科
软件有哪些内容？
作为软件的理论，应该研究哪些内容？
我们应该关注软件的架构、软件的规范
哪些问题是可以计算的？
哪些问题是不可以计算的？
也是可判定性问题
在可计算中，要关注
计算的复杂度
这门课
要关注哪些内容呢？
第一，正则语言
描述这个语言的自动机
要关注
DFA、NFA、以及它们之间的关系
它们的优化
还要关注正则语言另外的表示
像正则表示、正则文法
以及正则语言的性质
第二，上下文无关语言
描述这个语言的下推自动机
DPDA，以及它们之间的关系
还要关注描述这个语言的
上下文无关文法
文法的规范、以及上下无关语言的一些性质
第三，递归可枚举语言
描述它的自动机是 Turing 机
关注 Turing 机的拓展、Turing 计算
还要介绍递归语言
判定性问题，以及算法的复杂性问题
另外，介绍一些非递归可枚举语言
我们要介绍语言的一些描述
给了自动机
给了一些工程问题。怎样描述语言？
介绍文法和自动机
怎么设计？
有哪些应用？
特别在现在的软件中
像软件的建模、软件的检测，等等
这都是课程内要介绍的内容
这课用到一些参考书
第一个参考书是《软件理论基础》
由科学出版社出版
第二个是 Hopcroft 等人编写的
《自动机理论、语言、及计算导论》
第三本参考书是 Linz 编写的
《形式语言和自动机导论》
学习这门课
希望大家做到课前预习、课后复习
这课要布置作业
大家要按时完成作业
最重要的是
按照学堂在线的学习要求
和考核要求
当然，目标是希望大家学好这门课
这节内容介绍完毕
谢谢大家！
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
