2000年春博题目(是99年秋天考的)。 qu!<lW~c
DZ%8 |PmB
计算理论 X$ PS(_M
一、1、根据图灵机理论,说明现代计算机系统的理论基础。 I2W{tl
2、说明按乔姆斯基分类,语言、文法、自动机的关系 O E]~@eU
8ur_/h7
一、 证明 HALT(X ` 1,X)不是可计算的。 3m~U(yho
X;5 S
三、1、证明递归集都是递归可枚举集。 r=|vad$
2、举例属于递归可枚举集但不是递归集的集合,并证明之。 I'P.K| "R
E~qK&7+
四、1、证明L={(a,b)*|a,b的个数相同}为上下文无关语言。 wV?[3bEhM
2、并证明其不是正则的。 78gob&p?
r*>QT:sB
NrW [Q3E$
2000年4月 (s.o
人工智能 mxZ4
HD{
1 什么是知识表示?用框架系统表示你的卧室。 &4[<F"W>47
2 描述A算法(描述A*) :> x:(K
3 专家系统模型?建立知识库(书上关于鸟类的例子)。 }&=u
Z:
专家系统的模型。根据下述事实建立分类专家系统的知识库。见书上哺乳动物、鸟类的分类系统例子。 &KLvr|
4 什么是自然语言的理解?写出下列句子的句法分析树。 E=3#TBd
1)I WANTED YOU TO DO SOMTHING. "hz>{oe
2) I SAW SOME CHILDREN PLAYING BALL IN THE FIELD. 5NFq7&rJ6
2000年10月 n2H&t>N
操作系统 }D(DU5r
1 产生死锁的必要条件。 zv&ePq\#
2 写出生产者和消费者的互斥程序(书上的例子)。 9$8X>T^
3 写出可对文件和目录进行的操作。 ]U#JsMS
虚拟存储页面置换的几种算法。 p
^
}L
g6HphRJ5s
计算理论 c,+iU R<
1、 USH@:c#t
(1)给出图灵机的格局、计算及图灵机μ计算函数f的精确定义。 +0pgq (
(2 ) 对图灵机模型而言,church论题是什么? lK_
~d_f
(3)当x是完全平方时值为3x,否则为3x+1证明其是原始递归函数。 oD Q9.t
5+o
2 T]
2、证明φ(X,X)是不可计算的。 tvGg@Xs\
't||F1X~J
3、证明L={ambn|m,n>0,m≠n}是上下文无关的,但不是正则的。 ,ZsYXW
&h98.A*&
4、A为有穷字母表,L是A*的无穷子集, ~NTDG
(1) 证明存在无穷序列ω0,ω1,ω2…,它由L的所有字组成,每个字恰好在其中只出现一次。 U&