程序設(shè)計(jì)理論各年試題參考答案

1、程序設(shè)計(jì)理論各年試題參考答案Made by 林祺穎試題預(yù)測(cè)（這些為本人意見，僅供參考） ：題目前有 #為考試必考內(nèi)容，即類似的題目一定會(huì)出，一定要靈活掌握。 題目前沒有符號(hào)的為可能考內(nèi)容，一定要知道怎樣做。題目前有 3. Consider evaluation of the logic expressions with only operators &,| and | in C programming language. Construct an abstract machine for evaluation of the expressions and try to define the m

2、eaning function M(e) :Bool for any given expression e.這題不會(huì)寫。師兄也沒給出答案。 _題目意思是，對(duì)于一個(gè)只有 &,|,| 操作的 C 語言邏輯表達(dá)式，建立起抽象機(jī)，并且給出對(duì)于 給定的表達(dá)式 e，給出對(duì)應(yīng)的 meaning function M(e) :Bool 的定義 符號(hào)的為基本不考內(nèi)容，瀏覽一下即可。答案參考（如有任何補(bǔ)充或者感覺不對(duì)的地方，一定要向我提出來噢） ：黑色的為個(gè)人感覺沒有問題的部分，如果發(fā)現(xiàn)有錯(cuò)誤，那一定要跟我說。紅色 的為個(gè)人感覺可以修改或者不確定，甚至不太會(huì)做的部分，大家一起討論。 綠色 的為提示或者需要注意的部

3、分。用 w 代替。聯(lián)系方式：在群上找林祺穎，或者加 QQ： 1238260，我基本都在。面有些符號(hào)為了錄入方便，都作了一些替代，標(biāo)準(zhǔn)符號(hào)可要看書。如程序設(shè)計(jì)理論試題 2004 年 01 月 06 日該卷答案基本是一個(gè)師兄做的，紅色為我補(bǔ)充的部分1. Show that (P(Nat), ) is not a Well-founded Set, but(S|S is a finite subset of Nat,) is awell-founded set解釋： P(Nat) 為自然數(shù)集合的集合。即 Nat 的 Power Set。取第 1 個(gè)集合為 Nat, 第 2個(gè)集合為 Nat-1, 。,

4、第 n 個(gè)集合為 Nat-1,2,.n-1, 則可以產(chǎn)生 一個(gè) infinite descending sequence ( 無窮遞降序列 ), 所以 (P(Nat), )不是 Well-founded Set.設(shè) T=S|S is a finite subset of Nat, 若 (T, ) 不是 Well-founded Set, 則必然存在一個(gè) infinite descending sequence, 設(shè)為 a1,a2, ,an 則, a1 a2 an , 從而 |a1|a2| |an| 因?yàn)?ai 屬于 T(i=1), 即 ai 是一個(gè)有限集，所以 |ai|是一個(gè)有限的自然數(shù)， |

5、ai|不能形成一個(gè)無 限下降的序列，矛盾，所以 (T, )是 Well-founded Set.2. Show that for all formulas w 1 and w2, the formula w 1 w2 and w1 w2 and logically equivalent.證明 w1 w2 與 w1 w2 邏輯等價(jià)，即是要證明 |= w1 w2 w1 w2. 對(duì)于任意的 Interpretation I, I(w1 w2 w1 w2)( )等 價(jià)于 I(w1)( )I(w2)( ) I(w1)( )I(w2)( ), 因 為 w1,w2: Bool, 所 以 I(w1)( )=t

6、rue或 者 I(w1)()=false, I(w2)( )=true 或 者 I(w2)( )=fal。se若 I(w1)( )=true, I(w2)( )=true, 則 I(w1 w2w1 w2)( ) = (true truetrue true)=true;其余三種情況類似地也有 I(w1 w2w1 w2)( )true.所以 |= w1 w2w1 w2, 從而 w1 w2 與 w1 w2 邏輯等價(jià)。#4. Present the partial order ( Bool m Bool , ) graphically. How many elements does it have?

7、How many elements are maximal?這是一個(gè)定義在由 Bool 映射到 Bool 的函數(shù)的偏序集。并且是具有 =關(guān)系，所以某些映射 是不能成立的，如 ( t,ure),(true, ).Bool Bool 共有 11 個(gè)元素，用 ai(1=i(if 2=0 then 1 else 2*F(2-1)fi) =(if false then 1 else 2*F(1) fi) =2*F(1)=2*(if 1=0 then 1 else 1*F(1-1) fi) =2*(if false then 1 else 1*F(0) fi) =2*(1*F(0)=2*(1*1)=2(b

8、) 對(duì)應(yīng)邏輯程序如下 :F(0,1) .F(x,n) F(x-1,m),n=x*m 目標(biāo)是 F(2,x)這里要注意， 最后會(huì)出現(xiàn)不為空的情況 true:-. 另一種是需要加式子 m:-(2=0,false),(2-1,1)(if false then 1 else 2*F(1) fi, 2*F(1)(1=0,false),(1-1,0)(if false then 1 else 1*F(0) fi, 1*F(0) (F(0),1)(2*(1*1),2)即不是 Refutation ），有一種理解是具有默認(rèn)的式子(c) 邏輯程序的 derivation:G PF(2,x)= F(1,m1),x=

9、2*m1 = F(0,m2),m1=1*m2,x=2*m1= m1=1*m2,x=2*m1F(x1,n1) F(x1-1,m1),n1=x1*m1F(x2,n2) F(x2-1,m2),n2=x2*m2F(0,1)x1/2,n1/xx2/1,n2/m1m2/1= m1=2, x=4= 再根據(jù) true:-和替換 (m1/2,x/4) ，可以歸到。6. Give an example of a functional program for which the semantic functional is the identityfunction. Explain why?假設(shè)在 Usual In

10、terpretation I=(Nat,I 0)下，定義函數(shù)程序?yàn)?: F(x) 0 時(shí)，設(shè) =(1l,l2, lk), r=wlp( p), 根據(jù) l0 處的語句類型，分成兩種情況來定義 wlp(a,p).如果是平行的賦值語句，設(shè)形式如下所示 :l0: (x1,x2, xn):=(t1,t2,to lt1n; ); go則定義 wlp(a,p)= rxt11,txnn ;如果是條件轉(zhuǎn)移語句，設(shè)形式如下所示 : l0: if e then goto l else goto l fi;則定義 wlp(a,q)如下 :e r 如果 l1=l 且 l1 l e r 如果 l1 且l l1=l (ii

11、) 定義 partial correctness 的驗(yàn)證條件 vc(p,a,q) 為 p wlp(a,q).令B 為謂詞邏輯的 basis, p,q為WFFB的兩個(gè)公式， S L1B是一個(gè) flowchart 程序，對(duì)于 任意的 Interpretation I, 程序 S 在 Interpretation I 中，對(duì)于 p 和 q 是 partial correct 的，當(dāng)且僅 當(dāng)如果對(duì)于 S中的任意一條路徑 a, 都有驗(yàn)證條件 vc(p,a,q) 在I中為 valid 。#8.Show that the following is a correct inference rule in Ho

12、are logic using construction sequencein “Inductive Definition of Sets”. What are B and K in this context? And what is the inductively defined set in the context?p r,r e S r,( r e) q p while e do S od qfor all p,q,r WFF B, eQFFB, and SL2B.設(shè) WFFB 為 well-formed formula 的集合B= ptx x:=tp | p WFF B,x V, tT

13、BK= ( (p r, r eSr, (r e) q ) , pwhile e do S od q)|Bp,q,rWFFB,eQFFB,S L2推導(dǎo)出來的集合是 Hoare calculus 里面 logically valid 的公式集的一個(gè)子集。 推導(dǎo)過程： P-rreS1rr e-qrwhile e do S1 od repwhile r do S1 od qn w或者 n i， n Nat程序設(shè)計(jì)理論試題 2000.1.22(即老師的樣題)n Nat,0 n i -1w1.S fi |i Nat, fi :NatwNatw, fi(n)n!試指出鏈 S 在 Natw-Natw上的最小上

14、界。有些人說論域就是 CPO。對(duì)于該題， 由于 Nat ，且 (+)(a,b)( =)a+b,2*為 Nat 2-Nat ，且 (*)(a,b) ( =)a*b ，2Bool ，且 (=)(a,b) ( =)a=b 該公式的語義為 (Vx.(0=x)=true iff 所有的 x 屬于 Nat， (=)(0,x) ( =)true ，即 0 小 于等于 x (不建議寫成 x 大于等于 0)。7 (P(3,1)= (y:=1;if y=1 then x:=1 else x:=2 fi)(3,1) =(if y=1 then x:=1 else x:=2 fi)(3,1) =(if true th

15、en x:=1 else x:=2 fi)(3,1) =(x:=1)(3,1) =(1,1)#8. 對(duì)于格局 (S1， )，并對(duì)格局 (S1，)轉(zhuǎn)移到 (S2，),有： 當(dāng) S1 為 while e do S od ;S 時(shí)， S ，有 =， 且 S2為 a. S;S1當(dāng) (e)()=trueb. S當(dāng) (e)()=false當(dāng) S1 為 While e do S od 時(shí)，有 = ，且 S2 為 a. S當(dāng) (e)()=trueb.當(dāng) (e)()=false#9當(dāng)使用通常解釋 I 時(shí)，有F(2)= if 2=0 then 1 else 2*F(2-1) fi = if false then

16、1 else 2*F(1) fi = 2*(if 1=0 then 1 else 1*F(1-1) fi)=2*(if false then 1 else 1*(F(0) fi)=2*1*(F(0)=2*(if 0=0 then 1 else 0*F(0-1) fi)=2*1=2F(-2) 由于不可終止，所以 F(-2)未定義#10Vc(q,(test,loop,upd,test),q) q-wlp(test,loop,upd,test),q) wlp(test,q)=qwlp(upd,test),q)=q(y3+y2/y3)wlp(loop,upd,test),q)=q(y3+y2/y3)(

17、y1+1,y2+2/y1,y2)wlp(test,loop,upd,test),q)=(y3 (x=a (y1+1)2=c y3+y2+2=(y1+1+1)2 y2+2=2*(y1+1)+1)vc( )=(x=a y12=x y3=(y1+1)2 y2=2*y1+1 y3(x=a (y1+1)2rreS1rr-e-qr while e do S1 od r-ep while e do S1 od q(可看書 P153)程序設(shè)計(jì)理論期末練習(xí)題1. 可參考老師樣題的第 6 題。*2. 這題很難寫。先給個(gè)思路：第一要建立一個(gè) well-founded set(自然數(shù)集) ，并且需要最 小值為 0。然

18、后證明對(duì)于 x0 ，每次的計(jì)算都是遞減。然 后下結(jié)論。#3. 參考書本 P50。#4. F(x) Nat)-Nat 的函數(shù)，并設(shè)為 G。則 G(op) =F(3,x)( F/op)=op(3,4)則 ( F.F(3,x)*)()( )=3*4=12 ?？煽磿?P95。程序設(shè)計(jì)理論期末考試 (99)這年考試題目側(cè)重于概念，與之后幾年的題目有很大的區(qū)別*1. 問得真直接。不好做。 指稱語義：定義了基類，然后由基類影射到相應(yīng)的函數(shù)，然后由函數(shù)來定義其語義。 操作語義：定義了抽象機(jī)，然后及其相關(guān)操作。由抽象機(jī)的運(yùn)行和狀態(tài)來反映其語義。 異：指稱語義表示的語言要比操作語義要多。指稱語義重點(diǎn)在指稱上，即所

19、對(duì)應(yīng)的函數(shù)上。 而操作語義的重點(diǎn)在于抽象機(jī)的運(yùn)行及其狀態(tài)。*2. 使用 CPO的目的是最終能夠歸到基類，并且能夠歸到F和 V 這兩個(gè)最基本的類型。最小元表示函數(shù)影射的開始，也就是尋找對(duì)應(yīng)的語義中的最小語義單位。Chain 就是其影射過程，也即對(duì)應(yīng)的語義解釋過程。*3. Imperative Language: 即命令方式語言。 Algol-Like 語言。 該類語言通過各種相對(duì)獨(dú)立的語 句，語句自身是不會(huì)直接或間接調(diào)用自己， 可以通過獨(dú)立地對(duì)每條語句的解釋來進(jìn)行語義分 析。Declarative Language 即聲明方式語言。 Lisp-Like 語言。該類語言使用聲明性語句，語句自 身會(huì)

20、直接或者間接調(diào)用自己，通過對(duì)多個(gè)變量的映射關(guān)系，來最終確認(rèn)其對(duì)應(yīng)的語義。*4 個(gè)人感覺是正確的。 因?yàn)槿绻绦虻恼Z義脫離了形式系統(tǒng)， 那么程序的語義就不能解釋 或者不可理解了。而程序的正確性也不可驗(yàn)證了。5. 參考老師樣題。6. 參考老師樣題。7. 參考課本 P50。數(shù)據(jù)不同，最后結(jié)果為 (,(5,2,5,9)*8. 書本 P25。簡(jiǎn)單來說就是一個(gè)解釋 ， (w)( )=tr則ue,為 W 的 Model 。9 Complete。因?yàn)槎x了一個(gè)，即每個(gè) chain 都存在 lub 。這里要提出一個(gè)， R+也是 CPO。有人提出鏈： 1.1 ，1.11 ，1.111 ,，沒有 Lub。其實(shí)1。是

21、有的， lub 1 1 ,即1.1910. M(S)=x mod 2.11部分正確性是基于程序?qū)斎胗卸x下的正確性，即程序?qū)戏ǖ妮斎胧钦_的。 而完全正確性是需要證明其程序?qū)斎胗卸x的，即程序?qū)τ谳斎胧钦_的，并且可以終止的。 基于謂詞的正確性是證明給定的謂詞是正確的?；诠降恼_性是證明公式的守恒。12Partial Correct: i: 說明程序是無論有沒定義都部分正確。Ii: 說明程序是處處都沒有定義。Terminate: 程序處處有定義。13. 程序輸入是 x=y ，輸出是 x=y! ，所以最后的結(jié)果一定是讓 x 為 y！，y 在程序中可變(改 變以后可以歸回原來的值) ，但

22、最后的結(jié)果必定要讓 x=y! 。并且 y 要等于原值才是計(jì)算階乘 的程序。14. 為了保證每條路徑都遍歷，即程序的運(yùn)行情況都可保證。15. (pSq)( )=true iffIf (p)( =)true and if M (S)( )is defined,Then (q)(M (S)( )=true.看書 P150。程序設(shè)計(jì)理論期末考試 (2000)1. 想不到其他方法。用定義證明。2. 麻煩。直接證。不寫了。ii:說明程序是無論有沒定義都部分正確。iv. 同 iivi. 說明程序是無論有沒定義都可終止。3. i:說明程序是處處都沒有定義。 iii. 同 iiv. 程序處處有定義。4程序的執(zhí)行

23、就是對(duì)機(jī)器的操作，即由一種狀態(tài)轉(zhuǎn)換到另外一種狀態(tài)。程序狀態(tài) :是程序真實(shí)的狀態(tài)，與機(jī)器無關(guān)。機(jī)器狀態(tài) :機(jī)器狀態(tài)反映了程序狀態(tài)。5.輸入即 x=2,y=2,z=2 輸出要符合 x=2*y y=4*z ， 可能的輸出為 x=16 y=8 z=2 由于這題沒說中間的結(jié)果， z的值可以改變， 所以答案也可以是 8,4,1。甚至 24,12,3 都可以。反正滿足最后的條件就可以了。6狀態(tài)是由 (l1, 1)轉(zhuǎn)換到 (l2, 2)(1)2=1x/0(2) 2=1x/x+1(3) 2=1x,y/y,x(4) 定義 l1 下一指令為 l1,再下一指令為 l1. 2=1且l2=l1 if x!=0l2=l1

24、if x=07.老師樣題。8. 1=(begin,3,6,end) 2=(begin,2,6,end) 3=(begin,3,5,end)wlp:m1m2 m2m3wlp:m2m1 m1m3wlp:m1m2 m3m2 wlp:m2m1 m3 相等 由 continuous 定義可知，相等。 相等 -Continuous 由 Continuous 定義可知。書 P77。(b)不會(huì)做。10. 類似于作業(yè)?？赏瞥?Refutation 。下面是作業(yè)的解答。-f(2,2,x)(3)=(m/2,n/2,y/y1)-f(2,1,y1),f(1,y1,x)(3)=(m/2,n/1,x/y1,y/y2)-f(

25、2,0,y2),f(1,y2,y1),f(1,y1,x)(2)=(m/2,x/y2)-f(1,1,y2),f(1,y2,y1),f(1,y1,x)(3)=(m/1,n/1,x/y2,y/y3)-f(1,0,y3),f(0,y3,y2),f(1,y2,y1),f(1,y1,x)(2)=(m/1,x/y3)-f(0,1,y3),f(0,y3,y2),f(1,y2,y1),f(1,y1,x)(1)=(n/1,y3/2)-f(0,2,y2),f(1,y2,y1),f(1,y1,x)(1)=(n/2,y2/3)-f(1,3,y1),f(1,y1,x)(3)=(n/1,m/3,y/y4)-f(1,2,y4),f(0,y4,y1),f(1,y1,x)(3)=(m/1,n/2,x/y4,y/