第一章
1.1 图给出两台DFA M1和M2的状态图. 回答下述有关问题.
a.M1的起始状态是q1
b.M1的接受状态集是{q2}
c.M2的起始状态是q1
d.M2的接受状态集是{q1,q4}
e.对输入aabb,M1经过的状态序列是q1,q2,q3,q1,q1
f.M1接受字符串aabb吗?否
g.M2接受字符串ε吗?是
1.2 给出练习
2.1中画出的机器M1和M2的形式描述.
M1=(Q1,Σ,δ1,q1,F1) 其中
1)Q1={q1,q2,q3,};
2)Σ={a,b};
3)δ1为:
4)q1是起始状态
5)F1={q2}
M2=(Q2,Σ,δ2,q2,F2) 其中
1)Q2={q1,q2,q3,q4};
2)Σ={a,b};
3)δ2为:
3) q 2是起始状态 4) F 2={q 1,q 4}
1.3 DFA M 的形式描述为
( {q 1,q 2,q 3,q 4,q 5},{u,d},δ,q 3,{q 3}),其中δ在表2-3
中给出。试画出此机器的状态图。
1.6 画出识别下述语言的DFA 的状态图。
a){w | w 从1开始以0结束}
b){w | w 至少有3个1}
c) {w | w 含有子串0101}
d) {w | w 的长度不小于3,且第三个符号为0}
e) {w | w 从0开始且为奇长度,或从1开始且为偶长度}
或
f) {w | w 不含子串110}
g) {w | w 的长度不超过5}
}
i){w | w 的奇位置均为1}
j) {w | w 至少含有2个0,且至多含有1个1}
k) {ε,0}
0,1
1
m) 空集
n) 除空串外的所有字符串
1.7 给出识别下述语言的NFA ,且要求符合规定的状态数。 a. {w | w 以00
结束},三个状态
b. 语言{w | w 含有子串0101,即对某个x 和y ,w=x0101y },5个状态.
c. 语言{w | w 含有偶数个0
或恰好两个1},6个状态。
d. 语言{0},2个状态。
e. 语言0*1*0*0,3个状态。
f. 语言{ε},1个状态。
g. 语言0*,1个状态。
1.11证明每一台NFA 都能够转换成等价的只有一个接受状态的NFA 。
证明:设NFA M={Q ,Σ,δ,q 0,F},F={r i1,……,r ik }.添加一个状态p 后,r i1,……,r ik 分别向p 引ε箭头,将r i1,……,r ik 变为非接受状态,p 变为接受状态。又因为添加ε箭头不影响NFA 识别语言,所以命题成立。
1.14 a 证明:设M 是一台语言B 的DFA ,交换M 的接状态与非接受状态得到一台新的
DFA ,则这台新的DFA 是识别B 的补集,因此,正则语言类受在补运算下封闭。 b 举例说明:设M 是一台识别语言B 的NFA ,交换M 的接受状态与非接受状态得到一台新的NFA ,这台新的NFA 不一定识别B 的补集。NFA 识别的语言类在补集下封闭吗?解释你的回答。 解:
a. M 是DFA, M 是{Q,∑,δ,q 0,F},令N={Q,∑,δ,q 0,Q-F},设ω=ω1ω2…ωn 是字母表上任意字符串,因为M 与N 均为DFA,所以必然存在Q 中状态序列r 0,r 1,…,r n ,使得:r 0=q 0, δ(r i , ωi+1)=r i+1, i=0,…
,n-1
1)若r n ∈F 则ω∈B;
2)若r n ?F,则r n ∈Q-F,即N 接受ω,若ω?B, 所以N 接受B 的补集,即B 的补集正则。 所以,正则语言类在补运算下封闭。
b. 设B 为{0}。NFA M : 可识别它。
依题对它作变换,得到N :
则N 识别的语言{ε}不是B 的子集。所以交换M 的接受状态与非接受状态得到的新的NFA 不一定识别B 的补集。
但是由于NFA 识别的语言类与DFA 识别的语言类相同,即正则语言类。由a 的证明,正则语言类在补运算封闭,可知,NFA 识别的语言类---正则语言类在补运算下封闭。 若NFA 识别语言A ,必有 等价的DFA 识别A,从而由a 知,可交换DFA 的接受与非接受状态构造识别A 的补集的DFA,则必有等价的NFA 识别A 的补集。只是,该NFA 未必有原NFA 交换接受与非接受状态构造而成。
1.15 给出一个反例,说明下述构造不能证明定理
2.24,即正则语言类在星号运算下封闭。设N=(Q 1,Σ,δ1,q 1,F 1)识别A 1。如下构造N=(Q 1,Σ,δ1,q 1,F 1)。N 应该识别A 1*。
a. N 的状态集是N 1的状态集。
b. N 的起始状态是N 1的起始状态相同。
c. F={q 1}∪F 1。F 的接受状态是原来的接受状态加上它的起始状态。
d. 定义δ如下:对每一个q 属于Q 和每一个a 属于Σ。
???≠∈?≠?=ε
δεδδa F q q a q a F q a q a q },{),(
),,(),(11111
且若或若
HUNAN UNIVERSITY 计算理论导引实验报告 题目:图灵机(Turing)的模拟学生姓名: 学生学号: 专业班级:计算机科学与技术2班上课老师: 实验日期:2014-1-6
一、实验目的 (2) 二、实验内容.......................................................................................... 错误!未定义书签。 三、实验代码.......................................................................................... 错误!未定义书签。 四、测试数据以及运行结果 (8) 五、实验感想 (9)
一、实验目的 1、掌握Turing机的概念。 2、掌握Turing机的运行过程,了解每一个格局的转化。 二、实验内容 对于任意给定的一台Turing机和任意给定的字符串w ( w不含空格),编程模拟此Turing 机的运行过程,要求输出从开始运行起的每一格局。 三、实验代码 /***************************************************************** 图灵机的模拟过程 计科二班20110801212张琦佳 *****************************************************************/ # include
计算题库及参考答案 1、设A 点高程为15.023m ,欲测设设计高程为16.000m 的B 点,水准仪安置在A 、B 两点之间,读得A 尺读数a=2.340m ,B 尺读数b 为多少时,才能使尺底高程为B 点高程。 【解】水准仪的仪器高为=i H 15.023+2.23=17.363m ,则B 尺的后视读数应为 b=17.363-16=1.363m ,此时,B 尺零点的高程为16m 。 2、在1∶2000地形图上,量得一段距离d =23.2cm ,其测量中误差=d m ±0.1cm ,求该段距离的实地长度 D 及中误差D m 。 【解】==dM D 23.2×2000=464m ,==d D Mm m 2000×0.1=200cm=2m 。 3、已知图中AB 的坐标方位角,观测了图中四个水平角,试计算边长B →1,1→2,2→3, 3→4的坐标方位角。 【解】=1B α197°15′27″+90°29′25″-180°=107°44′52″ =12α107°44′52″+106°16′32″-180°=34°01′24″ =23α34°01′24″+270°52′48″-180°=124°54′12″ =34α124°54′12″+299°35′46″ -180°=244°29′58″ 4、在同一观测条件下,对某水平角观测了五测回,观测值分别为:39°40′30″,39°40′48″,39°40′54″,39°40′42″,39°40′36″,试计算: ① 该角的算术平均值——39°40′42″; ② 一测回水平角观测中误差——±9.487″; ③ 五测回算术平均值的中误差——±4.243″。 5、在一个直角三角形中,独立丈量了两条直角边a ,b ,其中误差均为m ,试推导由a ,b 边计算所得斜边c 的中误差c m 的公式? 【解】斜边c 的计算公式为22b a c += ,全微分得 db c b da c a bdb b a ada b a d c +=+++=--2)(212)(21212 22122 应用误差传播定律得2 22 222222222m m c b a m c b m c a m c =+=+= 6、已知=AB α89°12′01″,=B x 3065.347m ,=B y 2135.265m ,坐标推算路线为B →1→2,测得坐标推算路线的右角分别为=B β32°30′12″,=1β261°06′16″,水平距离分别为=1B D 123.704m ,=12D 98.506m ,试计算1,2点的平面坐标。 【解】 1) 推算坐标方位角 =1B α89°12′01″-32°30′12″+180°=236°41′49″ =12α236°41′49″-261°06′16″+180°=155°35′33″ 2) 计算坐标增量 =?1B x 123.704×cos236°41′49″=-67.922m , =?1B y 123.704×sin236°41′49″=-103.389m 。 =?12x 98.506×cos155°35′33″=-89.702m , =?12y 98.506×sin155°35′33″=40.705m 。 3) 计算1,2点的平面坐标 图 推算支导线的坐标方位角
微观第七章习题 一、名词解释 完全垄断市场垄断竞争市场寡头市场价格歧视博弈纳什均衡 占优策略均衡 二、选择题 1、对于垄断厂商来说,()。 A、提高价格一定能够增加收益; B、降低价格一定会减少收益; C、提高价格未必会增加收益,降低价格未必会减少收益; D、以上都不对。 2、完全垄断的厂商实现长期均衡的条件是()。 A、MR=MC; B、MR=SMC=LMC; C、MR=SMC=LMC=SAC; D、MR=SMC=LMC=SAC=LAC。 3、完全垄断厂商的总收益与价格同时下降的前提条件是()。 A、Ed>1; B、Ed<1; C、Ed=1; D、Ed=0。 4、完全垄断厂商的产品需求弹性Ed=1时()。 A、总收益最小; B、总收益最大; C、总收益递增; D、总收益递减。 5、完全垄断市场中如果A市场的价格高于B市场的价格,则() A、A市场的需求弹性大于B市场的需求弹性; B、A市场的需求弹性小于B市场的需求弹性; C、A市场的需求弹性等于B市场的需求弹性; D、以上都对。 6、以下关于价格歧视的说法不正确的是()。 A、价格歧视要求垄断者能根据消费者的支付意愿对其进行划分; B、一级价格歧视引起无谓损失; C、价格歧视增加了垄断者的利润; D、垄断者进行价格歧视,消费者就必定不能进行套利活动。 7、垄断竞争的厂商短期均衡时,()。 A、一定能获得差额利润; B、一定不能获得经济利润; C、只能得到正常利润; D、取得经济利润、发生亏损和获得正常利润都有可能。 8、垄断竞争厂商长期均衡点上,长期平均成本曲线处于( B )
A、上升阶段 B、下降阶段 C、水平阶段 D、以上三种情况都有可能 9、垄断竞争厂商实现最大利润的途径有:( D ) A、调整价格从而确定相应产量 B、品质竞争 C、广告竞争 D、以上途径都可能用 10、按照古诺模型下列哪一说法不正确,()。 A、双头垄断者没有认识到他们的相互依耐性; B、每一个寡头都认定对方的产量保持不变; C、每一个寡头垄断者都假定对方价格保持不变; D、均衡的结果是稳定的。 11、斯威齐模型是() A、假定一个厂商提高价格,其他厂商就一定跟着提高价格; B、说明为什么每个厂商要保持现有的价格,而不管别的厂商如何行动; C、说明为什么均衡价格是刚性的(即厂商不肯轻易的变动价格)而不是说明价格如何决定; D、假定每个厂商认为其需求曲线在价格下降时比上升时更具有弹性。 12、在斯威齐模型中,弯折需求曲线拐点左右两边的弹性是()。 A、左边弹性大,右边弹性小; B、左边弹性小,右边弹性大; C、两边弹性一样大; D、以上都不对。 13、与垄断相关的无效率是由于()。 A、垄断利润 B、垄断亏损 C、产品的过度生产 D、产品的生产不足。 三、判断题 1、垄断厂商后可以任意定价。 2、完全垄断企业的边际成本曲线就是它的供给曲线。 3、一级价格歧视是有市场效率的,尽管全部的消费者剩余被垄断厂商剥夺了。 4、寡头之间的串谋是不稳定的,因为串谋的结果不是纳什均衡。 5、垄断厂商生产了有效产量,但它仍然是无效率的,因为它收取的是高于边际成本的价格,获取的利润是一种社会代价。 6、完全垄断厂商处于长期均衡时,一定处于短期均衡。 7、垄断竞争厂商的边际收益曲线是根据其相应的实际需求曲线得到的。 8、由于垄断厂商的垄断地位保证了它不管是短期还是长期都可以获得垄断利润。 四、计算题 1、已知某垄断者的成本函数为TC=0.5Q2+10Q,产品的需求函数为P=90-0.5Q, (1)计算利润最大化时候的产量、价格和利润; (2)假设国内市场的售价超过P=55时,国外同质的产品将输入本国,计算售价p=55
第三章 上下文无关语言 3.1 略。 3.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例3.20,证明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10),证明上下文无关语言在补运算下不封闭。 证明:a.先说明A,B 均为上下文无关文法,对A 构造CFG C 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言,所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭,则对于(a)中上下文无关语言A,B ,A ,B 也为CFL ,且CFL 对并运算封闭,所以B A ?也为CFL ,进而知道B A ?为CFL ,由DeMorgan 定律B A ?=A ∩B ,由此A ∩B 是CFL,这与(a)的结论矛盾,所以CFL 对补运算不封闭。 3.3 略。 3.4和3.5 给出产生下述语言的上下文无关文法和PDA ,其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A 0, ε→ε 0,ε→ε 0,ε→ε 1,ε→ε 0,ε→ε
一、基础知识。(5小题,共26分。) 1.读音节,找词语朋友。(10分) táo zuì nínɡ zhònɡ wǎn lián ēn cì ()()()() zī rùn kuí wú zhēn zhì miǎn lì ()()()() xuán yá qiào bì hú lún tūn zǎo ()() 2.读一读,加点字念什么,在正确的音节下面画“_”。(4分) 镌.刻(juān juàn)抚摩.(mó mē)扁.舟(biān piān)阻挠.(náo ráo)塑.料(suò sù)挫.折(cuō cuò)归宿.(sù xiǔ)瘦削.(xiāo xuē)3.请你为“肖”字加偏旁,组成新的字填写的空格内。(4分) 陡()的悬崖胜利的()息俊()的姑娘 ()好的铅笔弥漫的()烟畅()的商品 ()遥自在的生活元()佳节 4.按要求填空,你一定行的。(4分) “巷”字用音序查字法先查音序(),再查音节()。按部首查字法先查()部,再查()画。能组成词语()。 “漫”字在字典里的意思有:①水过满,向外流;②到处都是;③不受约束,随便。 (1)我漫.不经心地一脚把马鞍踢下楼去。字意是() (2)瞧,盆子里的水漫出来了。字意是() (3)剩下一个义项可以组词为() 5.成语大比拼。(4分) 风()同()()崖()壁()()无比 和()可()()扬顿()()高()重 ( )不()席张()李() 二、积累运用。(3小题,共20分。) 1.你能用到学过的成语填一填吗?(每空1分) 人们常用来比喻知音难觅或乐曲高妙,用来赞美达芬
(1)鲁迅先生说过:“,俯首甘为孺子牛。” (2),此花开尽更无花。 (3)必寡信。这句名言告诉我们。 (4)但存,留与。 (5)大漠沙如雪,。 3.按要求写句子。(每句2分) (1)闰土回家去了。我还深深地思念着闰土。(用合适的关联词组成一句话)(2)老人叫住了我,说:“是我打扰了你吗?”(改成间接引语) (3)这山中的一切,哪个不是我的朋友?(改为陈述句) (4)月亮升起来了。(扩句) (5)小鱼在水里游来游去。(改写成拟人句) 三、口语交际。(共3分。) 随着“嫦娥一号”卫星的发射成功,作为中华少年的我们,面对祖国的飞速发展的科技,你想到了什么?想说点什么呢? 四、阅读下面短文,回答问题。(10小题,共26分。) 1.课内阅读。(阅读文段,完成练习) 嘎羧来到石碑前,选了一块平坦的草地,一对象牙就像两支铁镐,在地上挖掘起来。它已经好几天没吃东西了,又经过长途跋涉,体力不济,挖一阵就 喘息一阵。嘎羧从早晨一直挖到下午,终于挖出了一个椭圆形的浅坑。它滑下
四、计算题:(每小题8分,共16分)【得分: 】 1. 假定某消费者关于某种商品的消费数量Q 与收入M 之间的函数关系为M=1002 Q 求:当收入M=4900时的需求收入点弹性 解: Q= 110 m E =0.5 2.假定某厂商的短期生产的边际成本函数SMC=32 Q -8Q +100,且已知当产量Q =10时的总成本STC=2400,求相应的STC函数、SAC函数、AVC函数。 解: STC=3 Q -42 Q +100Q +2800 SAC=2 Q -4Q +28001 Q -+100 AVC=2 Q -4Q +28001 Q - 1.假设某种商品的需求函数和供给函数为 Q D =14-3P Q S =2+6P 求该商品供求均衡时的需求价格弹性和供给弹性。 解:根据市场均衡条件Qd=Qs,解得P=4/3 Q=10 该商品在市场均衡时的需求价格弹性为0.4 该商品在市场均衡时的供给价格弹性为0.8。 2.假定某商品市场上有1000位相同的消费者,单个消费者的需求函数为:d Q =10-2P ;同时有20个相同的厂商向该市场提供产品,每个厂商的供给函数为:S Q =500P 。 (1) 求该商品的市场需求函数和市场供给函数; (2) 如果消费者对该商品的偏好减弱,使得个人需求曲线向左移动了4个单位,求变化后 的市场均衡价格和均衡数量。 解:(1)Qd=1000×(10-2P)=10000-2000P Qs=20×500P=10000P (2)Qd=1000×(6-2P)=6000-2000P 6000-2000P = 10000P P=0.5 Q=5000 3.已知某人的效用函数为XY U =,他打算购买X 和Y 两种商品,当其每月收入为120元,2=X P 元、3=Y P 元时, (1)为获得最大效用,他应该如何选择X 和Y 的组合?
计算题:A (1—5) 1. 假定某消费者关于某种商品的消费数量Q 与收入M 之间的函数关系为M=1002 Q 求:当收入M=4900时的需求收入点弹性 解: Q= 110 m E =0.5 2.假定某厂商的短期生产的边际成本函数SMC=32 Q -8Q +100,且已知当产量Q =10时的总成本STC=2400,求相应的STC函数、SAC函数、AVC函数。 解: STC=3 Q -42 Q +100Q +2800 SAC=2 Q -4Q +28001 Q -+100 AVC=2 Q -4Q +28001 Q - 3、假设某种商品的需求函数和供给函数为Q D =14-3P , Q S =2+6P 求该商品供求均衡时的需求价格弹性和供给弹性。 解:根据市场均衡条件Qd=Qs,解得P=4/3 Q=10 该商品在市场均衡时的需求价格弹性为0.4 该商品在市场均衡时的供给价格弹性为0.8。 4、假定某商品市场上有1000位相同的消费者,单个消费者的需求函数为: d Q =10-2P ;同时有20个相同的厂商向该市场提供产品,每个厂商的供给函数 为:S Q =500P 。 (1) 求该商品的市场需求函数和市场供给函数; (2) 如果消费者对该商品的偏好减弱,使得个人需求曲线向左移动了4个单 位,求变化后的市场均衡价格和均衡数量。 解:(1)Qd=1000×(10-2P)=10000-2000P Qs=20×500P=10000P (2)Qd=1000×(6-2P)=6000-2000P 6000-2000P = 10000P P=0.5 Q=5000 5、已知某人的效用函数为XY U =,他打算购买X 和Y 两种商品,当其每月收入为120元,2=X P 元、3=Y P 元时,
计算理论答案 第一套BCACC CBCBB BBABC ACDAC 1.下列叙述中,正确的是()。 A)CPU能直接读取硬盘上的数据 B)CPU能直接存取内存储器 C)CPU由存储器、运算器和控制器组成 D)CPU主要用来存储程序和数据 2.1946年首台电子数字计算机ENIAC问世后,冯·诺依曼(Von Neumann)在研制EDVAC 计算机时,提出两个重要的改进,它们是()。 A)引入CPU和内存储器的概念 B)采用机器语言和十六进制 C)采用二进制和存储程序控制的概念 D)采用ASCII编码系统 3.汇编语言是一种()。 A)依赖于计算机的低级程序设计语言 B)计算机能直接执行的程序设计语言 C)独立于计算机的高级程序设计语言 D)面向问题的程序设计语言 4.假设某台式计算机的内存储器容量为128MB,硬盘容量为10GB。硬盘的容量是内存容量的()。 A)40倍 B)60倍 C)80倍 D)100倍 5.计算机的硬件主要包括:中央处理器(CPU)、存储器、输出设备和()。 A)键盘 B)鼠标 C)输入设备 D)显示器 6.根据汉字国标GB2312-80的规定,二级次常用汉字个数是()。 A)3000个 B)7445个 C)3008个 D)3755个 7.在一个非零无符号二进制整数之后添加一个0,则此数的值为原数的()。
A)4倍 B)2倍 C)1/2倍 D)1/4倍 8.Pentium(奔腾)微机的字长是()。 A)8位 B)16位 C)32位 D)64位 9.下列关于ASCII编码的叙述中,正确的是()。 A)一个字符的标准ASCII码占一个字节,其最高二进制位总为1 B)所有大写英文字母的ASCII码值都小于小写英文字母'a'的ASCII码值 C)所有大写英文字母的ASCII码值都大于小写英文字母'a'的ASCII码值 D)标准ASCII码表有256个不同的字符编码 10.在CD光盘上标记有"CD-RW"字样,此标记表明这光盘()。 A)只能写入一次,可以反复读出的一次性写入光盘 B)可多次擦除型光盘 C)只能读出,不能写入的只读光盘 D)RW是Read and Write的缩写 11.一个字长为5位的无符号二进制数能表示的十进制数值范围是()。 A)1~32 B)0~31 C)1~31 D)0~32 12、计算机病毒是指"能够侵入计算机系统并在计算机系统中潜伏、传播,破坏系统正常工作的一种具有繁殖能力的()。 A)流行性感冒病毒 B)特殊小程序 C)特殊微生物 D)源程序 13.在计算机中,每个存储单元都有一个连续的编号,此编号称为()。 A)地址 B)位置号 C)门牌号 D)房号 14.在所列出的:1、字处理软件,2、Linux,3、UNIX,4、学籍管理系统,5、Windows Xp和6.Office 2003这六个软件中,属于系统软件的有()。
微观经济学练习题 均衡价格理论 1、某市场的供给曲线与需求曲线分别为P=4Q s和P=12-2Q d。求出该市场的均衡价格和均 衡数量。 Q s =1/4P Q d=1/2(12-P)Q s = Q d1/4P=1/2(12-P)P=8,Q=2 2、如果大豆是牛的一种饲料,那么对大豆市场的价格补贴计划会如何影响牛肉的均衡价格 和均衡数量。 价格补贴计划会抬高牛饲料的价格,这又会使牛肉的供给曲线向左上方移动。于是牛肉的均衡价格上涨,均衡数量减少。(图略) 3、考虑一个市场,其供给曲线和需求曲线分别为:P=4Qs和P=12-2Qd。如果对场卖主出 售的每单位产出课税为6,均衡价格和均衡数量将会受到什么影响?如果对买主征收同样的税呢? 最初的均衡价格和均衡数量分别为:4Q s=12-2Q d,解出Q=2,P=8 税后,供给曲线变为:P=6+4 Q s P′,Q′分别表示税后的均衡价格和均衡数量。 得:=6+4Q′=12-2Q′,解出,P′=10,Q′=1 P′代表买主支付的价格。P′-6=4是卖主收取的价格。 若对买主课以6美元的税,则需求曲线变为P=6-2Q d,于是得到4Q″=6-2Q″, 解出Q″=1,P″=4。P″代表卖主收取的价格。P″+T= P″+6=10是买主支付的价格。 4、1986年7月某外国城市公共汽车票从32美分提高到40美分,同年8月的乘客为880 万人次,与1985年同期相比减少了12%,求需求的价格弧弹性。 解:P1=32 P2=40 Q2=880 Q1=880/(1-12%)=1000 E d= △Q/(Q1+Q2)·(P1+P2)/△P =(880 -1000)/(40 -32)× (40+32)/1000+880)=-0.57 所以,需求的价格弧弹性约为-0.57 5、X公司和Y公司是机床行业的两个竞争者,其主要产品的需求曲线分别为: PX=1000—5QX PY=1600—4QY 这两家公司现在的销售量分别为100单位X和250单位Y。 A:求X和Y当前的价格弹性。 A:Q X=100 Q Y=250 P X=1000-5Q X=1000 -5×100=500 P Y=1600-4Q Y=1600 -4 ×250=600 E dX=dQ X/dP X· P X/Q X=–1/5 ×500/100 = –1 E dY=dQ Y/dP Y· P Y/Q Y= –1/4 ×600/250 = –0.6 B:假定Y降价以后,使Q Y增加到300单位。同时导致X销售量Q X下降到75单位。试问X公司产品X的交叉价格弹性是多少? 由题设Q Y=300 Q X=75 P Y=1600-4 Q Y=1600 -4 ×300=400 △Q X=75 -100=-25 △P Y=400 -600=-200 于是X对Y的交叉弹性为: E XY= -25/ -200 ×(600+400)/(100+75)=5/7
东华大学 2010~ 2011学年第二学期研究生期末考试试题参考答案 和评分标准 考试学院:计算机 考试专业:计算机科学与技术 考试课程名称:计算理论导引与算法复杂性 一、单项选择题(每空2分,本题共20分) 1. DFA和NFA的区别在于(B )。 A、NFA能够识别的语言DFA不一定能够识别 B、对同一个输入串两者的计算过程不同 C、DFA能够识别的语言NFA不一定能够识别 D、NFA比DFA多拥有一个栈 2. 若一个语言A是非正则的,对于个给定的一个泵长p,若存在一个串s=xyz,|s|≥p,则 ( A )。 A、|y|可能大于等于0 B、xz∈A C、xyyz∈A D、|xy|不可能小于等于p 3. 下推自动机与图灵机的不同之处是( B )。 A、下推自动机比图灵机识别的语言多 B、下推自动机比图灵机识别的语言少 C、下推自动机识别的语言是不可判定 D、拥有一个无限的存储带 4. 如果一个语言是图灵可判定的,则(A)。 A、对于一个不属于它串s,图灵机计算s时,一定能够到达拒绝状态 B、对于一个不属于它串s,不一定有一个判定器判定s C、对于一个不属于它串s,图灵机计算s时,有可能进入无限循环状态 D、对于一个不属于它串s,图灵机计算s时,一定不会停机 5. 一个集合在条件( C )下是不可数的。 A、该集合为无限集合 B、组成该集合的元素是实数 C、该集合的规模大于自然数集合的规模 D、该集合是一个有限的集合 6. 对于一个语言,( C )的说法是正确的。 A、如果它属于Turing-recognizable,那么,一定属于EXPTIME B、如果它是NP-hard,那么,一定属于NP C、如果它是NP-complete,那么,一定属于NP D、它一定能被图灵机识别 7. 如果A≤m B且B是可判定的,则(A)。
《计算理论》试题答案(2007级) 一、证明:设M是一台识别语言B的DFA,交换M的接受状态与非接受状态得到一台新的DFA,则这台新DFA识别B的补集。因而,正则语言类在补运算下封闭。(8分) 参考答案: 设M’是一台将DFA M 的接受态与非接受态交换后的DFA,接下来证明M识别B语言,则M’识别B的补集: 假定M’识别x ,则对于x 在M’上运行将结束于M’的一个接受态,因为M和M’交换了接受态与非接受态,因此对于x运行于M,将会结束于一个非接受态,所以x∈/B。类似地,如果x不被M’接受,则它一定被M接受。故M’恰好接受所有不被M接受的那些串,因此M’识别B的补集。 既然B是任意的正则语言,且我们已构造出一台自动机识别它的补集,它表明任何正则语言的补也是正则的。因此,正则语言类在补运算下封闭。 二、令∑={0,1,+,=}和ADD={x=y+z | x,y,z是二制整数,且x是y与z的和},证明ADD不是正则的。(8分) 参考答案: 假定ADD是正则的。让P作为泵引理中的泵长度,选择S的串形式为1P=0P+1P作为ADD的一个成员。因为S有长度大于P,由泵引理保证它能分割成形如:S=xyz的三部分,满足泵引理的条件。泵引理的第三个条件有|xy|≤P,《它表明对于K≥1,y就是1K。这是xy2z是串1P+K=OP+1P,而它不是ADD的成员,由泵引理导出矛盾,因此ADD不是正则的。 三、请将下述CFG转换成等价的乔姆斯基范式文法。(8分) A→BAB|B|ε B→00|ε 参考答案: S0→AB|CC|BA|BD|BB|ε A→AB|CC|BA|BD|BB B→CC C→0 D→AB 四、请用泵引理证明语言A={ 0n#02n#03n | n≥0 }不是上下文无关的。(8分) 参考答案: 由泵引理,让P作为泵长度,s=0p#02p#03p ,接下来证明s=uvxyz不能进行泵抽取。 v和y都不能包含#,否则,xv2wy2z将超过2个#s ,因此,如果我们按#’s将s分成三段如:0p,02p,03p,至少有一段不包含v或y。因此,由于段之间的1:2:3的比例不再维持,xv2wy2z也不语言A中。故语言A={ 0n#02n#03n | n≥0 }不是上下文无关。的
土木工程测量6_计算题库 及参考答案 -标准化文件发布号:(9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII
计算题库及参考答案 1、设A 点高程为,欲测设设计高程为的B 点,水准仪安置在A 、B 两点之间,读得A 尺读数a=,B 尺读数b 为多少时,才能使尺底高程为B 点高程。 【解】水准仪的仪器高为=i H +=,则B 尺的后视读数应为 b==,此时,B 尺零点的高程为16m 。 2、在1∶2000地形图上,量得一段距离d =,其测量中误差=d m ±,求该段距离的实地长度D 及中误差D m 。 【解】==dM D ×2000=464m ,==d D Mm m 2000×=200cm=2m 。 3、已知图中AB 的坐标方位角,观测了图中四个水平角,试计算边长B →1,1→2,2→3,3→4的坐标方位角。 【解】=1B α197°15′27″+90°29′25″-180°=107°44′52″ =12α107°44′52″+106°16′32″-180°=34°01′24″ =23α34°01′24″+270°52′48″-180°=124°54′12″ =34α124°54′12″+299°35′46″-180°=244°29′58″ 4、在同一观测条件下,对某水平角观测了五测回,观测值分别为:39°40′30″,39°40′48″,39°40′54″,39°40′42″,39°40′36″,试计算: ① 该角的算术平均值——39°40′42″; ② 一测回水平角观测中误差——±″; ③ 五测回算术平均值的中误差——±″。 5、在一个直角三角形中,独立丈量了两条直角边a ,b ,其中误差均为m ,试推导由a ,b 边计算所得斜边c 的中误差c m 的公式 【解】斜边c 的计算公式为22b a c +=,全微分得 db c b da c a bdb b a ada b a d c +=+++=--2)(212)(2121 222 1 22 应用误差传播定律得2 22 222222222m m c b a m c b m c a m c =+=+= 6、已知=AB α89°12′01″,=B x ,=B y ,坐标推算路线为B →1→2,测得坐标推算路线的右角分别为=B β32°30′12″,=1β261°06′16″,水平距离分别为=1B D ,=12D ,试计算1,2点的平面坐标。 【解】 1) 推算坐标方位角 =1B α89°12′01″-32°30′12″+180°=236°41′49″ =12α236°41′49″-261°06′16″+180°=155°35′33″ 2) 计算坐标增量 =?1B x ×cos236°41′49″=, =?1B y ×sin236°41′49″=。 =?12x ×cos155°35′33″=, 图 推算支导线的坐标方位角
3.假定某企业的短期成本函数是TC(Q)=Q 3-5Q 2+15Q+66: 指出该短期成本函数中的可变成本部分和不变成本部分; 写出下列相应的函数:TVC(Q) AC(Q) AVC(Q) AFC(Q)和MC(Q). 解(1)可变成本部分: Q 3-5Q 2+15Q 不可变成本部分:66 (2)TVC(Q)= Q 3-5Q 2+15Q AC(Q)=Q 2-5Q+15+66/Q AVC(Q)= Q 2-5Q+15 AFC(Q)=66/Q MC(Q)= 3Q 2-10Q+15 4已知某企业的短期总成本函数是STC(Q)=0.04 Q 3-0.8Q 2+10Q+5,求最 小的平均可变成本值. 解: TVC(Q)=0.04 Q 3-0.8Q 2+10Q AVC(Q)= 0.04Q 2-0.8Q+10 令08.008.0=-='Q C AV 得Q=10 又因为008.0>=''C AV 所以当Q=10时,6=MIN AVC
5.假定某厂商的边际成本函数MC=3Q2-30Q+100,且生产10单位产量时 的总成本为1000. 求:(1) 固定成本的值. (2)总成本函数,总可变成本函数,以及平均成本函数,平均可变成本 函数. 解:MC= 3Q2-30Q+100 所以TC(Q)=Q3-15Q2+100Q+M 当Q=10时 固定成本值:500 TC(Q)=Q3-15Q2+100Q+500 TVC(Q)= Q3-15Q2+100Q AC(Q)= Q2-15Q+100+500/Q AVC(Q)= Q2-15Q+100 6.某公司用两个工厂生产一种产品,其总成本函数为C=2Q12+Q22-Q1Q2,
一、证明:设M是一台识别语言B的DFA,交换M的接受状态与非接受状态得到一台新的DFA,则这台新DFA识别B的补集。因而,正则语言类在补运算下封闭。(8分) 参考答案: 设M’是一台将DFA M的接受态与非接受态交换后的DFA,接下来证明M识别B语言,则M’识别B的补集: 假定M’识别x,则对于x 在M’上运行将结束于M’的一个接受态,因为M和M’交换了接受态与非接受态,因此对于x运行于M,将会结束于一个非接受态,所以x∈/B。类似地,如果x不被M’接受,则它一定被M接受。故M’恰好接受所有不被M接受的那些串,因此M’识别B的补集。 既然B是任意的正则语言,且我们已构造出一台自动机识别它的补集,它表明任何正则语言的补也是正则的。因此,正则语言类在补运算下封闭。 二、令∑={0,1,+,=}和ADD={x=y+z | x,y,z是二制整数,且x是y与z的和},证明ADD不是正则的。(8分) 参考答案: 假定ADD是正则的。让P作为泵引理中的泵长度,选择S的串形式为1P=0P+1P作为ADD的一个成员。因为S有长度大于P,由泵引理保证它能分割成形如:S=xyz的三部分,满足泵引理的条件。泵引理的第三个条件有|xy|≤P,《它表明对于K≥1,y就是1K。这是xy2z是串1P+K=OP+1P,而它不是ADD的成员,由泵引理导出矛盾,因此ADD不是正则的。 三、请将下述CFG转换成等价的乔姆斯基范式文法。(8分) A→BAB|B|ε B→00|ε 参考答案: S0→AB|CC|BA|BD|BB|ε A→AB|CC|BA|BD|BB B→CC C→0 D→AB 四、请用泵引理证明语言A={0n#02n#03n | n≥0 }不是上下文无关的。(8分) 参考答案: 由泵引理,让P作为泵长度,s=0p#02p#03p ,接下来证明s=uvxyz不能进行泵抽取。 v和y都不能包含#,否则,xv2wy2z将超过2个#s ,因此,如果我们按#’s将s分成三段如:0p,02p,03p,至少有一段不包含v或y。因此,由于段之间的1:2:3的比例不再维持,xv2wy2z也不语言A中。故语言A={0n#02n#03n | n≥0 }不是上下文无关。的 五、下面的语言都是字母表{0,1}上的语言,请以实现描述水平级给出判定这些语言的图灵机:(8分)
计算理论习题答案CHAP2new
2.2 a. 利用语言A={a m b n c n | m,n ≥0}和A={a n b n c m | m,n ≥0}以及例 3.20,证 明上下文无关语言在交的运算下不封闭。 b. 利用(a)和DeMorgan 律(定理1.10),证明上下文无关语言在补运算下不封闭。 证明:a.先说明A,B 均为上下文无关文法,对A 构造CFG C 1 S →aS|T|ε T →bTc|ε 对B,构造CFG C 2 S →Sc|R|ε R →aRb 由此知 A,B 均为上下文无关语言。 但是由例3.20, A ∩B={a n b n c n |n ≥0}不是上下文无关语言,所以上下文无关语言在交的运算下不封闭。 b.用反证法。假设CFL 在补运算下封闭,则对于(a)中上下文无关语言A,B , A , B 也为CFL ,且CFL 对并运算封闭,所以B A ?也为CFL ,进而知道B A ?为CFL ,由DeMorgan 定律 B A ?=A ∩B ,由此A ∩B 是CFL,这与(a)的结论矛盾,所以CFL 对补运算不封闭。 2.4和2.5 给出产生下述语言的上下文无关文法和PDA ,其中字母表∑={0,1}。 a. {w | w 至少含有3个1} S →A1A1A1A A →0A|1A|ε ε,1→ 1, 0, ε,1→ ε,1→
b. {w | w 以相同的符号开始和结束} S →0A0|1A1 A →0A|1A|ε c. {w | w 的长度为奇数} S →0A|1A A →0B|1B|ε B →0A|1A d. {w | w 的长度为奇数且正中间的符号为0} S →0S0|1S1|0S1|1S0|0 e. {w | w 中1比0多} S →A1A 1,ε→ 0,ε→0,ε→1,1→ 0,0→0,ε→1,ε→0,ε→0,ε→ 0,ε→0,0→ε,ε→ ε,$→
计算题: 1、 已知某厂商的生产函数为:Q=L 3/8K 5/8,又设P L =3,P K =5。 ⑴、 求产量Q=10时的最低成本支出和使用的L 与K 的数量。(5分) ⑵、 求产量Q=25时的最低成本支出和使用的L 与K 的数量。(5分) 求总成本为160时,厂商均衡的Q 、K 、L 的值。(5分) 2、 已知生产函数为:Q=,试证明: ⑴、 该生产过程是规模报酬不变。(7分)⑵它受边际报酬递减规律的支配。 3、甲、乙两公司的产品的需求曲线分别为Q 1=,Q 2=,这两家公司现在的销售量分别为100和250。 (1)求甲、乙两公司当前的价格弹性 (2)假定乙公司降价后,使乙公司的销售量增加到300,同时又导致甲公司的销售量下降到75,问甲公司产品的交叉弹性是多少 4、垄断厂商的成本函数为TC=Q 2+2Q ,产品的需求函数为P=10-3Q ,求: (1)利润极大的销售价格、产量和利润; (2)若政府试图对该垄断厂商采取限价措施,迫使其按边际成本定价,求此时的价格和厂商的产量、利润; (3)求解收支相抵的价格和产量。 5. 假设某完全竞争厂商使用劳动和资本两种生产要素进行生产,在短期内,劳动的数量可变,资本的数量固定。厂商的成本曲线为322()161803 LTC Q Q Q Q =-+和 32 ()224120400STC Q Q Q Q =-++,试计算: (1)厂商预期的长期最低价格是多少 (2)如果要素价格不变,在短期内,厂商会维持经营的最低产品价格是多少 (3)如果产品价格是120元,那么在达到短期均衡时,厂商将生产多少产品获得的利润是多少 6. . 已知某消费者的效用函数U =XY ,他打算购买X 和Y 两种商品,当其每月收入为120元,Px=2元,Py=3元时,试问: (1)为获得最大的效用,该消费者应如何选择商品X 和Y 的消费数量 (2)假设商品X 的价格提高44%,商品Y 的价格保持不变,该消费者必须增加多少收入才能保持原有的效用水平 7.已知某一时期内商品的需求函数为Q d =50-5P ,供给函数为Q s =-10+5P 。 (1)求均衡价格P e 和均衡数量Q e ,并作出几何图形。 (2)假定供给函数不变,由于消费者收入水平提高,使需求函数变为Q d=60-5P 。求出相应的均衡价格P e 和均衡量Q e ,并作出几何图形。 (3)假定需求函数不变,由于生产技术水平提高,使供给函数变为Q s =-5+5P 。求出相应的均衡价格P e 和均衡量Q e ,并作出几何图形。 8.假定表2—5是需求函数Q d =500-100P 在一定价格范围内的需求表: (1)求出价格2元和4元之间的需求的价格弧弹性。 (2)根据给出的需求函数,求P=2元时的需求的价格点弹性。 9假定表2—6是供给函数Qs=-3+2P 在一定价格范围内的供给表: (2)根据给出的供给函数,求P=4元时的供给的价格点弹性。 10.某种商品原先的价格为1元,销售量为1000公斤,该商品的需求弹性系数为,如果降价至元一公斤,此时的销售量是多少降价后总收益是增加了还是减少了增加或减少了多少
练习 1.1 图给出两台DFA M 1和M 2的状态图. 回答下述有关问题. a. M 1的起始状态是q 1 b. M 1的接受状态集是{q 2} c. M 2的起始状态是q 1 d. M 2的接受状态集是{q 1,q 4} e. 对输入aabb,M 1经过的状态序列是q 1,q 2,q 3,q 1,q 1 f. M 1接受字符串aabb 吗?否 g. M 2接受字符串ε吗?是 1.2 给出练习 2.1中画出的机器M 1和M 2的形式描述. M 1=(Q 1,Σ,δ1,q 1,F 1) 其中 1)Q 1={q 1,q 2,q 3,}; 2)Σ={a,b}; 3 415)F 1={q 2} M 2=(Q 2,Σ,δ2,q 2,F 2) 其中 1)Q 2={q 1,q 2,q 3,q 4}; 2)Σ={a,b}; 3 324)F 2={q 1,q 4} 1.3 DFA M 的形式描述为 ( {q 1,q 2,q 3,q 4,q 5},{u,d},δ,q 3,{q 3}),其中δ在表2-3中给出。试画出此机器的状态图。 d
1.6 画出识别下述语言的DFA 的状态图。 a){w | w 从1开始以0结束} b){w | w 至少有3个1} c) {w | w 含有子串0101} d) {w | w 的长度不小于3,且第三个符号为0} e) {w | w 从0开始且为奇长度,或从1开始且为偶长度} 或
f) {w | w 不含子串110} g) {w | w 的长度不超过5} h){w | w 是除11和111以外的任何字符} i){w | w 的奇位置均为1} j) {w | w 至少含有2个0,且至多含有1个1} k) {ε,0} l) {w | w 含有偶数个0,或恰好两个1} 0,1 1
微型计算机原理 第三章 80X86微处理器 1.简述8086/8088CPU中BIU和EU的作用,并说明其并行工作过程。答: (1) BIU的作用:计算20位的物理地址,并负责完成CPU与存储器或I/O端口之间的数据传送。 (2) EU的作用:执行指令,并为BIU提供所需的有效地址。 (3) 并行工作过程:当EU从指令队列中取出指令执行时,BIU将从内存中取出指令补充到指令 队列中。这样就实现了取指和执行指令的并行工作。 2.8086/8088CPU内部有哪些寄存器?其主要作用是什么? 答:8086/8088CPU内部共有14个寄存器,可分为4类:数据寄存器4个,地址寄存器4个,段寄 存器4个和控制寄存器2个。其主要作用是: (1) 数据寄存器:一般用来存放数据,但它们各自都有自己的特定用途。 AX(Accumulator)称为累加器。用该寄存器存放运算结果可使指令简化,提高指令的执行速度。此外,所有的I/O指令都使用该寄存器与外设端口交换信息。 BX(Base)称为基址寄存器。用来存放操作数在内存中数据段内的偏移地址, CX(Counter)称为计数器。在设计循环程序时使用该寄存器存放循环次数,可使程序指令简化,有利于提高程序的运行速度。 DX(Data)称为数据寄存器。在寄存器间接寻址的I/O指令中存放I/O端口地址;在做双字长 乘除法运算时,DX与AX一起存放一个双字长操作数,其中DX存放高16位数。 (2) 地址寄存器:一般用来存放段内的偏移地址。 SP(Stack Pointer)称为堆栈指针寄存器。在使用堆栈操作指令(PUSH或POP)对堆栈进行操作时,每执行一次进栈或出栈操作,系统会自动将SP的内容减2或加2,以使其始终指向栈顶。 BP(Base Pointer)称为基址寄存器。作为通用寄存器,它可以用来存放数据,但更经常更重要的 用途是存放操作数在堆栈段内的偏移地址。 SI(Source Index)称为源变址寄存器。SI存放源串在数据段内的偏移地址。 DI(Destination Index)称为目的变址寄存器。DI存放目的串在附加数据段内的偏移地址。 (3) 段寄存器:用于存放段地址 CS(Code Segment)称为代码段寄存器,用来存储程序当前使用的代码段的段地址。 CS的内容左移4位再加上指令指针寄存器IP的内容就是下一条要读取的指令在存储器中的物理地址。 DS(Data Segment)称为数据段寄存器,用来存放程序当前使用的数据段的段地址。 DS 的内容左 移4位再加上按指令中存储器寻址方式给出的偏移地址即得到对数据段指定单元进行读写的物理地址。 SS(Stack Segment)称为堆栈段寄存器,用来存放程序当前所使用的堆栈段的段地址。堆栈是存 储器中开辟的按“先进后出”原则组织的一个特殊存储区,主要用于调用子程序或执行中断服务程 序时保护断点和现场。 ES(Extra Segment)称为附加数据段寄存器,用来存放程序当前使用的附加数据段的段地址。附 加数据段用来存放字符串操作时的目的字符串。 (4) 控制寄存器 IP(Instmcdon Pointer)称为指令指针寄存器,用来存放下一条要读取的指令在代码段内的偏移地 址。用户程序不能直接访问IP。 FLAGS称为标志寄存器,它是一个16位的寄存器,但只