文档库 最新最全的文档下载
当前位置:文档库 › 离散14-answer

离散14-answer

离散14-answer
离散14-answer

江苏技术师范学院20—20 学年第 学期 《离散数学》试卷(14)参考答案与评分标准 一、单项选择题(本大题共10道小题,每小题2分,共20分) 1. 下列四句话中是命题的是( D )。 A.今天有足球赛吗? B.好冷啊! C.我正在说谎。 D.我是大学生。 2. 设P :我买电脑,Q :我有钱。“我买电脑当且仅当我有钱”符号化为( A )。 A.P ?Q B.Q →P C.P ∨Q D.P ∧Q 3. 若无向图E V G ,=为树,其中n V =,m E =,则G 等价于以下叙述中的(A )。 A .G 连通且1+=m n B .G 连通且1+=n m C .当且仅当G 连通 D .当且仅当G 无回路 4. N 是自然数集合(包括0在内),代数系统的单位元是( B )。 A.1 B. 0 C. 0和1 D. 不存在 5. 谓词公式)()),()()()((x Q x y R y x P x →?∨?中变元x 是( C )。 A.自由变元 B.约束变元 C.既是自由变元又是约束变元 D.既不是约束变元又不是自由变元 二、填空题(本大题共10空,每空2分,共20分) 1. 设M (x ):x 是人,G (x ):x 犯错误;则命题“没有不犯错误的人”的符号化形式为: ))()((x G x M x ?∧?? 或 ))()((x G x M x →? 。 2. 谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x 的辖域是 P(x)∨?yR(y) 。 3. A={1,2,3},A 上关系R 的关系矩阵为??????????101011001,则R= {<1,1>,<2,1>,<2,2>,<3,1>,<3,3>} 。 4. B={{a,b},{b}},则B 的幂集P(B)= {Φ,{{a,b}},{{b}},{{a,b},{b}}} 。 5. 群(Z 6,+6)的所有子群 ,<{0,2,4},+6>,<{0,3},+6>,<{0},+6> 。 6. R 是实数集合,代数系统,任一实数x 的逆元x -1 = -x 。 装

线

班级

7.已知无向图G有12条边,1度顶点有2个,2度、3度、5度顶点各1个,其余

顶点度数均为4,则4度顶点的个数为 3 。

8.设个体域为整数集合Z,命题?x?y(x-y=9)的真值为_____1______。

9.设p:2+2=4,q:3+3=7,r:4+4=8,则公式()()r

?

∨的真值为0 。

p∧

q

p

q

10. R={|x-y=1,x∈A,y∈A}是定义在集合A={1,2,3,4,5}上的关系,则R的性质为

反自反、反对称。

1. 三、判断题(本大题共10小题,每小题1分,共10分)

正确的打“√”,错误的打“×”

1.(√)110是命题公式()r

?的成假赋值。

p→

q

2.(×)X∩Y=X∩Z => Y=Z。

3.(×)一条通过图中所有边一次且恰好一次的回路是哈密尔顿回路。

4.(×)设A,B,C是三个命题公式,如果B

∨,则C

?

A?。

C

B

A∨

5.(√)自然数集上二元运算*定义为:)

y

*,则*是可结合的。

x=

x

,

max(y

6.(×)欧拉回路是初级回路。

7.(×)群中必定有零元和单位元。

8.(×)设A,B为无限集,则A-B是空集。

9.(×))

P

x

Q

x?

?。

xP

?

?

x

))

(

)

x

(

(

xQ

)

(x

(

10.(√)集合A上全域关系是等价关系。

四、证明题(本大题共4小题,第1小题6分,第2-4小题各8分,共30分)

1.设A、B、C是三个集合,证明:A?B=A?(B-A)

证明:A?(B-A)=A?(B?~A)=(A?B)?(A?~A)=A?B (6分)

2.证明不存在具有奇数个面且每个面都具有奇数条棱的多面体。

证明:用反证法. 假设存在这样的多面体, 作无向图G=,

其中V={v | v为多面体的面},

E={(u,v) | u,v∈V∧u与v有公共的棱∧u≠v}.(4分)

根据假设, |V|为奇数且?v∈V, d(v)为奇数. 这与握手定理的推论矛盾。(4分)

3.在谓词逻辑中符号化下述命题,并推证之:

无理数都不能表示成分数,3.1415能表示成分数。所以3.1415不是无理数。

证明:设F(x):x是无理数,G(x):x能表示成分数,a:3.1415 (2分)

前提:?x(F(x)→?G(x)),G(a);

结论:?F(a) (2分)

证明:

① G(a) 前提引入

②?x(F(x)→?G(x)) 前提引入

③ F(a)→?G(a) ②UI规则

④?F(a) ①③拒取(4分)

4.在命题逻辑中构造下面推理的证明:

如果小张守第一垒并且小李向B队投球,则A队获胜。或者A队未获胜,或者A队成为联赛的第一名。小张守第一垒。A队没有成为联赛的第一名。因此小李没有向B队投球。

解:先将简单命题符号化。P:小张守第一垒;Q:小李向B队投球;R:A队取胜;S:A队成为联赛第一名。(2分)

前提:(P∧Q)→R,R∨S,P,S

结论:Q (2分)

证明:

(1) R∨S 前提引入

(2) S 前提引入

(3) R (1)(2)析取三段论

(4) (P∧Q)→R 前提引入

(5) (P∧Q) (3)(4)拒取式

(6) P∨Q (5)置换

(7) P 前提引入

(8) Q (6)(7)析取三段论(4分)

五、计算、应用题(本大题共4小题,第1-3小题各6分,第4小题12分,共30分)

1. 设集合A ={2,4,6,8,10,12},B={2,4,6},从A 到B 的关系R ={|x=2y},求R

和R -1。

解:(1)R={<4,2>,<8,4>,<12,6>} (3分)

(2)R 1-={<2,4>,<4,8>,<6,12>} (3分)

2. 求公式p r q p →→∨))((的析取范式和合取范式。

解:原式?()()p r q p ∨∨∨???()()()p r q p ∨?∧∨??

?()()p r q p ∨?∧∨?()()p r q r p ∨?∧∨?∧ (3分)

上式即原式的析取范式,再利用第三步的结论,即:

原式?()()p r q p ∨?∧∨?()()p r p q p ∨?∧∨∨?()()r p q p ?∨∧∨

即原式的合取范式。 (3分)

3.求以1,3,4,5,6权为的最优2元树,

要求写出步骤并计算它的权。

(4分)

W(T)=(1+3)*3+(4+5+6)*2=42 (2分)

4.已知有向图G 的邻接矩阵为

A=???

?

?

?

??????0111001111001010

(1)画出图G 并说出此图有几条边。(4分)

(2)v1到v3长为3的通路有多少条?v1到自身长为3的回路有多少条?(

4分) (3)此图是强连通还是单向连通图?(4分)

解:(1)图G 如下:(2分) 该图有9条边(2分)

(2)

A 2=????????????2121211001221211 A 3=?????

???????3443133342312243 v4到v2长为3的通路有4条。 (2分)

v1到自身长为3的回路有3条。 (2分)

(3)此图是强连通图。(4分)

附加题:在通信中,设八进制数字出现的频率(%)如下:

0: 25, 1: 20, 2: 15, 3: 10, 4: 10, 5: 10, 6: 5, 7: 5

采用2元前缀码,求传输数字最少的2元前缀码 (称作最佳前缀码),并求传输100个按上述比例出现的八进制数字需要多少个二进制数字?若用等长的(长为3)的码字传输需要多少个二进制数字?(要求画出最优2元树)

解:用Huffman 算法求以频率(乘以100)为权的最优2元树.

这里w 1=5,w 2=5,w 3=10,w 4=10,w 5=10,w 6=15,w 7=20,w 8=25.

编码:0---01,1---11,2---001,3---100,4---101,5---0001,6---00000

,7---00001 1 2

3

4

传100个按比例出现的八进制数字需W(T)=285个二进制数字,用等长码(长为3)需要用300个数字.

离散系统稳定性分析

实验一 离散系统稳定性分析 实验学时:2 实验类型:常规 实验要求:必作 一、实验目的: (1)掌握利用MATLAB 绘制系统零极点图的方法; (2)掌握离散时间系统的零极点分析方法; (3)掌握用MATALB 实现离散系统频率特性分析的方法; (4)掌握逆Z 变换概念及MATLAB 实现方法; (5)掌握用MATLAB 分析离散系统稳定性。 二、实验原理: 1、离散系统零极点图及零极点分析; 线性时不变离散系统可用线性常系数差分方程描述,即 ()()N M i j i j a y n i b x n j ==-= -∑∑ (8-1) 其中()y k 为系统的输出序列,()x k 为输入序列。 将式(8-1)两边进行Z 变换的 00 ()()()() () M j j j N i i i b z Y z B z H z X z A z a z -=-== = = ∑∑ (8-2) 将式(8-2)因式分解后有: 11 () ()() M j j N i i z q H z C z p ==-=- ∏∏ (8-3) 其中C 为常数,(1,2,,)j q j M = 为()H z 的M 个零点,(1,2,,)i p i N = 为()H z 的N 个极点。 系统函数()H z 的零极点分布完全决定了系统的特性,若某系统函数的零极点已知,则系统函数便可确定下来。 因此,系统函数的零极点分布对离散系统特性的分析具有非常重要意义。通过对系统函数零极点的分析,可以分析离散系统以下几个方面的特性: ● 系统单位样值响应()h n 的时域特性; ● 离散系统的稳定性;

离散系统的频率特性; 1.1、零极点图的绘制 设离散系统的系统函数为 ()()() B z H z A z = 则系统的零极点可用MA TLAB 的多项式求根函数roots()来实现,调用格式为: p=roots(A) 其中A 为待根求多项式的系数构成的行矩阵,返回向量p 则是包含多项式所有根的列向量。如多项式为231()4 8 B z z z =+ + ,则求该多项式根的MA TLAB 命令为为: A=[1 3/4 1/8]; P=roots(A) 运行结果为: P = -0.5000 -0.2500 需注意的是,在求系统函数零极点时,系统函数可能有两种形式:一种是分子、分母多项式均按z 的降幂次序排列;另一种是分子、分母多项式均按1z -的升幂次序排列。这两种方式在构造多项式系数向量时稍有不同。 (1)()H z 按z 的降幂次序排列:系数向量一定要由多项式最高次幂开始,一直到常数项,缺项要用0补齐;如 3 4 3 2 2()3221 z z H z z z z z += ++++ 其分子、分母多项式系数向量分别为A=[1 0 2 0]、B=[1 3 2 2 1]。 (2)()H z 按1z -的升幂次序排列:分子和分母多项式系数向量的维数一定要相同,不足的要用0补齐,否则0z =的零点或极点就可能被漏掉。如 1 1 2 12()11124 z H z z z ---+= + + 其分子、分母多项式系数向量分别为A=[1 2 0]、B=[1 1/2 1/4]。 用roots()求得()H z 的零极点后,就可以用plot()函数绘制出系统的零极点图。下面是求系统零极点,并绘制其零极点图的MA TLAB 实用函数ljdt(),同时还绘制出了单位圆。 function ljdt(A,B) % The function to draw the pole-zero diagram for discrete system p=roots(A); %求系统极点 q=roots(B); %求系统零点 p=p'; %将极点列向量转置为行向量

离散事件模拟

//离散事件模拟,模拟银行营业时的排队情况 //不考虑顾客中途离开,顾客到达事件随机,业务办理时间 //长度随机,选择最短的队排队,不再换队 //作者:nuaazdh //时间:2011年12月10日08:52:37 #include #include #include #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; typedef struct Event{ //事件类型 int OccurTime; //事件发生时刻 int NType; //事件类型,0表示到达事件,1至4表示四个窗口的离开事件 struct Event *next; }Event,ElemType; typedef struct{ //单向链表结构 ElemType *head;//头指针 ElemType *tail;//尾指针 int len; //长度 }LinkList; typedef LinkList EventList; //事件链表 typedef struct QElemType{ //队列元素 int ArriveTime;//到达时间 int Duration;//办理业务所需时间 struct QElemType *next; }QElemType; typedef struct{//队列结构 QElemType *head;//头指针 QElemType *tail;//尾指针 }LinkQueue; Event NewEvent(int occurT,int nType); //根据OccurTime和NType值,创建新事件 Status InitList(LinkList *L);

离散方法分类

离散方法分类 有限差分法 微分方程和积分微分方程数值解的方法。基本思想是把连续的定解区域用有限个离散点构成的网格来代替,这些离散点称作网格的节点;把连续定解区域上的连续变量的函数用在网格上定义的离散变量函数来近似;把原方程和定解条件中的微商用差商来近似,积分用积分和来近似,于是原微分方程和定解条件就近似地代之以代数方程组,即有限差分方程组,解此方程组就可以得到原问题在离散点上的近似解。然后再利用插值方法便可以从离散解得到定解问题在整个区域上的近似解。 有限差分法求解偏微分方程的步骤如下: 1、区域离散化,即把所给偏微分方程的求解区域细分成由有限个格点组成的网格; 2、近似替代,即采用有限差分公式替代每一个格点的导数; 3、逼近求解。换而言之,这一过程可以看作是用一个插值多项式及其微分来代替偏微分方程的解的过程. 如何根据问题的特点将定解区域作网格剖分;如何把原微分方程离散化为差分方程组以及如何解此代数方程组。此外为了保证计算过程的可行和计算结果的正确,还需从理论上分析差分方程组的性态,包括解的唯一性、存在性和差分格式的相容性、收敛性和稳定性。对于一个微分方程建立的各种差分格式,为了有实用意义,一个基本要求是它们能够任意逼近微分方程,这就是相容性要求。另外,一个差分格式是否有用,最终要看差分方程的精确解能否任意逼近微分方程的解,这就是收敛性的概念。此外,还有一个重要的概念必须考虑,即差分格式的稳定性。因为差分格式的计算过程是逐层推进的,在计算第n+1层的近似值时要用到第n层的近似值,直到与初始值有关。前面各层若有舍入误差,必然影响到后面各层的值,如果误差的影响越来越大,以致差分格式的精确解的面貌完全被掩盖,这种格式是不稳定的,相反如果误差的传播是可以控制的,就认为格式是稳定的。只有在这种情形,差分格式在实际计算中的近似解才可能任意逼近差分方程的精确解。关于差分格式的构造一般有以下3种方法。最常用的方法是数值微分法,比如用差商代替微商等。另一方法叫积分插值法,因为在实际问题中得出的微分方程常常反映物理上的某种守恒原理,一般可以通过积分形式来表示。此外还可以用待定系数法构造一些精度较高的差分格式。 有限容积法 有限容积法(Finite V olume Method)又称为控制体积法。 其基本思路是:将计算区域划分为一系列不重复的控制体积,并使每个网格点周围有一个控制体积;将待解的微分方程对每一个控制体积积分,便得出一组离散方程。其中的未知数是网格点上的因变量的数值。为了求出控制体积的积分,必须假定值在网格点之间的变化规律,即假设值的分段的分布的分布剖面。从积分区域的选取方法看来,有限体积法属于加权剩余法中的子区域法;从未知解的近似方法看来,有限体积法属于采用局部近似的离散方法。简言之,子区域法属于有限体积法的基本方法。有限体积法的基本思路易于理解,并能得出直接的物理解释。离散方程的物理意义,就是因变量在有限大小的控制体积中的守恒原理,如同微分方程表示因变量在无限小的控制体积中的守恒原理一样。限体积法得出的离散方程,要求因变量的积分守恒对任意一组控制体积都得到满足,对整个计算区域,自然也得到满足。这是有限体积法吸引人的优点。有一些离散方法,例如有限差分法,仅当网格极其细密时,离散方程才满足积分守恒;而有限体积法即使在粗网格情况下,也显示出准确的积分守恒。就离散方法而言,有限体积法可视作有限单元法和有限差分法的中间物。有限单元法必须假定值在网格点之间的变化规律(既插值函数),并将其作为

离散事件建模及仿真

第7章离散事件系统建模与仿真 离散事件系统指的是一组实体为了达到某些目的,以某些规则相互作用、关联而集合在一起。与连续事件系统不同,离散事件系统所包含的事件在时间上和空间上都是离散的。离散事件系统在生产和生活中是很常见的,例如一个超市就是一个离散事件系统,它由顾客和收银员组成。在离散事件系统中,各事件以某种顺序或在某种条件下发生,并且大都是随机性的,所以,其模型很难用某种规范的形式,一般采用流程图或者网络图的形式来定义实体在系统中的活动。这类系统在建模时,只要考虑系统内部状态发生变化的时间点和发生这些变化的原因,而不用描述系统内部状态发生变化的过程。本章将介绍几种常见的离散事件系统和离散事件系统建模方法。 7.1 离散事件系统模型 离散事件系统是指系统的状态仅在离散的时间点上发生变化的系统,而且这些离散时间点一般是不确定的。这类系统中引起状态变化的原因是事件,通常状态变化与事件发生是一一对应的。事件的发生没有持续性,可以看作在一个时间点上瞬间完成,事件发生的时间点是离散的,因而这类系统称为离散事件系统。首先看一个典型的离散系统的例子。 例7.1 超市服务系统 某理发店只有一名理发师。在正常的工作时间内,如果理发店没有顾客,则理发师空闲;如果有顾客,则为顾客理发。如果顾客到达理发店时,理发师正在为其他顾客服务,则新来的顾客在一旁排队等候。显然,每个顾客到达理发店的时间是随机的,而理发师为每个顾客服务的时间也是随机的,进而队列中每个顾客的等候时间也是随机的。 下面,结合例7.1介绍一下在离散事件系统仿真中所用到的一些基本概念。 (1)实体 实体是指有可区别性且独立存在的某种事物。在系统中,构成系统的各种成分称为实体,用系统论的术语,它是系统边界内的对象。在离散事件系统中,实体可分为两大类:临时实体和永久实体。临时实体指的是只在系统中存在一段时间的实体,这类实体由系统外部到达系统,在系统仿真过程中的某一时刻出现,最终在仿真结束前从系统中消失。例7.1中,顾客是临时实体,他们按一定的规律到达,经过理发师服务(可能要排队等待一段时间),最终离开系统。那些虽然达到,但未进入理发店的顾客则不能称为该系统的临时实体。永久实

有限差分,有限元,有限体积等离散方法的区别介绍

有限差分,有限元,有限体积等等离散方法的区别介绍 一、区域离散化 所谓区域离散化,实质上就是用一组有限个离散的点来代替原来连续的空间。实施过程是;把所计算的区域划分成许多互不重迭的子区域,确定每个子区域的节点位置及该节点所代表的控制容积。节点:需要求解的未知物理量的几何位置;控制容积:应用控制方程或守恒定律的最小几何单位。一般把节点看成是控制容积的代表。控制容积和子区域并不总是重合的。在区域离散化过程开始时,由一系列与坐标轴相应的直线或曲线簇所划分出来的小区域称为子区域。网格是离散的基础,网格节点是离散化物理量的存储位置。 大家都知道,常用的离散化方法有:有限差分法,有限元法,有限体积法。 1. 有限差分法是数值解法中最经典的方法。它是将求解区域划分为差分网格,用有限个网格节点代替连续的求解域,然后将偏微分方程(控制方程)的导数用差商代替,推导出含有离散点上有限个未知数的差分方程组。这种方法发展比较早,比较成熟,较多用于求解双曲线和抛物线型问题。用它求解边界条件复杂、尤其是椭圆型问题不如有限元法或有限体积法方便。 2. 有限元法是将一个连续的求解域任意分成适当形状的许多微小单元,并于各小单元分片构造插值函数,然后根据极值原理(变分或加权余量法),将问题的控制方程转化为所有单元上的有限元方程,把总体的极值作为各单元极值之和,即将局部单元总体合成,形成嵌入了指定边界条件的代数方程组,求解该方程组就得到各节点上待求的函数值。对椭圆型问题有更好的适应性。有限元法求解的速度较有限差分法和有限体积法慢,在商用CFD软件中应用并不广泛。目前的商用CFD软件中,FIDAP采用的是有限元法。 3. 有限体积法又称为控制体积法,是将计算区域划分为网格,并使每个网格点周围有一个互不重复的控制体积,将待解的微分方程对每个控制体积积分,从而得到一组离散方程。其中的未知数十网格节点上的因变量。子域法加离散,就是有限体积法的基本方法。就离散方法而言,有限体积法可视作有限元法和有限差分法的中间产物。 4. 有限分析法:同有限差分法一样,用一系列网格线将区域离散,所不同的是每个节点与相邻8个邻点组成。在计算单元中把控制方程中的非线形项局部线形化,并对该单元上未知函数的变化型线作出假设,把所选定型线表达式中的系数和常数项用单元边界节点上未知的变量值来表示,这样该单元内的被求问题就转化为第一类边界条件下的一个定解问题,可以找出分析解;然后利用这一分析解,得出该单元中点及边界上8个邻点上未知值间的代数方程,此即为单元中点的离散方程。两种离散方法外节点法:节点在子域的四角,先定节点位置而计算相应的界面内节点法:节点在子域中心,子域与控制容积重合。计算时先定界面后算出节点位置。 5. 边界元法(Boundary Element Method,BEM)上面四种方法都必须对整个区域作离散化处理,用分布在整个区域上的有限个节点上函数的近似值来代替连续问题的解。在边界元方法中应用格林函数公式,并通过选择适当的权函数把空间求解域的偏微分方程转换成为其边界上的积分方程,它把求解区中任一点的求解变量(如温度)与边界条件联系了起来。通过离散化处理,由积分方程导出边界节点上未知值的代数方程。解出边界上的未知值后就可以利用边界积分方程来获得内部任一点的被求函数之值。边界元法的最大优点是,可以使求解问题的空间维数降低一阶,从而使计算工作量及所需计算机容量大大减小。边界元法推广应用的一个最大限制是,需要已知所求解偏微分方程的格林函数基本解。虽然对不少偏微分方程这种基本解业已找出,但对Navier-Stoles方程这样的非线性偏微分方程,至今尚未找到其基本解。目前的一种处理方式是,把Navier-Stokes方程中的非线性项看作是扩散方程的源项并通过迭代的方式来求解,但一般只能获得Re较低情形的解。最近文献中采用高阶涡量—流函数方程的边界元方法,已使获得顶盖驱动流稳定解的Re高达10000。 格子—Boltzmann方法(Lattice-Boltzmann method,LBM)格子—Boltzmann方法是基于分子运动论的一种模拟流体流动的数值方法。在上述各种数值方法中,把本质上是离散的介质先假定是连续的,在此基础上建立起了N-S方程,然后又再把它离散化。在LBM中不再基于连续介质的假设,而是把流体看成是许多只有质量没有体积的微粒所组成,这些微粒可以向空间若干个方向任意运动。通过其质量、动量守恒的

离散事件系统仿真实验

实验二离散事件系统仿真实验 目录 实验题目 (1) 一、实验目标 (1) 二、实验原理 (1) 1. 排队系统的一般理论 (1) 2. 离散系统常用的仿真策略 (2) 3. 本实验采用单服务台模型 (3) 4. 仿真运行方式 (3) 三、理论分析 (4) 1. 涉及的基本概念 (4) 2. 仿真的总体规划设计 (5) 四、建模过程 (7) 1. 思路分析 (7) 2. 仿真策略 (7) 3. 事件列表 (8) 4. 变量定义 (8) 5. 系统流程框图 (9) 五、仿真源程序(Matlab) (10) 六、结果分析 (12) 七、感受及建议 (15)

实验题目 实体(临时实体)到达模式:实体到达模式是顾客到达模式,设到达时间间隔Ai 服从均值5min A β=的指数分布 /1 ()(0) A A A f A e A ββ?=≥服务模式:设服务员为每个顾客服务的时间为Si .它也服从指数分布,均值为4min S β=/1 ()(0) S S s f S e S ββ?=≥服务规则:由于是单服务台系统,考虑系统顾客按单队排列,并按FIFO 方式服务 一、实验目标 通过单服务台排队系统的方针,理解和掌握对离散事件的仿真建模方法,以便对其他系统进行建模,并对其系统分析,应用到实际系统,对实际系统进行理论指导。 二、实验原理 1. 排队系统的一般理论 一般的排队系统都有三个基本组成部分:

(1)到达模式:指动态实体(顾客)按怎样的规律到达,描写实体到达的统计特性。通常假定顾客总体是无限的。 (2)服务机构:指同一时刻有多少服务设备可以接纳动态实体,它们的服务需要多少时间。它也具有一定的分布特性。通常,假定系统的容量(包括正在服务的人数加上在等待线等待的人数)是无限的。 (3)排队规则:指对下一个实体服务的选择原则。通用的排队规则包括先进先出(FIFO),后进先出(LIFO),随机服务(SIRO)等。 2. 离散系统常用的仿真策略 (1)事件调度法(Event Scheduling): 基本思想:离散事件系统中最基本的概念是事件,事件发生引起系统状态的变化,用事件的观点来分析真实系统。通过定义事件或每个事件发生系统状态的变化,按时间顺序确定并执行每个事件发生时有关逻辑关系。 (2)活动扫描法: 基本思想:系统有成分组成,而成分又包含活动。活动的发生必须满足某些条件,且每一个主动成分均有一个相应的活动例程。仿真过程中,活动的发生时间也作为条件之一,而且较之其他条件具有更高的优先权。 (3)进程交互法: 基本思想:将模型中的主动成分历经系统所发生的事件及活动,按时间发生的顺序进行组合,从而形成进程表。系统仿真钟的推进采

离散时间系统最优控制

第五章离散时间系统最优控制

引言 ?前面所讨论的都是关于连续时间系统的最优控制问题。?现实世界中,很多实际系统本质上是时间离散的。 机 ?即使是系统是时间连续的,因为计算机是基于时间和数值上都离散的数字技术的,实行计算机控制时必须 将时间离散化后作为离散系统处理。 ?因此,有必要讨论离散时间系统的最优控制问题。 ?离散时间系统仍然属于连续变量动态系统(CVDS)范畴。 注意与离散事件动态系统(DEDS)的区别。 ?CVDS与DEDS是自动化领域的两大研究范畴,考虑不同的自动化问题。

5.1 离散时间系统最优控制问题的提法 (1) 离散系统最优控制举例——多级萃取过程最优控制 ?萃取是指可被溶解的物质在两种互不相溶的溶剂之间的转移,一般用于将是指可被溶解的物质在两种互不相溶的溶剂之间的转移,般用于将要提取的物质从不易分离的溶剂中转移到容易分离的溶剂中。 ?多级萃取是化工生产中提取某种价值高、含量低的物质的常用生产工艺。 萃取V u (0) u (1) u (k -1) u (N -1) V V V V V V 萃取器1萃取器2 萃取器 k 萃取器N x (0) x (1)x (2) x (k -1) x (k ) x (N )x (N -1) 含物质z (0)z (1) z (k-1) z (N -1) 多级萃取过程 A 的混合物以流量V 进入萃取器1,混合物中A 浓度x (0); 萃取剂以流量u (0)通过萃取器1,单位体积萃取剂带走A 的量为z (0); 一般萃取过程的萃取物含量均较低,可认为通过萃取器1后混合物流量仍为V ; 流出萃取器1的混合物中A 物质的浓度为x (1)。以此类推至萃取器N 。

数据结构课程设计之银行离散事件模拟

《数据结构》课程设计报告

银行业务模拟与离散事件模拟 一、实验目的 1. 通过此次课程设计中银行业务模拟的题目,掌握队列(或者链表) 等数据结构的基本操作方面的知识,并能灵活的解决一些基本的问题,加深对其性质及各项操作的理解; 2. 将所学数据结构方面的知识与一门具体的语言相结合(C/C++)来进行实现,感受数据结构的强大作用,加深理解。 二、问题描述 1.问题描述 假设某银行有4个窗口对外接待客户,从早晨银行开门(开门9:00am,关门5:00pm)起不断有客户进入银行。由于每个窗口在某个时刻只能接待一个客户,因此在客户人数众多时需要在每个窗口前顺次排队,对于刚进入银行的客户(建议:客户进入时间使用随机函数产生),若某个窗口的业务员正空闲,则上前办理业务;反之,若4个窗口均有窗户所占,他便会排在人数最少的队伍后面。 2. 任务要求 编制一个程序以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间。建议有如下设置: (1)客户到达时间随机产生,一天客户的人数设定为100人。 (2)银行业务员处理时间随机产生,平均处理时间10分钟。 (3)将一天的数据(包括业务员和客户)以文件方式输出。 三、算法的思想与算法实现步骤 1. 基本思想 通过队列数据类型进行基本操作,主要有三个模块:分别是主函数模块、 主要操作函数及基本操作函数。其中,主函数负责其他子函数的调用实现以及基本界面的操作,主要函数包括开门函数的实现:OpenForDay,顾客到达函数:CustomerArrived,顾客离开的函数:CustomerDepartion等;而基本操作函数

就是对其中牵扯到的操作进行具体的实现,如按时间先后插入队列OrderInsert、寻求最短的队列MinCuQueue、删除队列元素以及销毁等。 2. 实现步骤 首先,分析题目要求划分实现模块、画出大致的流程图,定义基本数据类型,诸如结构体、队列等; 其次,考虑基本大致的操作,比如要拟定开门的时间、顾客到来为其提供服务以及离开时的操作等; 再次,针对上述的基本操作实现具体需要进行的操作,具体实现每个环节需要进行的基本操作,即具体编写每个小函数实现功能; 最后,编写主函数对每个实现进行按需调用,实现操作。 3. 流程图 图-1 事件流程图

离散的有限K-L展开式的形式

离散的有限K-L 展开式的形式设一连续的随机实函数x(t), 21T t T ≤≤,则x(t)可用已知的正交函数集{φj (t), j=1,2,…}的线性 组合来展开,即: 2 11j j j j j 2211T t T ,)t (a )t (a )t (a )t (a )t (x ≤≤=++++=∑∞ =φφφφΛ Λ (1) 式中,a j 为展开式的随机系数,φj (t)为一连续的正交函数,它应满足: ? ? ? ?≠==2 1 T T m )t (n n m if 0n m if ,1dt )t (~ φφ 其中)t (~ m φ为φm (t)的共轭复数式。 将上式写成离散的正交函数形式,使连续随机函数x(t)和连续正交函数φj (t)在区间21T t T ≤≤内被等间隔采样为n 个离散点,即: )}n (x ,),2(x ),1(x {)t (x Λ→ )}n (,),2(),1({)t (j j j j φφφφΛ→ 写成向量形式: T ))n (x ,),2(x ),1(x (x Λ= n ,,2,1j ,))n (,),2(),1((T j j j j ΛΛ=→φφφφ 将式(1)取n 项近似,并写成离散展开式: 21n 1j j j T t T ,a a x ≤≤Φ==∑=φ (2) 其中,a 为展开式中随机系数的向量形式,即: a = (a 1, a 2, …, a j , …, a n )T Φ为n x n 维矩阵,即:

??? ?? ?? ?????==Φ)n () n ()n ()2() 2()2()1()1()1(),,,(n 21n 2 1 n 21n 21φφφφφφφφφφφφΛ ΛΛΛΛΛΛΛ 其中,每一列为正交函数集中的一个函数,小括号内的序号为正交函数的采样点次序。因此,Φ实质上是由φj 向量组成的正交变换矩阵,它将x 变换成a 。

单服务台排队系统离散事件系统仿真实验

离散事件系统仿真实验 一、实验目标 通过单服务台排队系统的方针,理解和掌握对离散事件的仿真建模方法,以便对其他系统进行建模,并对其系统分析,应用到实际系统,对实际系统进行理论指导。 二、实验原理 1.排队系统的一般理论 一般的排队系统都有三个基本组成部分: (1)到达模式:指动态实体(顾客)按怎样的规律到达,描写实体到达的统计特性。通常假定顾客总体是无限的。 (2)服务机构:指同一时刻有多少服务设备可以接纳动态实体,它们的服务需要多少时间。它也具有一定的分布特性。通常,假定系统的容量(包括正在服务的人数加上在等待线等待的人数)是无限的。 (3)排队规则:指对下一个实体服务的选择原则。通用的排队规则包括先进先出(FIFO),后进先出(LIFO),随机服务(SIRO)等。 2.对于离散系统有三种常用的仿真策略:事件调度法、活动扫描法、进程交互法。 (1)事件调度法(Event Scheduling): 基本思想:离散事件系统中最基本的概念是事件,事件发生引起系统状态的变化,用事件的观点来分析真实系统。通过定义事件或每个事件发生系统状态的变化,按时间顺序确定并执行每个事件发生时有关逻辑关系。 (2)活动扫描法: 基本思想:系统有成分组成,而成分又包含活动。活动的发生必须满足某些条件,且每一个主动成分均有一个相应的活动例程。仿真过程中,活动的发生时间也作为条件之一,而且较之其他条件具有更高的优先权。 (3)进程交互法: 基本思想:将模型中的主动成分历经系统所发生的事件及活动,按时间发生的顺序进行组合,从而形成进程表。系统仿真钟的推进采用两张进程表,一是当前事件表,二是将来事件表。 3.本实验采用的单服务台模型 (1)到达模式:顾客源是无限的,顾客单个到达,相互独立,一定时间的到达数服从指数

排队系统的离散事件模拟-示例

2.4 M/M/1排队系统的模拟 这个排队系统的服务员为一人。顾客到达系统的间隔时间为平均值等于1分的指数分布随机变量。单位顾客服务时间为平均值等于0.5分的指数分布随机变量。单列排队,采取先进先出的规则,排队行列的最大容量为100。模拟的终止条件为有1000个顾客服务结束离开系统。 2.4.1 系统的实体、属性和事件 事件类型有顾客到达事件、服务开始事件以及服务结束事件。但是,服务开始事件一般与顾客到达事件或服务结束事件相互重合,所以决定有两类事件: a. 第1类事件——顾客到达事件; b. 第2类事件——顾客在服务结束后离开系统。 2.4.2 系统模拟程序 为了进行模拟,除了主程序外,还编制了一系列的子程序或函数,它们的功能如表1.2.3所示。 表1.2.3 排队服务系统模拟的子程序和函数 表1.2.4列举模型的变量的名称和定义。 表1.2.4 本模型的变量

图1.2.8是本模拟模型的主程序,它的主要功能如下: MAIN PROGRAM NEVNTS = 2 //事件类型 READ 10, MARRVT, MSERVT //到达间隔时间为1,服务时间为0.5 10 FORMA T(2F10.0) READ 20, TOTCUS //结束服务顾客总数1000 20 FORMA T(I 10) CALL INIT 30 CALL TIMING GO TO (40, 50), NEXT //NEXT = 1, GO TO 40; NEXT = 2, GO TO 50 40 CALL ARRIVE GO TO 60 50 CALL DEPART 60 IF(NUMCUS .LT. TOTCUS) GO TO 30 CALL REPORT STOP END 图1.2.8 排队服务系统模拟的主程序 SUBROUTINE INIT TIME = 0.0 STATUS = 0.0 //服务员状态 NIQ = 0 //系统中的停留人数 TLEVNT = 0.0 //上次事件时间 NUMCUS = 0 //已结束服务的顾客数 TOTDEL = 0.0 //顾客停留时间总和 ANIQ = 0.0 //系统中人数的时间积分值

银行业务模拟与离散事件模拟

兰州商学院陇桥学院 工学系课程设计报告 设计题目:银行业务模拟与离散事件模拟系别:工学系 专业 (方向): 年级、班: 学生姓名: 学生学号: 指导教师: 年月日

目录 一、系统开发的背景。 (1) (一)系统功能要求 (1) (二)系统模块结构设计 (1) 三、系统的设计与实现 (2) (一)开门函数: (3) (二)顾客到达函数: (4) (三)顾客离开函数: (5) 四、系统测试 (6) 五、总结 (7) 六、附件(代码、部分图表) (7)

银行业务模拟与离散事件模拟 一、系统开发的背景。 为了在现实生活中,方便银行业务员更好的操作和管理银行出现的各种事件,以及方便算出各种时间,我们设计了银行业务模拟与离散事件模拟系统。 通过此次课程设计中银行业务模拟的题目,掌握队列,或链表等数据结构的基本操作方面的知识并能灵活的解决一些基本的问题,加深对其性质及操作的理解。 将所学数据结构方面的知识与一门具体的语言相结合来进行实现,感受数据结构的强大作用,加深理解。 (一)系统功能要求 编制一个程序,可以以模拟银行的这种业务活动并计算一天中客户在银行逗留的平均时间 1、客户到达时间随机产生,一天客户的人数设定为100人; 2、银行业务员处理时间随机产生,平均处理时间为10分钟; 3、将一天的数据结构(包括业务员和客户)以文件方式输出。 . (二)系统模块结构设计 通过对系统功能的分析,银行业务模拟与离散事件模拟系统功能如下图所示。

银行业务模拟与离散事件模拟系统 通过上图的功能分析,把整个系统划分为3个模块: 1、开门函数,该模块主要实现:银行开始正常营业时间,借助函数OpenForDay()来实现; 2、顾客到达函数,该模块主要实现:客户在银行里从排队到办理完银行业务的功能,借助函数CustomerArrive()来实现; 3、顾客离开函数,该模块主要实现:银行下班时间及顾客全部离开的功能,借助函数CustomerDepart()来实现。 三、系统的设计与实现 【流程图】

基于事件驱动编程

所谓事件驱动,简单地说就是你点什么按钮(即产生什么事件),电脑执行什么操作(即调用什么函数).当然事件不仅限于用户的操作. 事件驱动的核心自然是事件。从事件角度说,事件驱动程序的基本结构是由一个事件收集器、一个事件发送器和一个事件处理器组成。事件收集器专门负责收集所有事件,包括来自用户的(如鼠标、键盘事件等)、来自硬件的(如时钟事件等)和来自软件的(如操作系统、应用程序本身等)。事件发送器负责将收集器收集到的事件分发到目标对象中。事件处理器做具体的事件响应工作,它往往要到实现阶段才完全确定,因而需要运用虚函数机制(函数名往往取为类似于HandleMsg的一个名字)。对于框架的使用者来说,他们唯一能够看到的是事件处理器。这也是他们所关心的内容。 视图(即我们通常所说的“窗口”)是“事件驱动”应用程序的另一个要元。它是我们所说的事件发送器的目标对象。视图接受事件并能够对其进行处理。当我们将事件发送到具体的视图时,实际上我们完成了一个根本性的变化:从传统的流线型程序结构到事件触发方式的转变。这样应用程序具备相当的柔性,可以应付种种离散的、随机的事件。 由于Windows本身是基于“事件驱动”模型的。因而在Windows操作系统下实现应用程序框架有相当的便利。在事件驱动程序的基本单元中,事件收集器已经由Windows系统完成;事件发送器也已经由Windows完成了部分内容。之所以是部分而非完全是因为Windows是用C语言实现的,而不是C++。由于没有对象,Windows将事件发送到所谓的“窗口函数”中(尽管不是发送到具体的对象,但应该说这是面向对象方式实现的一个变体)。要感谢Windows做了这件事。确定事件的目标所要做的工作的复杂可能要超出我们的想象。weWidgets的中所有可以处理事件的类都继承自wxEvtHandler,其中包含frames,buttons,menus,even documents,所有的窗体类(即从wxWindow继承的类)和程序类(application class). 这些类可以有一个事件表,用来绑定事件和被调用的函数(handler functions). 过程3.2. 建立一个静态事件表(即编译时生成的事件表)的操作步骤 建立一个新类(直接或间接从wxEvtHandler继承) 为每个要处理的事件声明被调用的函数 在被处理的事件所在的类的声明中加入宏DECLARE_EVENT_TABLE 在宏BEGIN_EVENT_TABLE... END_EVENT_TABLE(就是事件表)中将函数与枚举的数字绑定(因为产生该类型的事件的按钮不唯一,要用枚举数来区分);有些事件不必与枚举数绑定,因为产生该类型的事件的对象可以确定(比如就是this). 1.要理解事件驱动和程序,就需要与非事件驱动的程序进行比较。实际上,现代的程序大多是事件驱动的,比如多线程的程序,肯定是事件驱动的。早期则存在许多非事件驱动的程序,这样的程序,在需要等待某个条件触发时,会不断地检查这个条件,直到条件满足,这是很浪费cpu时间的。而事件驱动的程序,则有机会释放cpu从而进入睡眠态(注意是有机会,当然程序也可自行决定不释放cpu),当事件触发时被操作系统唤醒,这样就能更加有效地使用cpu. 2.再说什么是事件驱动的程序。一个典型的事件驱动的程序,就是一个死循环,并以一个线程的形式存在,这个死循环包括两个部分,第一个部分是按照一定的条件接收并选择一个要处理的事件,第二个部分就是事件的处理过程。程序的执行过程就是选择事件和处理事件,而当没有任何事件触发时,程序会因查询事件队列失败而进入睡眠状态,从而释放cpu。 3.事件驱动的程序,必定会直接或者间接拥有一个事件队列,用于存储未能及时处理的事件。 4.事件驱动的程序的行为,完全受外部输入的事件控制,所以,事件驱动的系统中,存在大量这种程序,并以事件作为主要的通信方式。

离散事件系统仿真论

摘要 近年来,随着我国铁路事业的迅猛发展,铁路的运输能力得到了大幅度提升。在客运技术与速度提高的同时,作为旅客体验铁路服务的一个必要环节,售票环节的重要性也随之提高。然而大型客运站真实的售票过程极为复杂,旅客的行为受事件驱动,他们的状态在一些不均匀的离散时刻发生改变且其变化的内部机理非常复杂,离散时间点一般不能确定,这是典型的离散事件系统,通常无法利用一般的数学方法进行描述。我们通常采用离散事件系统仿真的方法来解决此类问题,它是解决此类问题的最有用处的方法之一。 要对系统进行仿真研究,首先就必须建立起系统的仿真模型。本文在阅读大量文献的基础上,简单介绍了离散事件系统的建模与仿真方法,并对北京西客站售票大厅建立离散事件系统仿真模型,对旅客售票过程进行了优化改善。 关键词:离散事件,系统仿真

Abstract In recent years, with the rapid development of China's railway business, railway transport capacity has been improved significantly. The process of Buy a ticket became more and more important , while the technology and speed had Substantially Improved.But the process in the real world is so complex that we can not use Mathematical methods to study it. The most useful way to study this case is to Simulate the Discrete Event System. Simulation study of a system, we must first establish a system simulation model. On the base of studying a lot of academic articles this thesis simplely introduced the discrete event systems modeling and simulation methods and established the discrete event systems of Beijing West Railway Station. Simulated and optimizated the process of Buy a ticket KEYWORDS:discrete event , system simulation . 1. 概述 (4) 1.1. 售票服务环节研究 (4)

Python离散事件模拟和SimPy简介

Introduction to Discrete-Event Simulation and the SimPy Language Norm Matloff February13,2008 c 2006-2008,N.S.Matloff Contents 1What Is Discrete-Event Simulation(DES)?3 2World Views in DES Programming3 2.1The Activity-Oriented Paradigm (3) 2.2The Event-Oriented Paradigm (4) 2.3The Process-Oriented Paradigm (6) 3Introduction to the SimPy Simulation Language7 3.1SimPy Overview (8) 3.2Introduction to SimPy Programming (9) 3.2.1MachRep1.py:Our First SimPy Program (10) 3.2.2MachRep2.py:Introducing the Resource Class (14) 3.2.3MachRep3.py:Introducing Passivate/Reactivate Operations (16) 3.2.4MMk.py:“Do It Yourself”Queue Management (18) 3.2.5SMP.py:Simultaneous Possession of Resources (20) 3.2.6Cell.py:Dynamic Creation of Threads (22) 3.3Note These Restrictions on PEMs (25) 3.4SimPy Data Collection and Display (25) 3.4.1Introduction to Monitors (25) 3.4.2Time Averages (26) 3.4.3The Function Monitor.timeAverage() (27) 3.4.4But I Recommend That You Not Use This Function (27)

第4章 离散事件系统仿真(本)

第4章 离散事件系统仿真

4.1 离散事件仿真的基本概念 4.1.1.事件 ?事件是描述系统的一个基本要素。事件是指引起系统状态变化的行为,系统的动态过程是靠事件来驱动的。例如,在物流系统中,工件到达可以定义为一类事件。因为工件到达仓库,仓库货位的状态会从空变为满,或者引起原来等待入库的队列长度的变化。 ?事件一般分为两类:必然事件和条件事件。只与时间有关的事件称为必然事件。如果事件发生不仅与时间因素有关,而且还与其它条件有关,则称为条件事件。系统仿真过程,最主要的工作就是分析这些必然事件和条件事件。

4.1.2 成分 描述系统的另一基本要素是成分。成分与实体是同一概念,只是根据习惯,在描述系统时用实体,而在模型描述中用成分。成分分为主动成分和被动成分。 可以主动产生活动的成分称为主动成分,如物流系统中的工件,它的到达将产生入库活动或排队活动。本身不产生活动,只在主动成分作用下才产生状态变化的那些成分称为被动成分。

4.1.3 进程 由若干事件与若干活动组成的过程称为进程。它描述了各事件活动发生的相互逻辑关系及时序关系。例如,工件由车辆装入进货台;经装卸搬运进入仓库;经保管、加工到配送至客户的过程就是一个进程。事件、活动与进程的关系如图 3-1所示进程

4.1.4.仿真时钟 ?仿真时钟用于表示仿真事件的变化。 ?由于仿真实质上是对系统状态在一定时间序列的动态描述,因此,仿真时钟一般是仿真的主要自变量,仿真时钟的推进是系统仿真程序的核心部分。 ?应当指出,仿真时钟所显示的是仿真系统对应实际系统的运行时间,而不是计算机运行仿真模型的时间。仿真时间与真实时间将设定成一定比例关系,使得像物流系统这样复杂的系统,利用计算机仿真只需要几分钟就可以完成,而真实系统的运行则需要若干天,甚至若干月。

离散事件

关于离散事件系统仿真的总结 1、离散系统仿真的认识 1.1系统仿真与系统 系统仿真是以相似原理、系统技术、信息技术及其应用领域有关专业技术为基础,以计算机和各种专用物理效应设备为工具,利用系统模型对真实的或假想的系统进行动态研究的一门多学科的综合性技术口。相似论是系统仿真的主要理论依据。 系统仿真研究的对象是系统。系统是指具有某些特定功能、按照某些规律结合起来、互相作用、互相依存的所有事物的集合或总和。 任何系统都存在三方面需要研究的内容,即实体、属性和活动。实体是存在于系统中的每一项确定的物体。属性是实体所具有的每一项有效的特性。活动是导致系统状态发生变化的一个过程。活动是在一段时间内发生的情况,活动反映了系统的变化规律。存在系统内部的实体、属性和活动组成的整体称为系统的状态。处于平衡状态的系统统称为静态系统,状态随时间不断变化着的系统为动态系统。 根据系统状态的变化是否连续可将系统分为连续系统和离散系统及连续离散混合系统。连续系统的状态变量是连续变化的。离散系统包括离散时间系统和离散事件系统,离散时间系统的状态变量是间断的,但是它和连续系统具有相似的性能,它们的系统模型都能用方程的形式加以描述。 1.2离散事件系统 离散事件系统是指受事件驱动、系统状态跳跃式变化的动态系统。离散事件系统的系统状态仅在离散的时间点上发生变化,而且这些离散时间点一般是不确定的。例如:单人理发馆系统,设上午9:00开门,下午5:00关门。顾客到达时间一般是随机的,为每个顾客服务的时间长度也是随机的。 这类系统中引起状态变化的原因是事件,通常状态变化与事件的发生是一一对应的。事件的发生一般带有随机性,即事件的发生不是确定性的,而是遵循某种概率分布。而且事件的发生没有持续性,在一个时间点瞬间完成。离散事件系统的系统模型不能用方程的形式描述。离散事件系统的研究方法是排队论和运筹论。针对离散事件系统的仿真就称为离散事件系统仿真. 1.3系统模型 系统模型是对实际系统的一种抽象,是系统本质的表述,是人们对客观世界反复认识、分析,经过多级转换、整合等相似过程而形成的最终结果,它具有与系统相似的数学描述形式或物理属性,以各种可用的形式给出研究系统的信息。 系统仿真中所用的模型分为实体模型和数学模型.在离散事件系统仿真中使用的是数学模型.

相关文档
相关文档 最新文档