博文
有穷自动机_1(2010-04-20 21:34:00)
摘要：NFA(不确定的有限自动机)与DFA(确定的有限自动机)
DFA的定义：
一个确定的有限自动机(DFA)M是一个五元组：M(S,∑,f,S0,Z)
S:代表一个有限状态集合。
∑：代表一个字母表,它的每个元素称为一个输入字符。 f：代表......
正规文法转为正规式的规则(2010-04-20 21:09:00)
摘要：正规式：也叫正则表达式，它是一种表达正规集的工具。一个正规式对应一个正规文法。
正规文法转换成正规式：
规则1：A→xB,B→y A→xy
规则2：A→xA|y A→x*y(*代表0到无穷个x)规则3：A→x,A→y A→x|y......
编译原理中的文法类型(2010-04-20 19:59:00)
摘要：文法类型：
0型文法：对于推导式α→β,那么α∈(Vn∪Vt)*且至少含有一个非终结符，β∈(Vn∪Vt)*，则该推导式属于~。
1型文法：也叫上下文有关文法，此文法对应线性有界自动机。1型文法在0型文法的基础上满足|β|>=|α|,则该推导式属于~。||代表长度。
2型文法：也叫上下文无关文法，它对应下推自动机。2型文法在1型文法的基础上满足推导式(α→β)的左侧都是非终结符。
3型文法：也叫正规文法，它对应有限状态自动机。它在2型文法的基础上满足A→a|aB(一个非终结符推导出一个终结符或一个终结符带一个非终结符。右线性)，A→a|Ba(左线性)。
|代表“或”的意思。......
堆排序(2010-04-15 22:49:00)
摘要： 什么是堆？
堆是以完全二叉树形式存储的一组数据。
堆排序步骤
1、建立堆
用层次遍历的方式将一组数值构建成一棵树。
2、调整堆
刚建立的树是未完成排序的，需要对构建好的树进行调整。这里需要先了解2个概念：
大顶堆，小顶堆。
什么是大顶堆、小顶堆呢？如果我们用层次遍历的方式从数值1开始依次对第一步建成的树的顶点给一个标号的话，那么大顶堆需要满足以下条件：1号顶点的值>=2号顶点的值>=3号顶点的值，如果顶点的标号用变量i表示的话可推导出以下公式：i>=2i>=2i+1。小顶堆则刚好相反，可表示为i<=2i<=2i+1。
虽然明白了上面的定义，但是现在还是不能下手对第一步构建的树进行调整。因为上面的定义只告诉了我们排序完成后的堆是什么样子的，还差了一把让我们动手的钥匙。
现在让我们来分析一下这把钥匙是什么？一个完全二叉树有以下特性：顶点总数/2+1的顶点是叶子节点，而且由于树的存储结构是单向的，叶子节点没有指向父节点的指针。所以要比较节点值大小的话一定要从一个父节点开始。如果一棵树的节点数为n的话，那我们就应该从n/2号顶点开始比较。但是假如n是一个奇数呢？那我们就直接取整。至于原因大家画一个5或9个节点的树分析一下就知道了。
好了正式动手，按大顶堆排序调整这棵树吧。方法如下：
1、假如有该父节点只有一个孩子节点，且父节点值>孩子节点。不用调整
2、假如有该父节点只有一个孩子节点，且父节点值<孩子节点。值互换
3、假如有该父节点有两个孩子节点，且父节点值>2个孩子节点。不用调整
4、假如有该父节点有两个孩子节点，且父节点值<2个孩子节点。和最大值的孩子......
常用内部排序算法及分类(2010-04-15 21:19:00)
摘要：1、插入排序(直接插入，希尔排序)
2、选择排序(简单选择，堆排序)
3、交换排序(冒泡，快速排序)
4、归并排序
5、基数排序......
AOE网，关键路径(2010-04-14 22:14:00)
摘要：边带权值的AOV网称为AOE网。
关键路径的重要概念：
1、顶点j事件的最早发生时间：从源点到顶点J的最长路径长度。记做：Ve(j)
2、活动ai的最早开始时间：顶点j的出度所代表的活动ai的最早开始时间等于j的最早发生时间。记做：e(i)
3、顶点j事件的最迟发生时间：在不推迟整个工程完工的前提下，事件j允许最迟的发生时间。记做：Vl(j)
4、活动ai的最迟开始时间：Vl(j)-(ai所需时间),就是活动ai的最迟开始时间。记做：l(i)......
AOV网和拓扑排序(2010-04-14 21:17:00)
摘要：把用顶点表示活动有向边表示活动之间开始的先后关系的有向图，简称为AOV网。
拓扑排序，是求拓扑序列 的过程。
过程如下：
1、先找到图中入度为零的顶点
2、完成该活动后删除代表该活动顶点的所有出度，然后继续找入度为零的顶点。
3、拓扑序列不是唯一的。......