護(hù)理心理學(xué)作業(yè)及答案全2015

1、第9章怎樣研究算法怎樣研究算法:遺傳算法示例遺傳算法示例1、P類問題、NP類問題、NPC類問題是計(jì)算機(jī)科學(xué)領(lǐng)域關(guān)于可求解性可計(jì)算性很重要的概念。關(guān)于P、NP和NPC類問題，回答下列問題。(1)下列說法不正確的是_____。(A)P類問題是計(jì)算機(jī)可以在有限時(shí)間內(nèi)能夠求解的問題；(B)NP類問題是計(jì)算機(jī)可以在有限時(shí)間內(nèi)能夠驗(yàn)證“解”的正確性的問題；(C)NPC類問題是對(duì)問題的每一個(gè)可能解，計(jì)算機(jī)都可以在有限時(shí)間內(nèi)驗(yàn)證“解”的正確性的問題，被

2、稱為NP完全問題；(D)上述說法有不正確的；答案：D解釋：本題考核P類問題、NP類問題、NPC類問題的概念。P類問題指計(jì)算機(jī)可以在有限時(shí)間內(nèi)求解的問題，(A)正確；NP類問題指雖然在多項(xiàng)式時(shí)間內(nèi)難于求解但不難判斷給定一個(gè)解的正確性問題，(B)正確；NPC問題指NP問題的所有可能答案都可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算，稱為NPComplete問題，(C)正確；(A)(B)(C)都正確，所以(D)錯(cuò)誤。具體內(nèi)容請(qǐng)參考第九章視頻之“可求解

3、與難求解問題”以及第九章課件。(2)可解性問題是指能夠找到多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行求解的問題，難解性問題是指找不到多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行求解的問題。下列說法不正確的是_____。(A)P類問題是可解性問題，NP類問題是難解性問題。(B)NP類問題不一定是難解性問題，因?yàn)镻類問題也一定是NP類問題；(C)NP類問題不確定是否是P類問題，但NPC類問題一定是難解性問題；(D)上述說法有不正確的；答案：A解釋：本題考核對(duì)可解性問題和難解性問

4、題概念的理解。P類問題指計(jì)算機(jī)可以在有限時(shí)間內(nèi)求解的問題，所以是可解性問題；NP類問題指雖然在多項(xiàng)式時(shí)間內(nèi)難于求解但不難判斷給定一個(gè)解的正確性問題，但P類問題是NP類問題的一個(gè)子集，所以NP類問題不一定是難解性問題；NPC問題指NP問題的所有可能答案都大學(xué)計(jì)算機(jī)計(jì)算思維練習(xí)題集(E)上述說法有不正確的；答案：B解釋：本題考核對(duì)P類問題、NP類問題概念的理解。P類問題是總能找到一個(gè)多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行求解的問題，NP類問題雖然是不確定

5、能找到多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行求解，但一定能找到多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行“解”的正確性驗(yàn)證的問題，所以(B)錯(cuò)誤。具體內(nèi)容請(qǐng)參考第九章視頻之“可求解與難求解問題”以及第九章課件。(6)非確定性多項(xiàng)式問題是指這樣的問題，下列說法不正確的是_____。(A)它能夠找到一個(gè)算法、甚至是多項(xiàng)式時(shí)間復(fù)雜性算法進(jìn)行求解，但算法中包含“不確定性”，如“任意組合一個(gè)解，…”、“隨機(jī)組合一個(gè)解，…”等；(B)它能夠找到一個(gè)算法、甚至是多項(xiàng)式時(shí)間復(fù)雜性算法

6、進(jìn)行求解，但算法是通過“猜測(cè)”方式求出問題的解；(C)它能夠通過“產(chǎn)生任何一個(gè)解，并驗(yàn)證解的正確性”的方法進(jìn)行求解；(D)它一定是能夠找到多項(xiàng)式時(shí)間復(fù)雜性算法以驗(yàn)證給定“解”的正確性的問題；(E)上述說法有不正確的；答案：E解釋：本題考核對(duì)NP類問題概念的理解。NP類問題：非確定性多項(xiàng)式問題(NondeterministicPolynomial)。有些問題，其答案是無法直接計(jì)算得到的，只能通過間接的猜算或試算來得到結(jié)果，這就是非確定性問

7、題(Nondeterministic)。雖然在多項(xiàng)式時(shí)間內(nèi)難于求解但不難判斷給定一個(gè)解的正確性的問題，即：在多項(xiàng)式時(shí)間內(nèi)可以由一個(gè)算法驗(yàn)證一個(gè)解是否正確的非確定性問題，所以(A)(B)(C)(D)都是正確的，(E)錯(cuò)誤。具體內(nèi)容請(qǐng)參考第九章視頻之“可求解與難求解問題”以及第九章課件。(7)、關(guān)于NP類問題求解，下列說法正確的是_____。(A)NP類問題求精確解，可能找不到多項(xiàng)式時(shí)間復(fù)雜性算法；但NP類問題求近似解，則一定能夠找到多項(xiàng)式